text:
# Full Lecture 14

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

# Convergence

In this lecture we will focus on extremely useful results that occur when we consider large sample sizes. In order to analyze these results, we need to introduce a few concepts related to convergence of sequences of random variables.

A sequence of random variables $X_{n}$ converges to a random variable $X$:

• in probability if $\lim_{n\rightarrow\infty}P\left(\left|X_{n}-X\right|\geq\varepsilon\right)=0,\,\forall\varepsilon\gt 0$
• almost surely if $P\left(\lim_{n\rightarrow\infty}\left|X_{n}-X\right|\gt \varepsilon\right)=0,\,\forall\varepsilon\gt 0$
• in quadratic mean if $\lim_{n\rightarrow\infty}E\left[\left(X_{n}-X\right)^{2}\right]=0$

Some convergence concepts are 'stronger' than others. The following facts are useful:

• $X_{n}\overset{q.m.}{\rightarrow}X\Rightarrow X_{n}\overset{p}{\rightarrow}X$
• $X_{n}\overset{a.s.}{\rightarrow}X\Rightarrow X_{n}\overset{p}{\rightarrow}X$
• Quadratic mean convergence does not imply, nor is it implied, by almost sure convergence

## Example: Convergence in Probability vs. Almost Sure Convergence

Let

$X_{n}=\begin{cases} 1, & \text{with probability }\frac{1}{n}\\ 0, & \text{with probability }1-\frac{1}{n} \end{cases}$

$Y_{n}=\begin{cases} 1, & \text{with probability }\frac{1}{n^{2}}\\ 0, & \text{with probability }1-\frac{1}{n^{2}} \end{cases}$

Do these random sequences converge in probability and/or almost surely to zero?

We first check that both sequences converge in probability to zero. For $X_{n}$, we require

\begin{aligned} & \lim_{n\rightarrow\infty}P\left(\left|X_{n}-0\right|\geq\varepsilon\right)=0\\ \Leftrightarrow & \lim_{n\rightarrow\infty}P\left(X_{n}\geq\varepsilon\right)=0\end{aligned}

If $\varepsilon\gt 1$, the condition above is always satisfied, since $X_{n}\in\left\{ 0,1\right\}$.

For $\varepsilon\in\left(0,1\right)$, we have

\begin{aligned} & \lim_{n\rightarrow\infty}P\left(X_{n}\geq\varepsilon\right)=0\\ \Leftrightarrow & \lim_{n\rightarrow\infty}P\left(X_{n}=1\right)=0\\ \Leftrightarrow & \lim_{n\rightarrow\infty}\frac{1}{n}=0\end{aligned}

which does indeed hold. The same method can be used to prove convergence in probability for $Y_{n}$.

Now, consider convergence almost surely.

For $X_{n}$, we require

\begin{aligned} & P\left(\lim_{n\rightarrow\infty}\left|X_{n}-X\right|\gt \varepsilon\right)=0\\ \Leftrightarrow & P\left(\lim_{n\rightarrow\infty}X_{n}\gt \varepsilon\right)=0\\ \Rightarrow & P\left(\lim_{n\rightarrow\infty}X_{n}=1\right)=0\end{aligned}

where the last equation follows from the fact that $X\in\left\{ 0,1\right\}$, and that the condition can only be satisfied if the probability of $X_{n}$ equaling 1 vanishes as $n\rightarrow0$.

We will approach this problem indirectly.

Consider the sum, starting at a very high $n$, of the probability that $X_{n}=1$: $\sum_{i=n}^{\infty}P\left(X_{n}=1\right)=\sum_{i=n}^{\infty}\frac{1}{i}$.

If this sum diverges, it means that for very high $n$, we still obtain $X_{n}=1$ with a finite probability, such that adding all the ones creates a diverging sum. If, on the other hand, the sum converges, this means that when $n$ is large, the probability of observing $X_{n}=1$ equals zero. Notice that

$\sum_{i=n}^{\infty}P\left(X_{n}=1\right)=\sum_{i=n}^{\infty}\frac{1}{i}=\infty$

and

$\sum_{i=n}^{\infty}P\left(Y_{n}=1\right)=\sum_{i=n}^{\infty}\frac{1}{i^{2}}\lt \infty$

(We don’t prove the results above here.)

While both sequences converge in probability to zero, only $Y_{n}$ converges almost surely. The reason is that, when $n$ is very high, the probability of observing $X_{n}=1$ remains finite (so that the sum of subsequent probabilities diverges), while the probability of observing $Y_{n}=1$ vanishes to zero (so that the sum of subsequent probabilities converges).

## Estimator Consistency

Because estimators are statistics, we can apply the definitions we have found to them as well.

We say that an estimator $\widehat{\theta}$ is consistent if

$\widehat{\theta}\left(X_{1}..X_{n}\right)\overset{p}{\rightarrow}\theta,\forall\theta\in\Theta$,

where $X_{1}..X_{n}$ is a sequence of random variables (usually, data).

For example, the maximum-likelihood estimator is consistent, i.e., $\widehat{\theta_{ML}}\overset{p}{\rightarrow}\theta_{0}$.

# Theorem: Law of Large Numbers

Let $X_{1}..X_{n}$ be a sequence of random variables, where $E\left(X_{i}\right)=\mu$ and $Var\left(X_{i}\right)\lt \sigma^{2}$.

Then,

$\overline{X}_{n}=\frac{1}{n}\sum_{i=1}^{n}X_{i}\overset{p}{\rightarrow}\mu.$

This result is probably not very surprising, and in a sense, we have been using it intuitively for the method-of-moments estimator.

The sample mean, as $n$ increases, converges in probability to the population mean $E\left(X_{i}\right)$.

The proof follows from Chebychev’s inequality:

$Pr\left(\left|\overline{X}_{n}-\mu\right|\geq\varepsilon\right)\leq\frac{Var\left(\overline{X}_{n}\right)}{\varepsilon^{2}}=\frac{\sigma^{2}}{n\varepsilon^{2}}$ such that $\lim_{n\rightarrow\infty}\,Pr\left(\left|\overline{X}_{n}-\mu\right|\geq\varepsilon\right)\leq\lim_{n\rightarrow\infty}\,\frac{\sigma^{2}}{n\varepsilon^{2}}=0,\,\forall\varepsilon\gt 0.$

Notice that we did not restrict $X_{i}$ to be a random sample. If we are willing to impose that condition, we can prove a stronger result:

## Strong Law of Large Numbers

Let $X_{1}..X_{n}$ be a random sample with mean $\mu$. Then,

$\overline{X}_{n}=\overset{a.s.}{\rightarrow}\mu$

Although this result applies for any random sample, in this case, we do not require that $\sigma^{2}$ exists, such that it may not converge in quadratic mean.

# Convergence in Distribution

A sequence of random variables $X_{n}$ converges in distribution to a random variable $Y$ if, at all continuity points of $F_{Y}\left(y\right)$,

$\lim_{n\rightarrow\infty}\,F_{X_{n}}\left(y\right)=F_{Y}\left(y\right)$

Convergence in distribution is very intuitive: As $n\rightarrow\infty$, the distributions of $X_{n}$ converge point-by-point to that of $Y$.

## Example

The reason we only require the limit condition to hold only at continuity points of $F_{Y}$ can be illustrated with an example (the specific reasoning is a bit deeper, but we won’t concern ourselves with that).

Let $f_{X_{N}}=\begin{cases} n, & 0\lt x\lt \frac{1}{n}\\ 0, & otherwise \end{cases}$

Clearly, as $n\rightarrow\infty$, $X_{n}$ is approaching a mass point at zero, so we may want it to converge in distribution to $Y$, where $P\left(Y=0\right)=1$. However, the value of $F_{X_{N}}\left(0\right)$ is zero for all $n$, and so $\lim_{n\rightarrow\infty}F_{X_{N}}\left(0\right)\neq F_{Y}\left(0\right)=1$.

By not requiring that the limit condition holds at $F_{Y}\left(0\right)$, we do satisfy convergence in distribution, i.e., $X_{n}\overset{d}{\rightarrow}Y_{n}$.

# Slutsky’s Theorem

Slutsky’s Theorem provides some nice results that apply to convergence in distribution:

If a sequence $X_{n}$ converges in distribution to $X$, and a sequence $Y_{n}$ converges in probability to a constant $c$, then

• $X_{n}.Y_{n}\overset{d}{\rightarrow}c.X$
• $X_{n}+Y_{n}\overset{d}{\rightarrow}c+X$
• $\frac{X_{n}}{Y_{n}}\overset{d}{\rightarrow}\frac{X}{c}$ if $c\neq0$

The results above also holds if $X_{n}$ converges in probability, in which case the implications also apply to convergence in probability.

# Central Limit Theorem

Let $X_{1}..X_{n}$ be a random sample with twice differentiable generating function $M_{X}\left(t\right)$ in a neighborhood of zero, and mean $\mu$ and variance $\sigma^{2}.$

Then,

$\frac{\sqrt{n}\left(\overline{X}_{n}-\mu\right)}{\sigma}\overset{d}{\rightarrow}N\left(0,1\right)$

This is a striking result. When $n$ is large, the standardized sample mean converges to the standard normal distribution.

## Proof

We first define the standardized variable $Y_{i}=\frac{X_{i}-\mu}{\sigma}$, s.t.

$M_{Y}^{'}\left(0\right)=E\left(Y\right)=0$ and $M_{Y}^{''}\left(0\right)=Var\left(Y\right)=1$.

Notice that $\frac{1}{\sqrt{n}}\sum_{i=1}^{n}Y_{i}=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\frac{X_{i}-\mu}{\sigma}=\frac{n}{\sqrt{n}}\sum_{i=1}^{n}\frac{\overline{X}_{n}-\mu}{\sigma}=\sqrt{n}\frac{\overline{X}_{n}-\mu}{\sigma},$ which is our statistic of interest.

So, if we show that $\frac{1}{\sqrt{n}}\sum_{i=1}^{n}Y_{i}$ has the same m.g.f. as $N\left(0,1\right)$, because we have assumed that $M_{X}\left(t\right)$ exists in a neighborhood of zero, this will imply

$\frac{1}{\sqrt{n}}\sum_{i=1}^{n}Y_{i}=\sqrt{n}\sum_{i=1}^{n}\frac{\overline{X}_{n}-\mu}{\sigma}\sim N\left(0,1\right)$ (Recall that the m.g.f. only identifies the distribution of $Z$ if $M_{Z}\left(0\right)$ exists).

Now, notice that if $Z_{n}=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}Y_{i}$,

\begin{aligned} & =M_{Z_{n}}\left(t\right)=E\left[\exp\left(t\frac{1}{\sqrt{n}}\sum_{i=1}^{n}Y_{i}\right)\right]=E\left[\Pi_{i=1}^{n}\exp\left(t\frac{Y_{i}}{\sqrt{n}}\right)\right]\\ & \underset{(i.i.d.)}{=}\Pi_{i=1}^{n}E\left[\exp\left(t\frac{Y_{i}}{\sqrt{n}}\right)\right]=\Pi_{i=1}^{n}M_{Y_{i}}\left(\frac{t}{\sqrt{n}}\right)=M_{Y}\left(\frac{t}{\sqrt{n}}\right)^{n}.\end{aligned}

Let us now expand $M_{Y}\left(\frac{t}{\sqrt{n}}\right)$ around zero:

$M_{Y}\left(\frac{t}{\sqrt{n}}\right)=M_{Y}\left(0\right)+M_{Y}^{'}\left(0\right)\frac{t}{\sqrt{n}}+\frac{M_{Y}^{''}\left(0\right)}{2}\left(\frac{t}{\sqrt{n}}\right)^{2}+R_{Y}\left(\frac{t}{\sqrt{n}}\right)$

by Taylor’s theorem, the remainder approaches zero as $n$ approaches infinity. We will ignore it from now on (but it is possible to prove precisely that it vanishes).

Notice also that $M_{Y}\left(0\right)=1,$ $M_{Y}^{'}\left(0\right)=E\left(Y\right)=0$ and $M_{Y}^{''}\left(0\right)=Var\left(Y\right)=1$, s.t. we obtain

$M_{Y}\left(\frac{t}{\sqrt{n}}\right)\simeq1+0+\frac{t^{2}}{2n}$

When $n$ is large, we obtain $\lim_{n\rightarrow\infty}\left[M_{Y}\left(\frac{t}{\sqrt{n}}\right)\right]^{n}=\lim_{n\rightarrow\infty}\left(1+\frac{t^{2}}{2n}+\underset{\rightarrow0}{\underbrace{R_{Y}\left(\frac{t}{\sqrt{n}}\right)}}\right)^{n}=\lim_{n\rightarrow\infty}\left(1+\frac{t^{2}}{2n}\right)^{n}=\text{e}^{\frac{t^{2}}{2}}.$

The result is the m.g.f. of $N\left(0,1\right)$, thereby proving the CLT.

# Delta Method

The delta method allows us to approximate the distribution of the transformation of a random variable, as long as $n$ is large.

The delta method states that if a sequence of random variables $X_{n}$ satisfies $\sqrt{n}\left(X_{n}-\mu\right)\overset{d}{\rightarrow}N\left(0,\sigma^{2}\right)$ then for any function $g\left(\cdot\right)$ continuously differentiable in a neighborhood of $\mu$ with derivative $g^{'}\left(\mu\right)$,

$\sqrt{n}\left(g\left(X_{n}\right)-g\left(\mu\right)\right)\overset{d}{\rightarrow}N\left(0,g^{'}\left(\mu\right)^{2}.\sigma^{2}\right)$

## Proof

The proof involves expanding $g\left(X_{n}\right)$ around $\mu$:

$g\left(X_{n}\right)=g\left(\mu\right)+\left(X_{n}-\mu\right)g^{'}\left(\mu\right)+R\left(X_{n}\right)$.

We can rewrite this version of the Taylor expansion using the mean value theorem, which yields the alternative version

$g\left(X_{n}\right)=g\left(\mu\right)+\left(X_{n}-\mu\right)g^{'}\left(\tilde{X}_{n}\right),\,for\,some\,\tilde{X}_{n}\in\left(X_{n},\mu\right)$.

Moving $g\left(\mu\right)$ to the lhs yields $g\left(X_{n}\right)-g\left(\mu\right)=\left(X_{n}-\mu\right)g^{'}\left(\tilde{X}_{n}\right)$

Because $\tilde{X}_{n}$ lies between $X_{n}$ and $\mu$, $\tilde{X}_{n}\overset{p}{\rightarrow}\mu$ if $X_{n}\overset{p}{\rightarrow}\mu$.

Remembering that

$\sqrt{n}\left(X_{n}-\mu\right)\overset{d}{\rightarrow}N\left(0,\sigma^{2}\right)$,

then,

$\underset{\overset{d}{\rightarrow}N\left(0,\sigma^{2}\right)}{\underbrace{\sqrt{n}\left(X_{n}-\mu\right)}}.\underset{\overset{p}{\rightarrow}g^{'}\left(\mu\right)}{\underbrace{g^{'}\left(\tilde{X}_{n}\right)}}\Rightarrow\sqrt{n}\left(g\left(X_{n}\right)-g\left(\mu\right)\right)\overset{d}{\rightarrow}N\left(0,g^{'}\left(\mu\right)^{2}.\sigma^{2}\right)$

To obtain the result above, we first used the facts that $\sqrt{n}\left(X_{n}-\mu\right)\overset{d}{\rightarrow}N\left(0,\sigma^{2}\right)$ and that $g^{'}\left(\tilde{X}_{n}\right)\overset{p}{\rightarrow}g^{'}\left(\mu\right)$. By Slutsky’s theorem, the product converges in distribution to the distribution of $g^{'}\left(\mu\right).\sigma.Z$, where $Z=N\left(0,1\right)$. Finally, the last result follows from the fact that $\sqrt{n}\left(X_{n}-\mu\right)g^{'}\left(\tilde{X}_{n}\right)=\sqrt{n}\left(g\left(X_{n}\right)-g\left(\mu\right)\right)$.

This result is often useful to calculate the distribution of a transformation of an estimator. For example, while estimating a model, it may be convenient to constrain a parameter estimate of $\theta$ to be positive. One way to accomplish this is to estimate some parameter $\widehat{\beta}$, s.t. $\widehat{\theta}=\exp\left(\widehat{\beta}\right)$. For any value of $\widehat{\beta}$, we will obtain a positive estimate of $\widehat{\theta}$ by applying the exponential. If we know the distribution of $\sqrt{n}\left(\widehat{\beta}-E\left(\widehat{\beta}\right)\right)$ has a $N\left(0,\sigma^{2}\right)$ distribution, then the delta method can be used to produce the distribution of $\widehat{\theta}$. To be clear, in this case the sequence of random variables $X_{n}$ would be data, such that $\widehat{\beta}_{n}=\widehat{\beta}\left(X_{n}\right)$, for example.

# Somewhat Pedantic Remark on Notation

You may have noticed that statements like

$\sqrt{n}\left(X_{n}-\mu\right)\overset{d}{\rightarrow}N\left(0,\sigma^{2}\right)$

seem overly complicated. It may seem simpler to write the statement above as

$\frac{\sqrt{n}\left(X_{n}-\mu\right)}{\sigma}\overset{d}{\rightarrow}N\left(0,1\right)$

or even

$X_{n}\overset{d}{\rightarrow}N\left(\mu,\frac{\sigma^{2}}{n}\right)$.

While the second statement is perfectly fine, the last statement is problematic. The reason is that the right-hand side, $N\left(\mu,\frac{\sigma^{2}}{n}\right)$, is the distribution limit of the left-hand side in $n$, and so should not depend on $n$. So, try to keep $n$ in the left-hand side. If you really want to have it on the right-hand side, you can use the alternative notation,

$X_{n}\overset{\sim}{\sim}N\left(\mu,\frac{\sigma^{2}}{n}\right).$


text:
# Finding the Area of a polygon

1. May 21, 2007

### disregardthat

Hi, I am to find a formula for the area of a regular polygon with a side "a".

I just keep getting the wrong answer: this is how i did it:

if we draw a circle in a coordinate system, with radius "r". The diameter lyes on the x-axis. I draw an angle from the center. This angle is then 360/n where n is the amount of sides the polygon can have.

The two other angles in the triangle we get with two sides "r" and one side "a" is 180/n.

Ok, to find the side r expressed with a:

$$r^2 = r^2 + a^2 2ra \cos{\frac{180}{n}}$$

$$a = 2r \cos{\frac{180}{n}}$$

$$r = \frac{a}{2 \cos{\frac{180}{n}}}$$

The area of this triangle is:

$$A = \frac{1}{2} \sin{\frac{180}{n}} ar = \frac{1}{2} \sin{\frac{180}{n}} \frac{a}{2 \cos{\frac{180}{n}}} a = \frac{1}{4} \tan{\frac{180}{n}} a^2$$

The area of the whole polygon will then be the area of the triangles in the circle. I multiply with the number I divided 360 with, "n".

So: $$A_n =\frac{n}{4} a^2 \tan{\frac{180}{n}}$$

But this is wrong! Why is it wrong?

$$A_n =\frac{na^2}{4 \tan{\frac{180}{n}}}$$

Last edited: May 21, 2007
2. May 21, 2007

### Werg22

$$r^2 = r^2 + a^2 - 2ra \cos{\frac{180}{n}}$$

This is wrong. The angle is 90 - 180/n, hence giving $$r^2 = r^2 + a^2 - 2ra \sin{\frac{180}{n}}$$

Last edited: May 21, 2007
3. May 22, 2007

### uart

I've got no idea where that line came from but it looks wrong (edit: ok I now see it was supposed to be the cosine rule). You should have just used :

$$a/2 = r \sin(180/n)$$

Which gives : $$r = \frac{a}{2 \sin(180/n)}$$

Now just substitute that into :

$$A = n ( \frac{1}{2} r^2 \sin(360/n) )$$

PS. Remember to use the trig identity : $$\sin(2x) = 2 \sin(x) \cos(x)$$ if you want to get your answer in exactly the same form as the one given.

Last edited: May 22, 2007
4. May 22, 2007

### disregardthat

Yes, it was the cosine rule I meant.

Hmm, that was wierd. We are not supposed to use trigonometric identities. Or at least the book doesn't mention any of it.

5. May 22, 2007

### Werg22

Well, uart expression is equivalent to $$A = n r^2 \sin(180/n)\cos(180/n)$$

Last edited: May 22, 2007
6. May 22, 2007

### uart

You can get a perfectly good (correct) answer without even using that last trig idenity, it just wont be in the exact same form as the one given. It will be 100% equivalent but just not an identical form.

Last edited: May 22, 2007

format: plain


text:
Exercise 2 2 determining your diversity quotient

Chemical equilibrium 62 equilibrium constants (part i) at the end of the lesson, students should be able to 2so2(g) + o2(g) 2so3(g) kp = 25 x 1010 at 500k exercise - 18 calculate kp for the following equilibria: a) n2o4 deduce the expression for reaction quotient lesson duration. Is pleased to provide free access to the classic edition of the biology place to all educators and their students exercise 2: f 1 and f 2 generations analysis of results case 1 case 2 experiment 2: how to calculate leaf surface area analysis of results i lab quiz i. The difference quotient i the ability to set up and simplify difference quotients is essential for calculus students it is from the difference quotient that the elementary formulas for derivatives are developed. We are asked to determine the ph of a solution of a weak electrolyte (ch 3 cooh) and a strong sample exercise 171 calculating the ph when a common ion is involved calculate the ph of a solution containing 0085 m nitrous acid (hno 2 k.

This algebra lesson explains how to find the difference quotient. Now try exercise 7 the quotient of two algebraic expressions is a fractional expression moreover, the quotient of two polynomials such as or is a rational expression now try exercise 65 3x2 2x 6 x 3 3x 4 3x2 4x 2x 6 x 3 3x 4 x x 3 2 3x 4 x 3x 4 2 x 3 x 3 3x 4. Respiratory exchange ratio respiratory quotient (rq) report a total number of calories burned for the entire time of exercise 6 calculate the number of kilocalories burned as fat and the number burned as cho for each. Exercise 2 2 determining your diversity quotient lab exercise 2: acceleration a objective this experiment will provide data to calculate the acceleration of a marble as it rolls down an incline plane over measured periods of time.

What's your diversity quotient view all items while you can't always easily determine where these holes lie, you can become a diversity candidate by defying stereotypes and differentiating yourself from the world you come from. to determine which industries make the regional economy unique understanding location quotient 2 of 4 employment, a decline in employment or lq indicates trouble for the entire economy growing employment paired with declining lq. The respiratory exchange ratio (rer) measuring this ratio can be used for estimating the respiratory quotient (rq) can exceed 1 during intense exercise, as co 2 production by the working muscles becomes greater and more of the inhaled o 2 gets used rather than being expelled.

Exercise 2 2 determining your diversity quotient

12 writing expressions work with a partner a the quotient of 3 and a number 4p words that imply multiplication or division section 12 writing expressions 9 use what you learned about writing expressions to complete exercises 9 - 12 on page 12 work with a partner. 26 rational functions what is a rational function exercise 262 you just sketched the graph of the function $$y=\dfrac{1}{x}$$ between $$-2$$ and $$+2$$ exclusive of \ it is necessary to find the quotient of the ratio.

• To be 2 now try exercise 15 f x x create a table that shows values of f determine that as x gets closer and closer to 1, f(x) 756 chapter 11 limits and an introduction to calculus.
• Free essays on exercise 2 2 determining your diversity quotient for students use our papers to help you with yours 1 - 30.
• Exercises 27 discuss the meaning of each of the following objects: std::cin and quotient of the two numbers 217 (printing) write a program that prints the numbers 1 to 4 on the same line with each pair of adjacent numbers separated by one space.
• Tify your answer determine which of the statements in 15-20 are true and which example 423 to do exercises 21-23 indicate which propel1ies which is a quotient of two integers with a nonzero denomi.
• Abstract algebra de nition of elds is assumed throughout these notes section 31: quotient (or factor) rings 51 section 32: (integral) domains 52 exercise 25 prove that for every a g, (a 1) 1 = a.

This is an exercise in hatcher's algebraic topology: what familiar space is the quotient $\delta$-complex of a $2$-simplex $[v_0,v_1,v_2]$ obtained by identifying the edges \$[v_0,v_1] quotient of a triangle up vote 4 down vote favorite 1. 32 the factor theorem and the remainder theorem 257 to determine our answer 2 x3+4x2 5x 14 2x2 12x 14 x3 6x2 7x 0 12xand 14 came from in the second row each of these terms was obtained by multiplying the terms in the quotient, x2, 6xand 7, respectively.

Exercise 2 2 determining your diversity quotient
Rated 5/5 based on 49 review


text:
# If you wanted to compare the shoe sizes and the heights of all the students in your math class, what graph would you use?

Set out the $x$-axis to represent the height and the $y$-axis to represent the shoe size (or the other way around).


text:
FACTOID # 18: Alaska spends more money per capita on elementary and secondary education than any other state.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Wishart distribution
Parameters Probability density function Cumulative distribution function $n > 0!$ deg. of freedom (real) $mathbf{V} > 0,$ scale matrix ( pos. def) $mathbf{V}!$ is positive definite $frac{left|mathbf{W}right|^frac{n-p-1}{2}} {2^frac{np}{2}left|{mathbf V}right|^frac{n}{2}Gamma_p(frac{n}{2})} expleft(-frac{1}{2}{rm Tr}({mathbf V}^{-1}mathbf{W})right)$ nΣ $Theta mapsto left|{mathbf I} - 2i,{mathbfTheta}{mathbfSigma}right|^{-n/2}$

In statistics, the Wishart distribution, named in honor of John Wishart, is any of a family of probability distributions for nonnegative-definite matrix-valued random variables ("random matrices"). These distributions are of great importance in the estimation of covariance matrices in multivariate statistics. Please refer to Real vs. ... In linear algebra, a positive-definite matrix is a Hermitian matrix which in many ways is analogous to a positive real number. ... In mathematics, the support of a real-valued function f on a set X is sometimes defined as the subset of X on which f is nonzero. ... In mathematics, a probability density function (pdf) is a function that represents a probability distribution in terms of integrals. ... In probability theory, the cumulative distribution function (abbreviated cdf) completely describes the probability distribution of a real-valued random variable, X. For every real number x, the cdf is given by where the right-hand side represents the probability that the random variable X takes on a value less than... In probability theory the expected value (or mathematical expectation) of a random variable is the sum of the probability of each possible outcome of the experiment multiplied by its payoff (value). Thus, it represents the average amount one expects as the outcome of the random trial when identical odds are... In probability theory and statistics, a median is a number dividing the higher half of a sample, a population, or a probability distribution from the lower half. ... In, mode means the most frequent value assumed by a random variable, or occurring in a sampling of a random variable. ... In probability theory and statistics, the variance of a random variable (or somewhat more precisely, of a probability distribution) is a measure of its statistical dispersion, indicating how its possible values are spread around the expected value. ... Example of the experimental data with non-zero skewness (gravitropic response of wheat coleoptiles, 1,790) In probability theory and statistics, skewness is a measure of the asymmetry of the probability distribution of a real-valued random variable. ... The far red light has no effect on the average speed of the gravitropic reaction in wheat coleoptiles, but it changes kurtosis from platykurtic to leptokurtic (-0. ... Claude Shannon In information theory, the Shannon entropy or information entropy is a measure of the uncertainty associated with a random variable. ... In probability theory and statistics, the moment-generating function of a random variable X is wherever this expectation exists. ... In probability theory, the characteristic function of any random variable completely defines its probability distribution. ... A graph of a Normal bell curve showing statistics used in educational assessment and comparing various grading methods. ... John Wishart (28 November 1898 â€“ 14 July 1956) was a Scottish agricultural statistician. ... In mathematics and statistics, a probability distribution is a function of the probabilities of a mutually exclusive and exhaustive set of events. ... For the square matrix section, see square matrix. ... A random variable is a mathematical function that maps outcomes of random experiments to numbers. ... In multivariate statistics, the importance of the Wishart distribution stems in part from the fact that it is the probability distribution of the maximum likelihood estimator of the covariance matrix of a multivariate normal distribution. ... Multivariate statistics or multivariate statistical analysis in statistics describes a collection of procedures which involve observation and analysis of more than one statistical variable at a time. ...

Suppose X is an $ntimes p$ matrix each row of which is drawn from p-variate normal distribution with zero mean: In probability theory and statistics, a multivariate normal distribution, also sometimes called a multivariate Gaussian distribution, is a specific probability distribution, which can be thought of as a generalization to higher dimensions of the one-dimensional normal distribution (also called a Gaussian distribution). ...

$X_{(i)}{=}(x_i^1,...,x_i^p)^Tsim N_p(0,V),$

Further suppose that the rows X(1), ..., X(n) are independent. Then the Wishart distribution is the probability distribution of the p×p random matrix In mathematics and statistics, a probability distribution is a function of the probabilities of a mutually exclusive and exhaustive set of events. ...

S = XTX,

where S is known as the scatter matrix. One indicates that S has that probability distribution by writing It has been suggested that this article or section be merged into sample mean and sample covariance. ...

$Ssim W_p(V,n).$

The positive integer n is the number of degrees of freedom. Sometimes this is written W(V,p,n). This article or section is in need of attention from an expert on the subject. ...

If p = 1 and V = 1 then this distribution is a chi-square distribution with n degrees of freedom. In probability theory and statistics, the chi-square distribution (also chi-squared or Ï‡2  distribution) is one of the theoretical probability distributions most widely used in inferential statistics, i. ...

Occurrence

The Wishart distribution arises frequently in likelihood-ratio tests in multivariate statistical analysis. It also arises in the spectral theory of random matrices. A likelihood-ratio test is a statistical test relying on a test statistic computed by taking the ratio of the maximum value of the likelihood function under the constraint of the null hypothesis to the maximum with that constraint relaxed. ... In probability theory and statistics, a random matrix is a matrix-valued random variable. ...

Probability density function

The Wishart distribution can be characterized by its probability density function, as follows. In the jargon of mathematics, the statement that Property P characterizes object X means, not simply that X has property P, but that X is the only thing that has property P. It is also common to find statements such as Property Q characterises Y up to isomorphism. The first... In mathematics, a probability density function (pdf) is a function that represents a probability distribution in terms of integrals. ...

Let ${mathbf W}$ be a $ptimes p$ symmetric matrix of random variables that is positive definite. Let ${mathbf V}$ be a (fixed) positive definite matrix of size $ptimes p$. In mathematics, a definite bilinear form B is one for which B(v,v) has a fixed sign (positive or negative) when it is not 0. ...

Then, if $ngeq p$, ${mathbf W}$ has a Wishart distribution with n degrees of freedom if it has a probability density function $f_{mathbf W}$ given by In mathematics, a probability density function (pdf) is a function that represents a probability distribution in terms of integrals. ...

$f_{mathbf W}(w)= frac{ left|wright|^{(n-p-1)/2} expleft[ - {rm trace}({mathbf V}^{-1}w/2 )right] }{ 2^{np/2}left|{mathbf V}right|^{n/2}Gamma_p(n/2) }$

where $Gamma_p(cdot)$ is the multivariate gamma function defined as In mathematics, the multivariate gamma distribution , , is a generalization of the gamma function. ...

$Gamma_p(n/2)= pi^{p(p-1)/4}Pi_{j=1}^p Gammaleft[ (n+1-j)/2right].$

In fact the above definition can be extended to any real n > p − 1.

Characteristic function

The characteristic function of the Wishart distribution is Some mathematicians use the phrase characteristic function synonymously with indicator function. ...

$Theta mapsto left|{mathbf I} - 2i,{mathbfTheta}{mathbfSigma}right|^{-n/2}.$

In other words,

$Theta mapsto {mathcal E}left{mathrm{exp}left[icdotmathrm{trace}({mathbf W}{mathbfTheta})right]right} = left|{mathbf I} - 2i{mathbfTheta}{mathbfSigma}right|^{-n/2}$

where ${mathcal E}(cdot)$ denotes expectation.

Theorem

If ${mathbf W}$ has a Wishart distribution with m degrees of freedom and variance matrix ${mathbf V}$---write ${mathbf W}sim{mathbf W}_p({mathbf V},m)$---and ${mathbf C}$ is a $qtimes p$ matrix of rank q, then In linear algebra, the column rank (row rank respectively) of a matrix A with entries in some field is defined to be the maximal number of columns (rows respectively) of A which are linearly independent. ...

${mathbf C}{mathbf W}{mathbf C'} sim {mathbf W}_qleft({mathbf C}{mathbf V}{mathbf C'},mright)$

Corollary 1

If ${mathbf z}$ is a nonzero $ptimes 1$ constant vector, then ${mathbf z'}{mathbf W}{mathbf z}simsigma_z^2chi_m^2$.

In this case, $chi_m^2$ is the chi-square distribution and $sigma_z^2={mathbf z'}{mathbf V}{mathbf z}$ (note that $sigma_z^2$ is a constant; it is positive because ${mathbf V}$ is positive definite). In probability theory and statistics, the chi-square distribution (also chi-squared or Ï‡2  distribution) is one of the theoretical probability distributions most widely used in inferential statistics, i. ...

Corollary 2

Consider the case where ${mathbf z'}=(0,ldots,0,1,0,ldots,0)$ (that is, the j-th element is one and all others zero). Then corollary 1 above shows that

$w_{jj}simsigma_{jj}chi^2_m$

gives the marginal distribution of each of the elements on the matrix's diagonal.

Noted statistician George Seber points out that the Wishart distribution is not called the "multivariate chi-square distribution" because the marginal distribution of the off-diagonal elements is not chi-square. Seber prefers to reserve the term multivariate for the case when all univariate marginals belong to the same family. Multivariate statistics or multivariate statistical analysis in statistics describes a collection of procedures which involve observation and analysis of more than one statistical variable at a time. ...

Estimator of the multivariate normal distribution

The Wishart distribution is the probability distribution of the maximum-likelihood estimator (MLE) of the covariance matrix of a multivariate normal distribution. The derivation of the MLE is perhaps surprisingly subtle and elegant. It involves the spectral theorem and the reason why it can be better to view a scalar as the trace of a 1×1 matrix than as a mere scalar. See estimation of covariance matrices. In mathematics and statistics, a probability distribution is a function of the probabilities of a mutually exclusive and exhaustive set of events. ... Maximum likelihood estimation (MLE) is a popular statistical method used to make inferences about parameters of the underlying probability distribution from a given data set. ... In statistics and probability theory, the covariance matrix is a matrix of covariances between elements of a vector. ... In probability theory and statistics, a multivariate normal distribution, also sometimes called a multivariate Gaussian distribution, is a specific probability distribution, which can be thought of as a generalization to higher dimensions of the one-dimensional normal distribution (also called a Gaussian distribution). ... In mathematics, particularly linear algebra and functional analysis, the spectral theorem is any of a number of results about linear operators or about matrices. ... In linear algebra, real numbers are called scalars and relate to vectors in a vector space through the operation of scalar multiplication, in which a vector can be multiplied by a number to produce another vector. ... In multivariate statistics, the importance of the Wishart distribution stems in part from the fact that it is the probability distribution of the maximum likelihood estimator of the covariance matrix of a multivariate normal distribution. ...

Probability distributionsview  talk  edit ]
Univariate Multivariate
Discrete: BenfordBernoullibinomialBoltzmanncategoricalcompound Poisson • discrete phase-type • degenerate • Gauss-Kuzmin • geometrichypergeometriclogarithmicnegative binomialparabolic fractalPoissonRademacherSkellamuniform • Yule-Simon • zetaZipf • Zipf-Mandelbrot Ewensmultinomialmultivariate Polya
Continuous: BetaBeta primeCauchychi-squareDirac delta function • Coxian • Erlangexponentialexponential powerFfading • Fisher's z • Fisher-Tippett • Gammageneralized extreme valuegeneralized hyperbolicgeneralized inverse Gaussian • Half-Logistic • Hotelling's T-square • hyperbolic secant • hyper-exponential • hypoexponential • inverse chi-square (scaled inverse chi-square)• inverse Gaussianinverse gamma (scaled inverse gamma) • KumaraswamyLandauLaplaceLévy • Lévy skew alpha-stable • logistic • log-normal • Maxwell-Boltzmann • Maxwell speedNakagaminormal (Gaussian) • normal-gamma • normal inverse Gaussian • ParetoPearson • phase-type • polarraised cosineRayleigh • relativistic Breit-Wigner • Riceshifted Gompertz • Student's t • triangulartruncated normal • type-1 Gumbel • type-2 Gumbel • uniform • Variance-Gamma • Voigtvon MisesWeibullWigner semicircleWilks' lambda Dirichlet • inverse-Wishart • Kentmatrix normalmultivariate normalmultivariate Student • von Mises-Fisher • Wigner quasi • Wishart
Miscellaneous: Cantorconditionalequilibriumexponential familyinfinitely divisible • location-scale family • marginalmaximum entropyposteriorprior • quasi • samplingsingular

Results from FactBites:

 Wishart distribution - Wikipedia, the free encyclopedia (494 words) In statistics, the Wishart distribution, named in honor of John Wishart, is any of a family of probability distributions for nonnegative-definite matrix-valued random variables ("random matrices"). Noted statistician George Seber points out that the Wishart distribution is not called the "multivariate chi-square distribution" because the marginal distribution of the off-diagonal elements is not chi-square. The Wishart distribution is the probability distribution of the maximum-likelihood estimator (MLE) of the covariance matrix of a multivariate normal distribution.
More results at FactBites »

Share your thoughts, questions and commentary here


text:
1.6k views

Consider the following grammar

• $S \rightarrow S * E$
• $S \rightarrow E$
• $E \rightarrow F + E$
• $E \rightarrow F$
• $F \rightarrow id$

Consider the following LR(0) items corresponding to the grammar above

1. $S \rightarrow S *.E$
2. $E \rightarrow F. + E$
3. $E \rightarrow F + .E$

Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

1. i and ii
2. ii and iii
3. i and iii
4. None of the above
edited | 1.6k views

ans is D.

edited by
+14
answer is (D).. we can quickly observe here, in (i) "." is after *, that means it has just processed * input..

in (ii) "." is after F, it has just processed F.. in (iii) "." is after +.. that means it has just processed +..

So none these belong to the same canonical set of item.!! because "." comes either before all alphabet or just after the alphabet has just processed...

We don't have to draw whole list of canonical item to answer this 1 mark question.. :D
+1
your ans is right but i have a doubt in state daigram.for state i0  there will be one  production for F with follow +.

if i am wrong then correct me ...
–1
You are right @vaishali above dfa is wrong. F->id look ahead should be + also. Please correct me if I am wrong. Thank you!
+1

Just want to clarify,

1) Question is asked on the LR(0) items, so there is no need to add look ahead.

2) In the state I3, there is shift Reduce conflit , E->F.+E and E->F.

$\Rightarrow$ NOT possible for these three items to be in same state

There will be 9 sets I0 to I8

(I) will be in set I5

(II) will be in set I3

(III) will be in set I6

So (D)

Given Grammar is left Recursive.

1
2
+1 vote


text:
# How do you divide (3x^2+7x-20) / (x+4)?

Jul 30, 2015

$3 x - 5$

#### Explanation:

Hint: If you see the question carefully, you might notice that the question was intended so that you may have to factor the numerator in such a way that $x + 4$ is a factor, and gets cancelled with the denominator. Let's try doing that.

Let $N = 3 {x}^{2} + 7 x - 20$.
Note that $3 x \left(x + 4\right) = 3 {x}^{2} + 12 x$

Thus, we write:
$N = 3 {x}^{2} + 12 x - 5 x - 20 = 3 x \left(x + 4\right) - 5 \left(x + 4\right) = \left(3 x - 5\right) \left(x + 4\right)$

Now we come to the question itself
$\frac{3 {x}^{2} + 7 x - 20}{x + 4} = \frac{\left(3 x - 5\right) \cancel{\left(x + 4\right)}}{\cancel{\left(x + 4\right)}} = 3 x - 5$


text:
Minimum distance between two numbers
Basic Accuracy: 38.9% Submissions: 68592 Points: 1

You are given an array A, of N elements. Find minimum index based distance between two elements of the array, x and y.

Example 1:

Input:
N = 4
A[] = {1,2,3,2}
x = 1, y = 2
Output: 1
Explanation: x = 1 and y = 2. There are
two distances between x and y, which are
1 and 3 out of which the least is 1.

Example 2:

Input:
N = 7
A[] = {86,39,90,67,84,66,62}
x = 42, y = 12
Output: -1
Explanation: x = 42 and y = 12. We return
-1 as x and y don't exist in the array.

Complete the function minDist() which takes the array, n, x and y as input parameters and returns the minimum distance between x and y in the array. If no such distance is possible then return -1.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 <= N <= 105
0 <= A[i], x, y <= 105

We are replacing the old Disqus forum with the new Discussions section given below.

to report an issue on this page.

### Editorial

We strongly recommend solving this problem on your own before viewing its editorial. Do you still want to view the editorial?


text:
# How do I interpret the results of a log-linear regression involving constructed personality trait independent variables?

The following model was estimated:

Linear regression
Number of obs     =      1,027
F(45, 981)        =      17.85
Prob > F          =     0.0000
R-squared         =     0.4268
Root MSE          =     .46636
|               Robust
lunpaid |      Coef.   Std. Err.      t    P>|t|
ropen1 |   .0257707   .0140323     1.84   0.067
rextra1 |   .0208155   .0128139     1.62   0.105
ragree1 |   .0210167   .0175203     1.20   0.231
rcon1 |   .0494945   .0180238     2.75   0.006
rneur1 |   .0154446   .0133066     1.16   0.246

where lunpaid (the dependent variable) is equal to the log of unpaid overtime, and ropen1 - rneur1 correspond to the big 5 personality traits openness extraversion, agreeableness, conscientiousness and neuroticism. (A number of controls were included in the model however I have excluded them from the picture.) These independent variables were generated by taking an average of 3 likert measured traits from 'does not apply to me' to 'applies to me perfectly'.

   big5: forgiving nature   |      Freq.     Percent        Cum.
----------------------------+-----------------------------------
does not apply to me at all |         16        0.64        0.64
2 |         78        3.13        3.77
3 |        173        6.94       10.71
4 |        319       12.80       23.52
5 |        649       26.04       49.56
6 |        910       36.52       86.08
applies to me perfectly |        347       13.92      100.00
----------------------------+-----------------------------------
Total |      2,492      100.00

The average of forgiving nature + 2 more traits looks like this:

agree |      Freq.     Percent        Cum.
------------+-----------------------------------
2 |          3        0.04        0.04
2.333333 |         14        0.19        0.23
2.666667 |         33        0.44        0.66
3 |         78        1.03        1.70
3.333333 |         90        1.19        2.89
3.666667 |        161        2.14        5.03
4 |        233        3.09        8.12
4.333333 |        324        4.30       12.41
4.666667 |        490        6.50       18.91
5 |        675        8.95       27.86
5.333333 |        848       11.25       39.11
5.666667 |      1,117       14.81       53.93
6 |      1,304       17.29       71.22
6.333333 |      1,135       15.05       86.27
6.666667 |        554        7.35       93.62
7 |        481        6.38      100.00
------------+-----------------------------------

The age variable was then regressed on each generated personality variable and the residuals were used as the explanatory variables in the regression (in order to remove age effects).

My question is, how should I interpret the coefficients? I realise that conscientiousness is the only statistically significant result. Is this interpretation correct:

A unit increase in trait conscientiousness is associated with a 5% increase in unpaid overtime hours supplied, and this result is highly significant at the 1% level.

• Possible duplicate of Interpretation of log transformed predictor – gung Jan 11 '17 at 2:16
• Apologies for the images, I have edited my submission. I understand that the usual interpretation for a log-linear model is: "One unit increase in IV is associated with a (B1 * 100) percent increase in DV." I am wondering how this interpretation might change given how the independent variables were generated. – L.Emma Jan 11 '17 at 2:40
• I'm not sure I see how they were generated makes any difference to their interpretation. Can you say more? – gung Jan 11 '17 at 2:42
• @gung Sorry if I'm not explaining myself well. I have updated my post with one of the average of 3 traits (agreeableness) variable. I guess I'm just paranoid that using generating the variables from the likert scale changes the interpretation. I take it that this interpretation seems correct: A unit increase in trait conscientiousness is associated with a 5% increase in unpaid overtime hours supplied, and this result is highly significant at the 1% level. – L.Emma Jan 11 '17 at 12:07


text:
## 3. Other Geometric Flows

1. #### Problem 3.1.

[B. Kotschwar, J. Streets] Must two Yang-Mills self-shrinkers that are asymptotic to the conical connection be actually identical?
• #### Problem 3.2.

[L. Ni]
Let $u:S^n \to \mathbb{R}$ be a positive function satisfying $$u \cdot \det (D^2u+ug_{ij})=1,$$ where $g_{ij}$ is the round metric on $S^n$. Can one show that $u \equiv 1$?

More generally, if $u$ satisfies $$u^{\frac{1}{\alpha}} \det (D^2u+ug_{ij})=1,$$ for $\alpha > \frac{1}{n+2}$, can one show that $u \equiv 1$?

The case $\alpha =\frac 1 n$ is known to be true. The case $n=1$ or $n=2$ with $\alpha \in (\frac 1 2, 1)$ is also true. Form the point of view of geometry, $u$ is the Gauss curvature.
• #### Problem 3.3.

[J. Streets] Let $S^2$ be the 2 dimension unit sphere and $g$ be a metric on $S^2$ with positive Gauss curvature. Take $g=e^{2u} ds^2$. Consider the flow $$\partial_t u=-1+\frac{\overline{K_u}}{K_u}$$ where $\overline{K_u}$ is the average of $K_u$. Known: long time existence; some weak convergence (a priori estimate degenerate at $t=\infty$).

Question: Does the flow converge to round? (If the genus is greater than 1, the analogous flow is understood). What about higher dimensions? More information for $n=2$ can be found on the paper on arxiv.

Cite this as: AimPL: Geometric flows and Riemannian geometry, available at http://aimpl.org/flowriemannian.


text:
# Can a modified "grappling hook" be used to pull a human into melee range?

The design of this grappling hook is to fire hooks at a target at a max distance of 8 meters (~26 feet), a human for ease of calculation, pull the human to about 1 meter (~3 feet) to the person who is wielding the hook. Then the hooks can be quickly removed (under two seconds) from the human even if the human is struggling against the wielder.

Note the hooks are designed specifically for this purpose. A couple of question of the design:

1. How much force is required to fire the hooks?
2. Can the hooks ever be able to grab into an unarmored human and a human wearing kevlar armor, and not be removed until the right time?
3. Are there materials of the rope or chain withstand that amount of force?

For now we will not consider the effects of the firing force on the wielder's arm, or whether the wielder could pull the human that close. We are also not concerned about practicality. Potentially lethal force is fine, but not preferred.

• Comments are not for extended discussion; this conversation has been moved to chat. Jan 10 '18 at 21:24
• "we will not consider the effects of the firing force on the wielder's arm, or whether the wielder could pull the human that close. We are also not concerned about practicality". Undo this, and the question becomes answerable, with a resounding "no". What you are doing is saying "Assuming this impossible thing is doable, how effective is it?" The suspension of rules make the evaluation of the thing's effectivity a farce Sep 10 at 6:53

You may want to investigate in some non-aggressive alternative to harpoons.

Depending on the technological level of your world (you mentioned Kevlar, so I assume we're not in a Medieval setting) a nice alternative could be synthetic Setae that have a large adhesive force on almost all solid surfaces (Teflon being one of the few exceptions); this adhesive force can be "switched off" almost instantly by varying the incidence of the nanostructures making up the adhesive surface.

1. Force depends on speed you want to impress to your "grappling hook"; the proposed solution is quite lightweight, so you can think about something akin to pitching a baseball.
2. Yes, it would stick to almost anything, including bare skin. Excessive sweat or other oily coating could reduce considerably adhesive force. You can counteract enlarging surface (think ball inside a wet towel).
3. Force you need to express is the force needed to drag an unwilling human. You may easily have a Kevlar line strong enough and a small electrical winch, but you also need an anchor to pull your "prey" to you, otherwise you risk being dragged to him. You might want to embed some taser-like device to temporarily inhabilitate target.
• This actually fits pretty well! Good answer. Jan 8 '18 at 22:27
• This type of weapon can be easily negated if its use is expected - targets would just have to hang toilet paper as the outer shell of armor. Jan 8 '18 at 22:58
• @Alexander: true, but that would hardly withstand any serious fighting for more than a few seconds. The good thin is this grapple is reusable. Jan 8 '18 at 23:37

If you're looking for this:

But if you're just trying to see if you can pull a human into melee range using a hook... Of course you can! With enough power, you can do anything!

Let's take a look at the physics... The average weight of a human is 62kg (137lb). Given that you said melee range, I'm gonna assume that they're and they are wearing armor. We'll round them to 80kg. Now, we can start at the end. Assuming they have an embedded hook in them... Could you reel them in? Math time! We can see that, by their mass, their normal force is $9.81\frac{m}{s^2}*80kg= 784.8N$. Given a coefficient of friction of .4 (I totally fudged that number, but it's within acceptable ranges), you'd need 314N of force to pull your attacker to you on level ground. Given that you're pulling them 7 meters (As stated above) the energy you'd expend is 2198J, or about a half a food calorie. That's okay, it's small, in fact. XKCD has a delightful article on tug-of-war and related things here, which is what this ends up being. You've gotta pull with more force than your opponent AND not move, yourself.

Now, let's analyze the firing mechanism. We know that the claw mechanism needs to be able to withstand up to 1000N of force(314N *2 + some rounding to account for heavier opponents.) If we assume a relatively small 'tug' area of $15cm^2$, then we can see the pressure on the 'wound site' is 66Pa. It'll hurt, but it probably won't rip out. You could use a hook mechanism like that of a harpoon for the engage/disengage mechanism.

So... Why couldn't you just go ahead and use a harpoon?

Having read two whole scenes from Moby Dick, I recall that the harpoon was mainly used to keep ahold of the whale and to bleed it out until it died. Even though whales are much bigger than humans,Citation needed the forces at work are similar. The XKCD article I linked earlier says that the average pull force of 'elite tug-of-war players' is around 1000N (Well...actually it uses kilogram-force, but I converted it.) In other words... No matter what kind of device you're using, it's gonna be at the limit of your capability to pull your opponent to you.

Moving on to kevlar...

Kevlar vests are designed to stop bullets. A quick google says that the average force of a bullet is 304 N. Kevlar is stronger. Furthermore, any hook you might use would have a bigger cross section than a bullet. Ergo, kevlar beats harpoon.

• This is a good answer, but I have to disagree on the kevlar comment. Kevlar vests that can stop bullets are notorious for failing to stop knives, since Kevlar fibers are great at stopping blunt, high-speed, low-momentum projectiles, but not sharp, low-speed, high-momentum ones. A harpoon is probably closer to a bladed weapon than a bullet in how it interacts with armor. Jan 9 '18 at 16:31
• Interesting! I do admit, I'm not really an expert on any of this, and about a third of my physics knowledge is learned on the spot. I'll cross-validate your Kevlar claim, then update my answer when I've got time. Jan 9 '18 at 16:45
– Aify
Jan 9 '18 at 18:05

Yes; your modified grappling hook is basically a harpoon gun with a detachable tip for ease of removal.

1) Depends on the size of the harpoon

2) Yes. With regards to kevlar armor though, depends where you hit and the power of your harpoon gun.

3) Yes. Plenty, steel cable seems to work just fine. Alternatively, you can use kevlar line.

Have you ever tried to drag someone, or push him?

When you do that you notice something: it requires a lot of strength to even move him from a step, it's easier to lift him: look at nearly all riot police arrestation. They prefer to lift the guy than to drag or push him, because they don't need as much strength to proceed and he can't do much to resist.

And what you are requiring is a weapon that you could carry and use it to drag somone for over 7 meter? Even if you are way stronger than your opponent it would be a very long and hard task.

And, even if that work, what could be the purpose of such a thing? Riot police are way more effective as they are possible with today's technology. With that range there is a high chance that some people will try to pull the chain to make you release your grip.

There are so many flaws in the concept itself that there is no way it would work.

Yes, but there are ways to make it MUCH easier.

Disable the target's ability to do anything to the best of your ability Looking at real world less than lethal options, notice how its not just a single weapon, its a package of multiple different ones optimized to work alongside each other. Here, why not do the same? Depending on what equipment you have you should have this grapling hook as a part of a bigger system, consisting of different ways of incapacitating someone. Whether it be dazzlers, pepper spray or old fashioned rubber bullets, use THOSE alongside it.

It also makes whatever you will do in melee range that much easier


text:
# "The executable package.exe aborted with system error code 1073740940" in ABAQUS with the following VUMAT for crystal plasticity [closed]

I am new to crystal plasticity simulations and have been studying the concepts from "Introduction to Crystal Plasticity" in Mechanics of Microstructured Materials book. Additionally, I have been going through the publicly available UMAT for crystal plasticity (Huang 1991). I have also come across a paper titled "Comparison of the implicit and explicit finite element methods using crystal plasticity (2007)," where the authors have implemented the model in Abaqus/Explicit environment.

Though I now understand the theoretical basis of the crystal plasticity formulation, I have been unable to implement the model as a VUMAT subroutine, as carried out in the paper. I received the VUMAT file here, but when I tried to run it I got the error:

"The executable package.exe aborted with system error code 1073740940"


text:
- Current Issue - Ahead of Print Articles - All Issues - Search - Open Access - Information for Authors - Downloads - Guideline - Regulations ㆍPaper Submission ㆍPaper Reviewing ㆍPublication and Distribution - Code of Ethics - For Authors ㆍOnlilne Submission ㆍMy Manuscript - For Reviewers - For Editors
 Quasi-commutative semigroups of finite order related to Hamiltonian groups Bull. Korean Math. Soc. 2015 Vol. 52, No. 1, 239-246 https://doi.org/10.4134/BKMS.2015.52.1.239Printed January 31, 2015 Mohammad Reza Sorouhesh and Hossein Doostie Tehran Science and Research Branch Islamic Azad University, Tehran Science and Research Branch Islamic Azad University Abstract : If for every elements $x$ and $y$ of an associative algebraic structure $(S,\cdot)$ there exists a positive integer $r$ such that $ab=b^ra$, then $S$ is called quasi-commutative. Evidently, every abelian group or commutative semigroup is quasi-commutative. Also every finite Hamiltonian group that may be considered as a semigroup, is quasi-commutative however, there are quasi-commutative semigroups which are non-group and non commutative. In this paper, we provide three finitely presented non-commutative semigroups which are quasi-commutative. These are the first given concrete examples of finite semigroups of this type. Keywords : quasi-commutativity, finitely presented semigroups MSC numbers : 20M05 Downloads: Full-text PDF


text:
Guillaume Lazzara committed Mar 08, 2013 1   Guillaume Lazzara committed Mar 08, 2013 2 3 4 5   Guillaume Lazzara committed Mar 08, 2013 6 7 8 9  $projectname:$title $title  Guillaume Lazzara committed Mar 08, 2013 10   Guillaume Lazzara committed Mar 08, 2013 11 12   Guillaume Lazzara committed Mar 08, 2013 13 14 15 $treeview $search$mathjax  Guillaume Lazzara committed Mar 08, 2013 16 17  $extrastylesheet  Guillaume Lazzara committed Mar 08, 2013 18 19   Guillaume Lazzara committed Mar 08, 2013 20 21   Guillaume Lazzara committed Mar 08, 2013 22 23 24 25 26 27  Olena  Guillaume Lazzara committed Mar 08, 2013 33 $projectnumber  Guillaume Lazzara committed Mar 08, 2013 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
$projectbrief$projectbrief
 Guillaume Lazzara committed Mar 08, 2013 28   Guillaume Lazzara committed Mar 08, 2013 29 30 31 32   Guillaume Lazzara committed Mar 08, 2013 55


text:
×

# SAT Direct and Inverse Variation

If $$x$$ and $$y$$ are positive numbers and $$x$$ is directly proportional to $$\frac{1}{y}$$, which of the following is directly proportional to $$\frac{1}{x^{7}}$$?

(A) $$\ \ \frac{1}{y^{7}}$$
(B) $$\ \ \frac{1}{y}$$
(C) $$\ \ y$$
(D) $$\ \ y^{7}$$
(E) $$\ \ y^{8}$$

$$B$$ varies directly with the square of $$n$$ and the cube of $$m$$ and inversely with $$p$$. What is the value of $$B$$ if $$m=7, n=12$$, $$p=84$$, and the constant of proportionality, $$k,$$ is $$k=\frac{1}{21}$$?

(A) $$\ \ \frac{1}{12348}$$

(B) $$\ \ \frac{1}{21}$$

(C) $$\ \ \frac{12}{21}$$

(D) $$\ \ 28$$

(E) $$\ \ 588$$

In which of the following equations is $$y$$ directly proportional to $$x$$?

(A) $$\ \ y=\frac{1}{5}\cdot x^{-2}$$

(B) $$\ \ y=\frac{5}{x}$$

(C) $$\ \ y=\frac{1}{5}\cdot x$$

(D) $$\ \ y=\frac{1}{5}\cdot x^{2}$$

(E) $$\ \ y=5+2x$$

The kinetic energy of an object, $$KE$$, is directly proportional to its mass, $$m$$, and to the square of its velocity, $$v$$. If the mass is divided by $$2$$ and the velocity is multiplied by $$11$$, and if $$k$$ is a proportionality constant, which of the following does NOT represent the object's new kinetic energy, $$KE_{new}$$?

(A) $$\ \ KE_{new}=\frac{121k}{2}\cdot KE_{old}$$

(B) $$\ \ KE_{new}=\frac{121 \cdot k}{2} \cdot m \cdot v^{2}$$

(C) $$\ \ KE_{new}=k\cdot \frac{m}{2} \cdot (v \cdot 11)^{2}$$

(D) $$\ \ KE_{new}=\frac{k\cdot 11}{2} \cdot m \cdot v^{2}$$

(E) $$\ \ KE_{new}= k\cdot 11^{2} \cdot \frac{1}{2}\cdot m \cdot v^{2}$$

$$y$$ varies directly with the square of $$x,$$ and $$y=196$$ when $$x=7$$. Given $$x<0$$, what is $$x$$ when $$y=1764$$?

(A) $$\ \ -63$$
(B) $$\ \ -21$$
(C) $$\ \ 0$$
(D) $$\ \ 21$$
(E) $$\ \ 63$$

×


text:
# 3.3 Electronic structure  (Page 5/5)

 Page 5 / 5

Models are often simplified. The small toy cars that you may have played with as a child are models. They give you a good idea of what a real car looks like, but they are much smaller and much simpler. A model cannot always be absolutely accurate and it is important that we realise this so that we don't build up a false idea about something.

In groups of 4-5, you are going to build a model of an atom. Before you start, think about these questions:

• What information do I know about the structure of the atom? (e.g. what parts make it up? how big is it?)
• What materials can I use to represent these parts of the atom as accurately as I can?
• How will I put all these different parts together in my model?

As a group, share your ideas and then plan how you will build your model. Once you have built your model, discuss the following questions:

• Does our model give a good idea of what the atom actually looks like?
• In what ways is our model inaccurate ? For example, we know that electrons move around the atom's nucleus, but in your model, it might not have been possible for you to show this.
• Are there any ways in which our model could be improved?

Now look at what other groups have done. Discuss the same questions for each of the models you see and record your answers.

The following simulation allows you to build an atom
run demo

This is another simulation that allows you to build an atom. This simulation also provides a summary of what you have learnt so far.
Run demo

## Summary

• Much of what we know today about the atom, has been the result of the work of a number of scientists who have added to each other's work to give us a good understanding of atomic structure.
• Some of the important scientific contributors include J.J.Thomson (discovery of the electron, which led to the Plum Pudding Model of the atom), Ernest Rutherford (discovery that positive charge is concentrated in the centre of the atom) and Niels Bohr (the arrangement of electrons around the nucleus in energy levels).
• Because of the very small mass of atoms, their mass is measured in atomic mass units (u). $1\phantom{\rule{2pt}{0ex}}u=1,67×10{}^{-24}\phantom{\rule{2pt}{0ex}}g$ .
• An atom is made up of a central nucleus (containing protons and neutrons ), surrounded by electrons .
• The atomic number (Z) is the number of protons in an atom.
• The atomic mass number (A) is the number of protons and neutrons in the nucleus of an atom.
• The standard notation that is used to write an element, is ${}_{Z}^{A}\mathrm{X}$ , where X is the element symbol, A is the atomic mass number and Z is the atomic number.
• The isotope of a particular element is made up of atoms which have the same number of protons as the atoms in the original element, but a different number of neutrons. This means that not all atoms of an element will have the same atomic mass.
• The relative atomic mass of an element is the average mass of one atom of all the naturally occurring isotopes of a particular chemical element, expressed in atomic mass units. The relative atomic mass is written under the elements' symbol on the Periodic Table.
• The energy of electrons in an atom is quantised . Electrons occur in specific energy levels around an atom's nucleus.
• Within each energy level, an electron may move within a particular shape of orbital . An orbital defines the space in which an electron is most likely to be found. There are different orbital shapes, including s, p, d and f orbitals.
• Energy diagrams such as Aufbau diagrams are used to show the electron configuration of atoms.
• The electrons in the outermost energy level are called valence electrons .
• The electrons that are not valence electrons are called core electrons .
• Atoms whose outermost energy level is full, are less chemically reactive and therefore more stable, than those atoms whose outer energy level is not full.

## End of chapter exercises

1. Write down only the word/term for each of the following descriptions.
1. The sum of the number of protons and neutrons in an atom
2. The defined space around an atom's nucleus, where an electron is most likely to be found
2. For each of the following, say whether the statement is True or False. If it is False, re-write the statement correctly.
1. ${}_{10}^{20}\mathrm{Ne}$ and ${}_{10}^{22}\mathrm{Ne}$ each have 10 protons, 12 electrons and 12 neutrons.
2. The atomic mass of any atom of a particular element is always the same.
3. It is safer to use helium gas rather than hydrogen gas in balloons.
4. Group 1 elements readily form negative ions.
3. Multiple choice questions: In each of the following, choose the one correct answer.
1. The three basic components of an atom are:
1. protons, neutrons, and ions
2. protons, neutrons, and electrons
3. protons, neutrinos, and ions
4. protium, deuterium, and tritium
2. The charge of an atom is...
1. positive
2. neutral
3. negative
3. If Rutherford had used neutrons instead of alpha particles in his scattering experiment, the neutrons would...
1. not deflect because they have no charge
2. have deflected more often
3. have been attracted to the nucleus easily
4. have given the same results
4. Consider the isotope ${}_{92}^{234}\mathrm{U}$ . Which of the following statements is true ?
1. The element is an isotope of ${}_{94}^{234}\mathrm{Pu}$
2. The element contains 234 neutrons
3. The element has the same electron configuration as ${}_{92}^{238}\mathrm{U}$
4. The element has an atomic mass number of 92
5. The electron configuration of an atom of chlorine can be represented using the following notation:
1. ${1\mathrm{s}}^{2}{2\mathrm{s}}^{8}{3\mathrm{s}}^{7}$
2. ${1\mathrm{s}}^{2}{2\mathrm{s}}^{2}{2\mathrm{p}}^{6}{3\mathrm{s}}^{2}{3\mathrm{p}}^{5}$
3. ${1\mathrm{s}}^{2}{2\mathrm{s}}^{2}{2\mathrm{p}}^{6}{3\mathrm{s}}^{2}{3\mathrm{p}}^{6}$
4. ${1\mathrm{s}}^{2}{2\mathrm{s}}^{2}{2\mathrm{p}}^{5}$
4. Give the standard notation for the following elements:
1. beryllium
2. carbon-12
3. titanium-48
4. fluorine
5. Give the electron configurations and aufbau diagrams for the following elements:
1. aluminium
2. phosphorus
3. carbon
6. Use standard notation to represent the following elements:
1. argon
2. calcium
3. silver-107
4. bromine-79
7. For each of the following elements give the number of protons, neutrons and electrons in the element:
1. ${}_{78}^{195}\mathrm{Pt}$
2. ${}_{18}^{40}\mathrm{Ar}$
3. ${}_{27}^{59}\mathrm{Co}$
4. ${}_{3}^{7}\mathrm{Li}$
5. ${}_{5}^{11}\mathrm{B}$
8. For each of the following elements give the element or number represented by 'x':
1. ${}_{45}^{103}\mathrm{X}$
2. ${}_{x}^{35}\mathrm{Cl}$
3. ${}_{4}^{x}\mathrm{Be}$
9. Which of the following are isotopes of ${}_{12}^{24}\mathrm{Mg}$ :
1. ${}_{25}^{12}\mathrm{Mg}$
2. ${}_{12}^{26}\mathrm{Mg}$
3. ${}_{13}^{24}\mathrm{Al}$
10. If a sample contains 69% of copper-63 and 31% of copper-65, calculate the relative atomic mass of an atom in that sample.
11. Complete the following table:
 Element Electron configuration Core electrons Valence electrons Boron (B) Calcium (Ca) Silicon (Si) Lithium (Li) Neon (Ne)
12. Draw aufbau diagrams for the following elements:
1. beryllium
2. sulphur
3. argon

where we get a research paper on Nano chemistry....?
what are the products of Nano chemistry?
There are lots of products of nano chemistry... Like nano coatings.....carbon fiber.. And lots of others..
learn
Even nanotechnology is pretty much all about chemistry... Its the chemistry on quantum or atomic level
learn
da
no nanotechnology is also a part of physics and maths it requires angle formulas and some pressure regarding concepts
Bhagvanji
hey
Giriraj
Preparation and Applications of Nanomaterial for Drug Delivery
revolt
da
Application of nanotechnology in medicine
what is variations in raman spectra for nanomaterials
I only see partial conversation and what's the question here!
what about nanotechnology for water purification
please someone correct me if I'm wrong but I think one can use nanoparticles, specially silver nanoparticles for water treatment.
Damian
yes that's correct
Professor
I think
Professor
Nasa has use it in the 60's, copper as water purification in the moon travel.
Alexandre
nanocopper obvius
Alexandre
what is the stm
is there industrial application of fullrenes. What is the method to prepare fullrene on large scale.?
Rafiq
industrial application...? mmm I think on the medical side as drug carrier, but you should go deeper on your research, I may be wrong
Damian
How we are making nano material?
what is a peer
What is meant by 'nano scale'?
What is STMs full form?
LITNING
scanning tunneling microscope
Sahil
how nano science is used for hydrophobicity
Santosh
Do u think that Graphene and Fullrene fiber can be used to make Air Plane body structure the lightest and strongest. Rafiq
Rafiq
what is differents between GO and RGO?
Mahi
what is simplest way to understand the applications of nano robots used to detect the cancer affected cell of human body.? How this robot is carried to required site of body cell.? what will be the carrier material and how can be detected that correct delivery of drug is done Rafiq
Rafiq
if virus is killing to make ARTIFICIAL DNA OF GRAPHENE FOR KILLED THE VIRUS .THIS IS OUR ASSUMPTION
Anam
analytical skills graphene is prepared to kill any type viruses .
Anam
Any one who tell me about Preparation and application of Nanomaterial for drug Delivery
Hafiz
what is Nano technology ?
write examples of Nano molecule?
Bob
The nanotechnology is as new science, to scale nanometric
brayan
nanotechnology is the study, desing, synthesis, manipulation and application of materials and functional systems through control of matter at nanoscale
Damian
Is there any normative that regulates the use of silver nanoparticles?
what king of growth are you checking .?
Renato
What fields keep nano created devices from performing or assimulating ? Magnetic fields ? Are do they assimilate ?
why we need to study biomolecules, molecular biology in nanotechnology?
?
Kyle
yes I'm doing my masters in nanotechnology, we are being studying all these domains as well..
why?
what school?
Kyle
biomolecules are e building blocks of every organics and inorganic materials.
Joe
The fundamental frequency of a sonometer wire streached by a load of relative density 's'are n¹ and n² when the load is in air and completly immersed in water respectively then the lation n²/na is
Properties of longitudinal waves


text:
Universal Structure and Universal PDE for Unitary Ensembles
Open Access Publications from the University of California

Universal Structure and Universal PDE for Unitary Ensembles

• Author(s): Rumanov, Igor
• et al.

Published Web Location

https://arxiv.org/pdf/0910.4417.pdf
No data is associated with this publication.
Abstract

An attempt is made to describe random matrix ensembles with unitary invariance of measure (UE) in a unified way, using a combination of Tracy-Widom (TW) and Adler-Shiota-Van Moerbeke (ASvM) approaches to derivation of partial differential equations (PDE) for spectral gap probabilities. First, general 3-term recurrence relations for UE restricted to subsets of real line, or, in other words, for functions in the resolvent kernel, are obtained. Using them, simple universal relations between all TW dependent variables and one-dimensional Toda lattice $\tau$-functions are found. A universal system of PDE for UE is derived from previous relations, which leads also to a {\it single independent PDE} for spectral gap probability of various UE. Thus, orthogonal function bases and Toda lattice are seen at the core of correspondence of different approaches. Moreover, Toda-AKNS system provides a common structure of PDE for unitary ensembles. Interestingly, this structure can be seen in two very different forms: one arises from orthogonal functions-Toda lattice considerations, while the other comes from Schlesinger equations for isomonodromic deformations and their relation with TW equations. The simple example of Gaussian matrices most neatly exposes this structure.

Item not freely available? Link broken?
Report a problem accessing this item


text:
Lemma 18.26.2. Let $f : (\mathop{\mathit{Sh}}\nolimits (\mathcal{C}), \mathcal{O}_\mathcal {C}) \to (\mathop{\mathit{Sh}}\nolimits (\mathcal{D}), \mathcal{O}_\mathcal {D})$ be a morphism of ringed topoi. Let $\mathcal{F}$, $\mathcal{G}$ be $\mathcal{O}_\mathcal {D}$-modules. Then $f^*(\mathcal{F} \otimes _{\mathcal{O}_\mathcal {D}} \mathcal{G}) = f^*\mathcal{F} \otimes _{\mathcal{O}_\mathcal {C}} f^*\mathcal{G}$ functorially in $\mathcal{F}$, $\mathcal{G}$.

Proof. For a sheaf $\mathcal{H}$ of $\mathcal{O}_\mathcal {C}$ modules we have

\begin{align*} \mathop{\mathrm{Hom}}\nolimits _{\mathcal{O}_\mathcal {C}}( f^*(\mathcal{F} \otimes _\mathcal {O} \mathcal{G}), \mathcal{H}) & = \mathop{\mathrm{Hom}}\nolimits _{\mathcal{O}_\mathcal {D}}( \mathcal{F} \otimes _\mathcal {O} \mathcal{G}, f_*\mathcal{H}) \\ & = \text{Bilin}_{\mathcal{O}_\mathcal {D}}( \mathcal{F} \times \mathcal{G}, f_*\mathcal{H}) \\ & = \text{Bilin}_{f^{-1}\mathcal{O}_\mathcal {D}}( f^{-1}\mathcal{F} \times f^{-1}\mathcal{G}, \mathcal{H}) \\ & = \mathop{\mathrm{Hom}}\nolimits _{f^{-1}\mathcal{O}_\mathcal {D}}( f^{-1}\mathcal{F} \otimes _{f^{-1}\mathcal{O}_\mathcal {D}} f^{-1}\mathcal{G}, \mathcal{H}) \\ & = \mathop{\mathrm{Hom}}\nolimits _{\mathcal{O}_\mathcal {C}}( f^*\mathcal{F} \otimes _{f^*\mathcal{O}_\mathcal {D}} f^*\mathcal{G}, \mathcal{H}) \end{align*}

The interesting “$=$” in this sequence of equalities is the third equality. It follows from the definition and adjointness of $f_*$ and $f^{-1}$ (as discussed in previous sections) in a straightforward manner. $\square$

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the toolbar).


text:
# What We Talk About When We Talk About Distributed Systems

For quite some time now I’ve been trying to learn about distributedsystems, and it’s appropriate to say that once you start digging,there seems to be no end to it, the rabbit hole goes on and on. Theliterature in distributed systems is quite extensive, with lots ofpapers coming from different universities, plus quite a few books tochoose from. For a total beginner like me, it proved hard to decidewhat paper to read, or what book to buy.

At the same time, I’ve found that several bloggers recommend this orthat paper that one must know in order to become a distributedsystems engineer (whatever that means). So the list of things to readgrows:FLP,Zab,Time, Clocks and the Ordering of Events in a Distributed Systems,Viewstamped Replication,Paxos,Chubbyand on and on. My problem is that many times I don’t see ajustification of why I should read this or that paper. I love theidea of learning just for knowledge’s sake, to satisfy curiosity, butat the same time one needs to prioritise what to read, since the dayonly has 24hs.

Apart from the abundance of papers and research material, as mentionedabove, there are also lots books. Having bought quite a few of themand read chapters here and there, I started to see that a book thathad a promising title was quite unrelated to what I was looking for,or that the content didn’t directly target the problems I would haveliked to solve. Therefore, I would like to go over what I think arethe main concepts of distributed systems, citing papers, books orresources where one can learn about them.

As I’m continuously learning while writing these words, please havesome patience, expect some mistakes, and be aware that I will try toexpand whatever I end up writing here.

Before we start, I must tell you that I have presented this blog postat various conferences, so here are the slides if you are interested:

And here’s a video of when I presented this talk at the Erlang UserConference in Stockholm:

## Main Concepts

Distributed systems algorithms can be classified according todifferent kinds of attributes. Some classifications are: the timingmodel; the kind of interprocess communication used; the failure modelassumed for the algorithm; and many others as we will see.

Here are the main concepts we will see:

### Timing Model

Here we have the synchronous model, the asynchronous model and thepartially synchronous model.

The synchronous model is the simplest one to use; here componentstake steps simultaneously, in what are called synchronousrounds. The time for a message to be delivered is usually known, andwe also can assume the speed of each process, ie.: how long it takesfor a process to execute one step of the algorithm. The problem withthis model is that it doesn’t reflect reality so well, even less in adistributed system context, where one can send a message to anotherprocess, and wish that the stars are aligned for us, so the messagearrives to said process. The good thing is that using this model it ispossible to achieve theoretical results that later can be translatedto other models. For example, due to the guarantees of this modelabout time, we could see that if a problem cannot be solved underthese timing guarantees, then it would probably be impossible to solveonce we relax them (think of a Perfect Failure Detector for instance).

The asynchronous model gets a bit more complex. Here componentscan take steps in whatever order they choose and they don’t offer anyguarantee about the speed in which they will take such steps. Oneproblem with this model is that while it can be simple to describe andcloser to reality, it still doesn’t reflect it properly. For example,a process might take infinitely long to respond to a request, but in areal project, we would probably impose a timeout on said request, andonce the timeout expires we will abort the request. A difficulty thatcomes with this model is how to assure the liveness condition of aprocess. One of the most famous impossibility results, the“Impossibility of Consensus with one Faulty Process”belongs to this timing model, where it is not possible to detect if aprocess has crashed, or if the process is just taking an infinitely longtime to reply to a message.

In the partially synchronous model, components have someinformation about timing, having access to almost synchronised clocks,or they might have approximations of how long messages take to bedelivered, or how long it takes a processes to execute a step.

The bookDistributed Algorithmsby Nancy Lynch is actually organised in sections based on these timingmodels.

### Interprocess Communication

Here we need to think about how processes in the system exchangeinformation. They can do it by sending messages to each other, in themessage passing model, or by using the shared memory model,where they share data by accessing shared variables.

One thing to keep in mind is that we can use a message passingalgorithm to build a distributed shared memory object. A common examplein books is the implementation of a read/write register. We also havequeues and stacks, which are used by some authors to describeconsistency properties, likelinearizabilty. Weshould not confuse shared memory as a way to share data betweenprocesses by accessing a shared variable with shared memoryabstractions built on top of message passing, like the ones justmentioned.

Back to the message passing model, we have another abstraction toconsider when trying to understand algorithms: the kind of link usedbetween processes (think of channels used to send messages back andforth between processes). These links will offer certain guarantees tothe algorithm using them. For example there’s the Perfect Linksabstraction that has reliable delivery and sends no duplicates; thisabstraction also assures exactly once delivery. We can easily see thatthis abstraction doesn’t reflect the real world either, thereforethere are other kinds of link abstractions used by algorithm designerswhen they try to design models that are closer to real systems. Keepin mind that even if the Perfect Links abstraction is not so real,it can still be useful, for example if we can prove a problem is notpossible to solve even assuming perfect links, then we know of a wholebunch of related problems which might not be solvable as well. On thetopic of links authors usually consider or assume FIFO messageordering, like inZab

### Failure Modes

I already wrote an article aboutfailure modes in distributed systemsbut it is worth reiterating here. A property of a distributed systemmodel is what kind of process failures are assumed. On thecrash-stop failure mode, a process is assumed to be correct until itcrashes. Once it crashes, it never recovers. There’s also thecrash-recovery model, where processes can recover after a fault, inthis case, some algorithms also include a way for the process torecover the state it had before before crashing. This can be doneeither by reading from persistent storage or by communicating withother processes in a group. It’s worth noting that for some groupmembership algorithms, a process that crashes and then recovers couldnot be considered as the same process that was alive before. Thisusually depends if we have dynamic groups or fixed groups.

There are also failure modes where processes fail to receive or sendmessages, these are called omission failure modes. There aredifferent kind of omissions as well, a process can fail to receive amessage, or to send a message. Why does this matter? Imagine thescenario where a group of processes implement a distributed cache. Ifa process is failing to reply to requests from other processes on thegroup, even though it is able to receive requests from them, that processwill still have its state up to date, which means it can reply to readrequests from clients.

A more complex failure mode is the one called Byzantine or arbitraryfailures mode, where processes can send wrong information to theirpeers; they can impersonate processes; reply to other process with thecorrect data, but garble its local database contents, and more.

When thinking about the design of a system, we should consider whichkind of process failures we want to cope with. Birman (seeGuide to Reliable Distributed Systems)argues that usually we don’t need to cope with Byzantine failures. Hecites work done at Yahoo! where they concluded that crash failures areway more common than Byzantine failures.

### Failure Detectors

Depending on the process failure mode and timing assumptions we canconstruct abstractions that take care of reporting to the system if aprocess has crashed, or if it is suspected to have crashed. There arePerfect Failure detectors that never give a false positive. Having acrash-stop failure mode plus a synchronous system, we can implementthis algorithm by just using timeouts. If we ask processes toperiodically ping back to the Failure Detector Process, we knowexactly when a ping should arrive to the failure detector (due to thesynchronous model guarantees). If the ping doesn’t arrive after acertain configurable timeout, then we can assume the other node hascrashed.

On a more realistic system, it might not be possible to always assumethe time needed for a message to reach its destination, or how longit will take for a process to execute a step. In this case we can havea failure detector p that would report a process q as suspectedif q doesn’t reply after a timeout of N milliseconds. If q laterreplies, then p will remove q from the list of suspectedprocesses, and it will increase N, since it doesn’t know what theactual network delay between itself and q is, but it wants to stopsuspecting q of having crashed, since q was alive, as it tooklonger than N to ping back. If at some point q crashes,then p will first suspect it has crashed, and it will never reviseits judgement (since q will never ping back). A better descriptionof this algorithm can be found inIntroduction to Reliable and Secure Distributed Programmingunder the name “Eventually Perfect Failure Detector”.

Failure Detectors usually offer two properties: completeness andaccuracy. For the Eventually Perfect Failure Detector type, we havethe following:

• Strong Completeness: Eventually, every process that crashes ispermanently suspected by every correct process.
• Eventual Strong Accuracy: Eventually, no correct process issuspected by any correct process.

Failure detectors have been crucial in solving consensus in theasynchronous model. There’s a quite famous impossibility resultpresented in theFLPpaper mentioned above. This paper talks about the impossibility ofconsensus in asynchronous distributed systems where one process mightfail. One way to go around this impossibility result is to introduce afailure detector that cancircumvent the problem.

Related to the problem of failure detectors is that of actually doingthe opposite, to determine which process hasn’t crashed and istherefore working properly. This process will then be trusted by otherpeers in the network and it will be considered as the leader that cancoordinate some distributed actions. This is the case of protocolslike Raft orZab thatdepend on a leader to coordinate actions.

Having a leader in a protocol introduces asymmetry between nodes,since non-leader nodes will then be followers. This will have theconsequence that the leader node will end up being a bottleneck formany operations, so depending on the problem we are trying to solve,using a protocol that requires leader election might not be what wewant. Note that most protocols that achieve consistency via some sortof consensus use a leader process and a set of followers. SeePaxos,Zab orRaft for some examples.

### Consensus

The consensus or agreement problem was first introduced in the paperReaching Agreement in the Presence of Faultsby Pease, Shostak and Lamport. There they introduced the problem likethis:

Fault-tolerant systems often require a means by which independent processors or processes can arrive at an exact mutual agreement of some kind. It may be necessary, for example, for the processors of a redundant system to synchronise their internal clocks periodically. Or they may have to settle upon a value of a time-varying input sensor that gives each of them a slightly different reading.

So consensus is a problem of reaching agreement among independentprocesses. These processes will propose some values for a certainproblem, like what’s the current reading of their sensor, and thenagree on a common action based on the proposed values. For example, acar might have various sensors providing it with information about thebreaks temperature levels. These readings might have some variationsdepending on the precision of each sensor and so on, but the ABScomputer needs to agree on how much pressure it should apply on thebreaks. That’s a consensus problem being solved in our everyday lives.The bookFault-Tolerant Real-Time Systemsexplains consensus and other problems in distributed systems in thecontext of the automotive industry.

A process that implements some form of consensus works via exposing anAPI with propose and decide functions. A process will proposea certain value when consensus starts and then it will have to decide ona value, based on the values that were proposed in the system. Thesealgorithms must satisfy certain properties, which are: Termination,Validity, Integrity and Agreement. For example for Regular Consensuswe have:

• Termination: Every correct process eventually decides some value.
• Validity: If a process decides v, then v was proposed by someprocess.
• Integrity: No process decides twice.
• Agreement: No two correct processes decide differently.

For more details on consensus please consult the original papermentioned above. Also the following books are a great reference:

### Quorums

Quorums are a tool used for designing fault-tolerant distributedsystems. Quorums refer to intersecting sets of processes that can beused to understand the characteristic of a sytem when some processesmight fail.

For example if we have an algorithm where N processes have crash-failuremodes, we have a quorum of processes whenever we have a majority ofprocesses applying certain operation to the system, for example awrite to the database. If a minority of process might crash, that isN/2 - 1 process crashes, we still have a majority of processes thatknow about the last operation applied to the system. For exampleRaft uses majorities when committing logs to the system. The leaderwill apply an entry to its state machine as soon as half the serversin the cluster have replied to its request of log replication. Theleader plus half the servers constitute a majority. This has theadvantage that Raft doesn’t need to wait for the whole cluster to replyto a log-replication RPC request.

Another example would be: let’s say we want to limit the access to ashared resource by one process at a time. This resource is guarded bya set S of processes. Whenever process p wants to access theresource it needs to first ask permission to a majority of theprocesses S guarding the resource. A majority of processes in Sgrant access to the resource to p. Now process q arrives into thesystem and tries to access the shared resource. No matter whichprocesses it contacts in S, q will never arrive to a majority ofprocesses that will grant it access to the shared resource until theresource is freed by p. SeeThe Load, Capacity, and Availability of Quorum Systemsfor more details.

Quorums don’t always refer to a majority of processes. Sometimes theyeven need more processes to form a quorum for an operation to succeed,like in the case of a group N processes that can suffer Byzantinefailures. In this case if f is the number of tolerated processfailures, a quorum will be a set of more than (N + f) / 2 processesSeeIntroduction to Reliable and Secure Distributed Programming.

If you are interested in this topic, there’s a whole book dedicated toquorums in distributed systems:

Quorum Systems: With Applications to Storage and Consensus

### Time in Distributed Systems

Understanding time and its consequences is one of the biggest problemsin distributed systems. We are used to the concept of events in ourlife happening one after the other, with a perfectly definedhappened beforeorder, but when we have a series of distributed processes, exchangingmessages, accessing resources concurrently, and so on, how can we tellwhich process event happened before? To be able to answer these kindsof questions, processes would need to share a synchronised clock, andknow exactly how long it takes for electrons to move around thenetwork; for CPUs to schedule tasks, and so on. Clearly this is notquite possible on a real-world system.

The seminal paper that discusses these issues is calledTime, Clocks, and the Ordering of Events in a Distributed Systemwhich introduced the concept of logical clocks. Logical Clocks are away of assigning a number to an event in the system; said numbers arenot related to the actual passage of time, but to the processing ofevents by a node in a distributed system.

There are many kinds of logical clocks algorithms, likeVector ClocksorInterval Tree Clocks.

For a very interesting discussion on time in distributed systems Irecommend reading the articleThere Is No Now byJustin Sheehy.

I would claim that time and its problems in distributed systems isone of the crucial concepts to understand. The idea of simultaneityis something we have to let go. This is related with the old beliefof “Absolute Knowledge”, where we used to think that such a thing asabsolute knowledge was attainable. The laws of physics show us thateven light requires some time in order to get from one place toanother, so whenever it reaches our eyes, and it’s processed by ourbrains, whatever the light is communicating, it’s an old view of theworld. This idea is discussed by Umberto Eco in the bookInventing the Enemy,chapter “Absolute and Relative”.

## A Quick look at FLP

To finalize this article, let’s take a quick look at theImpossibility of Distributed Consensus with One Faulty Processpaper to try to relate the concepts we have just learned aboutdistributed systems.

The abstract starts like this:

The consensus problem involves an asynchronous system of processes, some of which may be unreliable.

So we have an asynchronous system, where no timing assumptions aremade, either on processing speed or the time required for messages toreach other processes. We also know that some of these process maycrash.

The issue here is that in usual technical jargon,asynchronous mightrefer to a way of processing requests, like RPC for example, where aprocess p sends an asynchronous request to process q, and whileq is processing the request, p keeps doing other things, that is:p doesn’t block waiting for a reply. We can see that this definitionis completely different from the one used in the distributed systemsliterature, so without having this knowledge, it’s quite hard to fullyunderstand the meaning of just the first sentence of the FLP paper.

Later in the paper they say:

In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume that the message system is reliable—it delivers all messages correctly and exactly once.

So the paper only considers the crash-stop failure mode discussedabove (sometimes called fail-stop). We can also see that there are no omission failures, since themessage system is reliable.

And finally they also add this constraint:

Finally, we do not postulate the ability to detect the death of a process, so it is impossible for one process to tell whether another has died (stopped entirely) or is just running very slowly.

So we can’t use failure detectors either.

To recap, this means that the FLP impossibility applies for asynchronoussystems with fail-stop processors, with access to a reliable messagesystem, and where detecting the death of a process is notpossible. Without knowing the theory related to the different modelsof distributed systems, it might be possible that we miss many ofthese details, or we just interpret them in a totally different wayfrom what the authors meant.

For a more detailed overview of FLP please take a look at this blogpost:A Brief Tour of FLP Impossibility

Also, it is interesting to read the paperStumbling over Consensus Research: Misunderstandings and Issuesby Marcos Aguilera, which has a discussion about what it means for FLPto be an impossibility result for distributed systems (spoileralert: is not the same level of impossibility as the haltingproblem).

## Conclusion

As you can see, learning about distributed systems takes time. It’s avery vast topic, with tons of research on each of its sub-areas. Atthe same time implementing and verifying distributed systems is alsoquite complex. There are many subtle places where to commit mistakescan make our implementations totally broken under unexpectedcircumstances.

What if we choose the wrong quorum and then our new fancy replicationalgorithm loses critical data? Or we choose a very conservative quorumthat slows down our application without need, making us break SLAswith customers? What if the problem we are trying to solve doesn’tneed consensus at all and we can live with eventual consistency?Perhaps our system has the wrong timing assumptions? Or it uses afailure detector unfit for the underlying system properties? What ifwe decide to optimise an algorithm like Raft, by avoiding a small stephere or there and we end up breaking its safety guarantees? All thesethings and many more can happen if we don’t understand the underlyingtheory of distributed systems.

OK, I get it, I won’t reinvent the distributed systems wheel, but withsuch vast literature and set of problems, where to start, then? Asstated at the top of this article, I think randomly reading papers willget you nowhere, as shown with the FLP paper, where understanding thefirst sentence requires you to know about the various timingmodels. Therefore I recommend the following books in order to getstarted:

Distributed Algorithmsby Nancy Lynch. This book is kinda the bible of distributedsystems. It covers the various models cited above, having sectionswith algorithms for each of them.

Introduction to Reliable and Secure Distributed Programmingby Christian Cachin et al. Besides from being a very goodintroduction, it covers many kinds of consensus algorithms. The bookis full of pseudo-code explaining the algorithms which is a good thingto have.

Of course there are many more books, but I think these two are a goodstart. If you feel you need to diver deeper, here’s the list ofresources used in this article:

## References

posted @ 2015-12-15 10:25  leoncfor  阅读(310)  评论(0编辑  收藏  举报