Question

Write a simulation of zombies/walkers that move ra

0 0
Add a comment Improve this question Transcribed image text
Answer #1

Let N steps of equal length be taken along a line. Let p be the probability of taking a step to the right, q the probability of taking a step to the left, n_1 the number of steps taken to the right, and n_2 the number of steps taken to the left. The quantities p, q, n_1, n_2, and N are related by

p+q=

(1)

and

n_1+n_2=N.

(2)

Now examine the probability of taking exactly n_1 steps out of N to the right. There are (N; n_1)=(n_1+n_2; n_1) ways of taking n_1 steps to the right and n_2 to the left, where (n; m) is a binomial coefficient. The probability of taking a particular ordered sequence of n_1 and n_2 steps is p^(n_1)q^(n_2). Therefore,

P(n_1)=((n_1+n_2)!)/(n_1!n_2!)p^(n_1)q^(n_2)=(N!)/(n_1!(N-n_1)!)p^(n_1)q^(N-n_1),

(3)

where n! is a factorial. But this is simply a binomial distribution, so the mean number of steps n_1 to the right is

<n_1>=pN,

(4)

and the mean number of steps to the left is

<n_2>=N-<n_1>=N(1-p)=qN.

(5)

Similarly, the variance is given by

sigma_(n_1)^2=<n_1^2>-<n_1>^2=Npq,

(6)

and the root-mean-square deviation is

sigma_(n_1)=sqrt(Npq).

(7)

RandomWalkBiased

Consider now the distribution of the distances d_N traveled after a given number of steps,

d_N=n_1-n_2=2n_1-N,

(8)

as opposed to the number of steps in a given direction. The above plots show d_N(p) for N=200 and three values p=0.1, p=0.5, and p=0.9, respectively. Clearly, weighting the steps toward one direction or the other influences the overall trend, but there is still a great deal of random scatter, as emphasized by the plot below, which shows three random walks all with p=0.5.

RandomWalk

Surprisingly, the most probable number of sign changes in a walk is 0, followed by 1, then 2, etc.

For a random walk with p=1/2, the probability P_N(d) of traveling a given distance d after N steps is given in the following table.

steps 5 -4 -3 2 -1 0 1 2 3 4 5
0 1
1 1/2 0 1/2
2 1/4 0 2/4 0 1/4
3 1/8 0 3/8 0 3/8 0 1/8
4 1/(16) 0 4/(16) 0 16 0 16 0 1/(16)
5 32 0 5/(32) 0 (10)/(32) 0 (10)/(32) 0 32 0 32

In this table, subsequent rows are found by adding half of each cell in a given row to each of the two cells diagonally below it. In fact, it is simply Pascal's triangle padded with intervening zeros and with each row multiplied by an additional factor of 1/2. The coefficients in this triangle are given by

P_N(d)=1/(2^N)(N; (d+N)/2)

(9)

(Papoulis 1984, p. 291). The moments

mu_p=sum_(d=-N,-(N-2),...,N)d^pP_N(d)

(10)

of this distribution of signed distances are then given by

mu = 0

(11)

mu_2 = N

(12)

mu_3 = 0

(13)

mu_4 = N(3N-2),

(14)

so the mean is mu=0, the skewness is gamma_1=0, and the kurtosis excess is

gamma_2=-2/N.

(15)

The expectation value of the absolute distance after N steps is therefore given by

<d_N> = sum_(d=-N,-(N-2),...)^(N)|d|P_N(d)

(16)

= 1/(2^N)sum_(d=-N,-(N-2),...)^(N)(|d|N!)/(((N+d)/2)!((N-d)/2)!).

(17)

This sum can be done symbolically by separately considering the cases N even and N odd. First, consider even N so that N=2J. Then

<d_(2J)> = (N!)/(2^N)[sum_(d=-2J,; -2(J-1),...)^(-2)(|d|)/(((2J+d)/2)!((2J-d)/2)!)+0+sum_(d=2,4,...)^(2J)(|d|)/(((2J+d)/2)!((2J-d)/2)!)]

(18)

= N! 2 dl 2 dl d=-J-U-1) d= 12 ( 2

(19)

= (N!)/(2^N)[2sum_(d=1)^(J)(2d)/((J+d)!(J-d)!)]

(20)

= (N!)/(2^(N-2))sum_(d=1)^(J)d/((J+d)!(J-d)!).

(21)

But this sum can be evaluated analytically as

sum_(d=1)^Jd/((J+d)!(J-d)!)=1/(2Gamma(J)Gamma(1+J)).

(22)

Writing J=N/2, plugging back in, and simplifying gives

<d_(N even)>=2/(sqrt(pi))(Gamma(1/2+1/2N))/(Gamma(1/2N))=((N-1)!!)/((N-2)!!),

(23)

where N!! is the double factorial.

Now consider N odd, so N=2J-1. Then

<d_(N odd)> = <d_(2J-1)>

(24)

= (N!)/(2^N)[sum_(d=-(2J-1),; -(2J+1),...)^(-1)(|d|)/(((2J-1+d)/2)!((2J-1-d)/2)!)+sum_(d=1,3,...)^(2J-1)(|d|)/(((2J-1+d)/2)!((2J-1-d)/2)!)]

(25)

= (N!)/(2^(N-1))[sum_(d=1,3,...)^(2J-1)d/(((2J-1+d)/2)!((2J-1-d)/2)!)]

(26)

= (N!)/(2^(N-1))[sum_(d=2,4,...)^(2J)(d-1)/(((2J-2+d)/2)!((2J-d)/2)!)]

(27)

= (N!)/(2^(N-1))[sum_(d=1)^(J)(2d-1)/((J+d-1)!(J-d)!)].

(28)

But this sum can be evaluated analytically as

sum_(d=1)^J(2d-1)/((J+d-1)!(J-d)!)=1/([Gamma(J)]^2).

(29)

Writing J=(N+1) /2, plugging back in, and simplifying gives

(dv odd) = (N!)/(2^(N-1)[Gamma(1/2+1/2N)]^2)

(30)

= 2/(sqrt(pi))(Gamma(1/2N+1))/(Gamma(1/2N+1/2))

(31)

= (N!!)/((N-1)!!).

(32)

Both the even and odd solutions can be written in terms of J as

<d_J>=2/(sqrt(pi))(Gamma(J+1/2))/(Gamma(J))=((2J-1)!!)/((2J-2)!!),

(33)

or explicitly in terms of N as

<d_N> = 2^(1-n)[n/2](n; [n/2])

(34)

= {((N-1)!!)/((N-2)!!) for N even; (N!!)/((N-1)!!) for N odd.

(35)

The first few values of <d_N> for N=0, 1, ... are therefore 0, 1, 1, 3/2, 3/2, 15/8, 15/8, 35/16, 35/16, ... (OEIS A086116 and A060818; Abramowitz and Stegun 1972, Pr

Add a comment
Answer #1

Let N steps of equal length be taken along a line. Let p be the probability of taking a step to the right, q the probability of taking a step to the left, n_1 the number of steps taken to the right, and n_2 the number of steps taken to the left. The quantities p, q, n_1, n_2, and N are related by

p+q=

(1)

and

n_1+n_2=N.

(2)

Now examine the probability of taking exactly n_1 steps out of N to the right. There are (N; n_1)=(n_1+n_2; n_1) ways of taking n_1 steps to the right and n_2 to the left, where (n; m) is a binomial coefficient. The probability of taking a particular ordered sequence of n_1 and n_2 steps is p^(n_1)q^(n_2). Therefore,

P(n_1)=((n_1+n_2)!)/(n_1!n_2!)p^(n_1)q^(n_2)=(N!)/(n_1!(N-n_1)!)p^(n_1)q^(N-n_1),

(3)

where n! is a factorial. But this is simply a binomial distribution, so the mean number of steps n_1 to the right is

<n_1>=pN,

(4)

and the mean number of steps to the left is

<n_2>=N-<n_1>=N(1-p)=qN.

(5)

Similarly, the variance is given by

sigma_(n_1)^2=<n_1^2>-<n_1>^2=Npq,

(6)

and the root-mean-square deviation is

sigma_(n_1)=sqrt(Npq).

(7)

RandomWalkBiased

Consider now the distribution of the distances d_N traveled after a given number of steps,

d_N=n_1-n_2=2n_1-N,

(8)

as opposed to the number of steps in a given direction. The above plots show d_N(p) for N=200 and three values p=0.1, p=0.5, and p=0.9, respectively. Clearly, weighting the steps toward one direction or the other influences the overall trend, but there is still a great deal of random scatter, as emphasized by the plot below, which shows three random walks all with p=0.5.

RandomWalk

Surprisingly, the most probable number of sign changes in a walk is 0, followed by 1, then 2, etc.

For a random walk with p=1/2, the probability P_N(d) of traveling a given distance d after N steps is given in the following table.

steps 5 -4 -3 2 -1 0 1 2 3 4 5
0 1
1 1/2 0 1/2
2 1/4 0 2/4 0 1/4
3 1/8 0 3/8 0 3/8 0 1/8
4 1/(16) 0 4/(16) 0 16 0 16 0 1/(16)
5 32 0 5/(32) 0 (10)/(32) 0 (10)/(32) 0 32 0 32

In this table, subsequent rows are found by adding half of each cell in a given row to each of the two cells diagonally below it. In fact, it is simply Pascal's triangle padded with intervening zeros and with each row multiplied by an additional factor of 1/2. The coefficients in this triangle are given by

P_N(d)=1/(2^N)(N; (d+N)/2)

(9)

(Papoulis 1984, p. 291). The moments

mu_p=sum_(d=-N,-(N-2),...,N)d^pP_N(d)

(10)

of this distribution of signed distances are then given by

mu = 0

(11)

mu_2 = N

(12)

mu_3 = 0

(13)

mu_4 = N(3N-2),

(14)

so the mean is mu=0, the skewness is gamma_1=0, and the kurtosis excess is

gamma_2=-2/N.

(15)

The expectation value of the absolute distance after N steps is therefore given by

<d_N> = sum_(d=-N,-(N-2),...)^(N)|d|P_N(d)

(16)

= 1/(2^N)sum_(d=-N,-(N-2),...)^(N)(|d|N!)/(((N+d)/2)!((N-d)/2)!).

(17)

This sum can be done symbolically by separately considering the cases N even and N odd. First, consider even N so that N=2J. Then

<d_(2J)> = (N!)/(2^N)[sum_(d=-2J,; -2(J-1),...)^(-2)(|d|)/(((2J+d)/2)!((2J-d)/2)!)+0+sum_(d=2,4,...)^(2J)(|d|)/(((2J+d)/2)!((2J-d)/2)!)]

(18)

= N! 2 dl 2 dl d=-J-U-1) d= 12 ( 2

(19)

= (N!)/(2^N)[2sum_(d=1)^(J)(2d)/((J+d)!(J-d)!)]

(20)

= (N!)/(2^(N-2))sum_(d=1)^(J)d/((J+d)!(J-d)!).

(21)

But this sum can be evaluated analytically as

sum_(d=1)^Jd/((J+d)!(J-d)!)=1/(2Gamma(J)Gamma(1+J)).

(22)

Writing J=N/2, plugging back in, and simplifying gives

<d_(N even)>=2/(sqrt(pi))(Gamma(1/2+1/2N))/(Gamma(1/2N))=((N-1)!!)/((N-2)!!),

(23)

where N!! is the double factorial.

Now consider N odd, so N=2J-1. Then

<d_(N odd)> = <d_(2J-1)>

(24)

= (N!)/(2^N)[sum_(d=-(2J-1),; -(2J+1),...)^(-1)(|d|)/(((2J-1+d)/2)!((2J-1-d)/2)!)+sum_(d=1,3,...)^(2J-1)(|d|)/(((2J-1+d)/2)!((2J-1-d)/2)!)]

(25)

= (N!)/(2^(N-1))[sum_(d=1,3,...)^(2J-1)d/(((2J-1+d)/2)!((2J-1-d)/2)!)]

(26)

= (N!)/(2^(N-1))[sum_(d=2,4,...)^(2J)(d-1)/(((2J-2+d)/2)!((2J-d)/2)!)]

(27)

= (N!)/(2^(N-1))[sum_(d=1)^(J)(2d-1)/((J+d-1)!(J-d)!)].

(28)

But this sum can be evaluated analytically as

sum_(d=1)^J(2d-1)/((J+d-1)!(J-d)!)=1/([Gamma(J)]^2).

(29)

Writing J=(N+1) /2, plugging back in, and simplifying gives

(dv odd) = (N!)/(2^(N-1)[Gamma(1/2+1/2N)]^2)

(30)

= 2/(sqrt(pi))(Gamma(1/2N+1))/(Gamma(1/2N+1/2))

(31)

= (N!!)/((N-1)!!).

(32)

Both the even and odd solutions can be written in terms of J as

<d_J>=2/(sqrt(pi))(Gamma(J+1/2))/(Gamma(J))=((2J-1)!!)/((2J-2)!!),

(33)

or explicitly in terms of N as

<d_N> = 2^(1-n)[n/2](n; [n/2])

(34)

= {((N-1)!!)/((N-2)!!) for N even; (N!!)/((N-1)!!) for N odd.

(35)

The first few values of <d_N> for N=0, 1, ... are therefore 0, 1, 1, 3/2, 3/2, 15/8, 15/8, 35/16, 35/16, ... (OEIS A086116 and A060818; Abramowitz and Stegun 1972, Pr

Add a comment
Know the answer?
Add Answer to:
Write a simulation of zombies/walkers that move randomly in one dimension. Each walker begins at the...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT