Challenge: unpredictable walk?

Question

Let an 'unpredictable walk' denote a path of unit steps from (0,0), where for each step a random direction is chosen uniformly from 2π radians.

Let P(n,d) denote the probability that we end up within a distance of d from (0,0) after n 'unpredictable' steps. Also let Q(n,r) denote the probability that all steps of an 'unpredictable walk' of length n lies within a circle of radius r centered at the origin. Clearly P(n,n) = Q(n,n) = 1.

Can you determine P(n,d) and Q(n,r) for any d or r between 0 and n?

Anonymous · Accepted Answer

Just an observation that there is a simple formula for the expected squared distance. Let R[n] be the distance from the origin after n hops (so R[0]=0, R[1]=1, and so on).  At the end of each step n, it suffices to relocate to the x-axis a distance R[n] from the origin.  Let theta be the random angle chosen next, assumed to be independent of R[n].  Then:

R[n+1]^2 
= (R[n] + cos(theta))^2 + sin(theta)^2
= R[n]^2 + 2R[n]cos(theta) + 1

Taking expectations of both sides gives: 
E[R[n+1]^2] = E[R[n]^2] + 1

So E[R[n]^2] = n for n in {0, 1, 2, 3, …}

****
The general problem seems messy:  Let p(n,x) be the x-derivative of P(n,x).  Then:

p(n+1,y) = int p(n,x)g(x,y)dx

where g(x,y) is the derivative with respect to y of: 
Pr[R[n+1] <= y | R[n]=x] 
= Pr[R[n+1]^2 <= y^2 | R[n]=x]
= Pr[x^2 + 2xcos(theta) + 1 <= y^2] 
= Pr[cos(theta) <= (y^2 - 1 - x^2)/(2x)]
where theta is uniform over [0, 2pi] (and so the g(x,y) function 
in principle is computable).

Also, p(1,y) = delta(y-1), being an impulse function at y=1. 
So p(2,y), p(3,y), and so on, are obtained by successive integration 
with the g(x,y) function.

Heaven Convergence · Answer

P(n,d) = Ïd^2 / (Ïn^2) = d^2 / n^2
Q(n,r) = 2Ïr / (2Ïn) = r / n

? · Answer

Am I the only one who has no clue what any of this is talking about?

Trending News

Challenge: unpredictable walk?

3 Answers