# random walk probability problem

• Apr 26th 2008, 09:39 AM
jjmclell
random walk probability problem
Hi, I'm working through some math ecology stuff and I'm trying to understand how the author comes up with the following:

The author claims that this Bernouilli distribution:

$\displaystyle p(m,n) = ({1 \over 2})^n {n! \over ((n + m)/2)! ((n - m)/2)!}$

converges to this Gaussian distribution when n approaches infinity:

$\displaystyle \lim_{n \to \infty} p(m,n) = (2/{\pi}n)^{1/2}exp(-m^2/2n)$

Does anybody know why that would be? The probability is for a particle arriving at point m on a number line after n moves.

jjmclell
• Apr 26th 2008, 10:25 AM
CaptainBlack
Quote:

Originally Posted by jjmclell
Hi, I'm working through some math ecology stuff and I'm trying to understand how the author comes up with the following:

The author claims that this Bernouilli distribution:

$\displaystyle p(m,n) = ({1 \over 2})^n {n! \over ((n + m)/2)! ((n - m)/2)!}$

This is not the Bernoulli distribution that I nor my references know. Please provide some context.

Quote:

Does anybody know why that would be? The probability is for a particle arriving at point m on a number line after n moves.

In the case of 0,1 steps with propabilities 1/2, 1/2 the distribution of distance from start after n steps is ~Binomial(1/2,n),
This is the sum of n RV's each with known mean and variance, and the central limit theorem then gives the asymtotic distribution of distance as normal with appropriate mean and variance. This is a Bernoulli process with p=1/2.

RonL
• Apr 26th 2008, 11:48 AM
jjmclell
That Bernoulli distribution was derived as follows:

You start at 0 on a number line, and for each step you can go one interval to the left or to the right. To reach any point, $\displaystyle m$, in $\displaystyle n$ steps, you have to take $\displaystyle a$ steps to the right and $\displaystyle b$ steps to the left. With that said:

$\displaystyle a + b = n$
$\displaystyle a - b = m$

Through substitution:

$\displaystyle a = (n + m)/2$
$\displaystyle b = (n - m)/2$

The total number of possible paths by which to arrive at $\displaystyle m$ in $\displaystyle n$ steps is:

$\displaystyle {n! \over a!b!} = {n! \over ((n + m)/2)!((n - m)/2)!}$

If we want to get to any point, $\displaystyle m$, in $\displaystyle n$ moves, then we know how many moves we must take to the right, $\displaystyle a$, and how many to the left, $\displaystyle b$. If $\displaystyle a$ represents successes and $\displaystyle b$ represents failures then:

$\displaystyle p(m,n) = ({1 \over 2})^a ({1 \over 2})^b {n!\over a!b!}$

Which equals:

$\displaystyle ({1 \over 2})^n {n! \over ((n + m)/2)!((n - m)/2)!}$

To reiterate my question, how is it that the distribution above can go from being a Bernoulli distribution to a Gaussian distribution as $\displaystyle n$ approaches infinity?...assuming that the above distribution is in fact a Bernoulli distribution and I'm not completely wrong about everything I just said.
• Apr 26th 2008, 11:56 AM
CaptainBlack
Quote:

Originally Posted by jjmclell
That Bernoulli distribution was derived as follows:

You start at 0 on a number line, and for each step you can go one interval to the left or to the right. To reach any point, $\displaystyle m$, in $\displaystyle n$ steps, you have to take $\displaystyle a$ steps to the right and $\displaystyle b$ steps to the left. With that said:

$\displaystyle a + b = n$
$\displaystyle a - b = m$

Through substitution:

$\displaystyle a = (n + m)/2$
$\displaystyle b = (n - m)/2$

The total number of possible paths by which to arrive at $\displaystyle m$ in $\displaystyle n$ steps is:

$\displaystyle {n! \over a!b!} = {n! \over ((n + m)/2)!((n - m)/2)!}$

If we want to get to any point, $\displaystyle m$, in $\displaystyle n$ moves, then we know how many moves we must take to the right, $\displaystyle a$, and how many to the left, $\displaystyle b$. If $\displaystyle a$ represents successes and $\displaystyle b$ represents failures then:

$\displaystyle p(m,n) = ({1 \over 2})^a ({1 \over 2})^b {n!\over a!b!}$

Which equals:

$\displaystyle ({1 \over 2})^n {n! \over ((n + m)/2)!((n - m)/2)!}$

To reiterate my question, how is it that the distribution above can go from being a Bernoulli distribution to a Gaussian distribution as $\displaystyle n$ approaches infinity?...assuming that the above distribution is in fact a Bernoulli distribution and I'm not completely wrong about everything I just said.

The position after n steps is the sum of n independent identically distributed RV's taking the values -1 and +1 with probabilities 1/2 ans 1/2.

Then the central limit theorem does the rest.

This is essentially what I said before.

In more detail the mean for the change on a single step is 0, and the variance is 1. So the sum of n such RV's has asymtotic distribution N(0,n). You are not expected to provide a proof of the special case of the CLT (at least I presume not).

RonL
• Apr 26th 2008, 12:08 PM
jjmclell
Thanks a lot......definitely wish I had paid more attention in stats class.