Octodad Tries To Walk Straight

[gavinksong]

(This puzzle is based off of a student-created problem on an exam for an undergraduate Intro to Discrete Mathematics course at UC Berkeley)

Octodad has trouble walking straight. When he takes a step, he moves one yard in any random direction.

He decides to try and practice moving around on an xy-coordinate plane. If he starts at the origin, what will be the mean and standard deviation of his distance from the origin after taking a large number of steps?

[bonanova]

Let the walk begin at the origin of the complex plane and proceed with unit steps in an arbitrary direction.

Each step is s_j = e^{i theta_j}, where theta_j is uniformly taken from [0, 2pi).

The position on the complex plane after N steps is z_N = Sum_(j=1,N) s_j.

Because the steps have random phase the position has a mean value of zero.

<z_N> = 0.

 

To deal with real distances d we take the square of the norm of the (complex) displacement.

d_N² =   z_Nz_N* where * denotes complex conjugate.

d_N² = (Sum_(j=1,N) e^{i theta_j}) (Sum_(k=1,N) e^{-i theta_k}) = Sum of jk individual terms.

 

The individual terms have unit magnitude and random phase, except for the N instances when j=k and the phase is zero. A random walk of N unit steps in the x-y plane thus has an expected squared distance of N units.
<d_N²>= N.

 

The rms distance after N steps is N^1/2.
<d_N²>^1/2 = N^1/2.

 

The first two moments of the two dimensional random walk are 0 and N.

To understand how the first moment can be zero, consider the coordinates x_i, y_i that result from a random walk of N steps. Average these coordinates over many such random walks. Since negative and positive values are equally likely, one sees that the means are both zero.

 

However, if a positive result is desired, the rms value provides it.

[bonanova]

Define his walk. Is his azimuth not limited to vertical or horizontal steps?

 

[spoiler='I think it does not matter']1. Since the direction of each step is random, the mean distance traveled is zero.

 

2. Since the mean is zero, the standard deviation and rms (root mean square) of the distance

for large number of steps are the same, and equal to N^0.5 yards, where N is the number of yard-steps taken.

To travel a distance s yards requires s² steps.

[gavinksong]

Define his walk. Is his azimuth not limited to vertical or horizontal steps?

]1. Since the direction of each step is random, the mean distance traveled is zero.

2. Since the mean is zero, the standard deviation and rms (root mean square) of the distance

for large number of steps are the same, and equal to N^0.5 yards, where N is the number of yard-steps taken.

To travel a distance s yards requires s² steps.

Are you sure about that, bonanova?

If his mean distance is zero, that would mean that he is 100% likely to end up at the origin every time, since distance cannot be negative.

As for your question, I octodad is limited to moving around only on the xy-plane, but he may move in any direction (not just horizontally or vertically).

Cheers

[bonanova]

I meant to say his mean displacement from the origin (a vector quantity) is zero.

But that's not what you asked.

[gavinksong]

Let the walk begin at the origin of the complex plane and proceed with unit steps in an arbitrary direction.

Each step is s_j = e^{i theta_j}, where theta_j is uniformly taken from [0, 2pi).

The position on the complex plane after N steps is z_N = Sum_(j=1,N) s_j.

Because the steps have random phase the position has a mean value of zero.

<z_N> = 0.

To deal with real distances d we take the square of the norm of the (complex) displacement.

d_N² = z_Nz_N* where * denotes complex conjugate.

d_N² = (Sum_(j=1,N) e^{i theta_j}) (Sum_(k=1,N) e^{-i theta_k}) = Sum of jk individual terms.

The individual terms have unit magnitude and random phase, except for the N instances when j=k and the phase is zero. A random walk of N unit steps in the x-y plane thus has an expected squared distance of N units.

<d_N²>= N.

The rms distance after N steps is N^1/2.

<d_N²>^1/2 = N^1/2.

The first two moments of the two dimensional random walk are 0 and N.

To understand how the first moment can be zero, consider the coordinates x_i, y_i that result from a random walk of N steps. Average these coordinates over many such random walks. Since negative and positive values are equally likely, one sees that the means are both zero.

However, if a positive result is desired, the rms value provides it.

To be honest, I don't know the actual solution to this problem. It was a bonus problem on an exam, but I never got the exam back.

Your answer makes sense, bonanova. My reasoning is that as Octodad moves farther away from the origin, his chances of moving back toward the origin decreases, but stays strictly greater than 50%. To see this visually, you can draw a circle around the origin whose radius is the distance between Octodad and the origin, draw a unit circle around Octodad, and shade in the area of the unit circle that is within the larger circle. Thus, it makes sense that the mean distance would increase with N, but eventually begin flattening out with higher values of N.

Do you care to try and solve for the standard deviation, or is that too much?

[gavinksong]

I meant to say that Octodad's chances of moving

away from the origin decrease but remain strictly greater than 50% as he is father away from the origin.

[bonanova]

Well the standard deviation is just the rms deviation from the mean.
Since the mean is zero, I guess the standard deviation is also N^1/2.

[bonanova]

I meant to say that Octodad's chances of moving

away from the origin decrease but remain strictly greater than 50% as he is father away from the origin.

 

Exactly right.

 

Even though:

 

His steps are memoryless. Kind of like me these days.

At each step he does not know (a) where he is or (b) how he got there.

Or at least if he knows, it does not affect his next step. Like a coin toss.

At every point, his remaining walk is the same as the start of a new walk.

 

Nevertheless:

 

His expected total distance from the start does increase as he takes more steps.

Considering all his available steps, more than half of them increase his distance from the start.

On a circle, more than half of the 360-degree directions are outside the circle.