A Random Walk

By Stephen Laverack on Thursday, September 26, 2002 - 08:40 pm:

Spin a fair coin. Take one pace forward if it lands on heads and one pace back if lands on tails. Continue this "game". What is the probability that (eventually) you will return to your starting point?

By Andre Rzym on Friday, September 27, 2002 - 10:41 pm:

Stephen:

If you want to post your computations I'll happily try to see what paths you might have missed. I'm not sure the limit of this sum is easy to compute (you may need something called the Reflection Principle to get it working) but it can definitely be done (I've done a more general form of this problem before by 'counting paths' and it was a long proof). Here's a nice way to solve your problem:

Suppose we are distance $k$ (i.e. $k$ paces) from the origin (starting point). Suppose the coin may be biased: probability $p$ for heads (one pace forwards) $q = 1 - p$ for tails (one pace back). Define $P_{k}$ as the probability of returning to the origin when you are currently $k$ steps from the origin. Note that $P_{k}$ is independent of how many tosses you have made to date.

Now from $k$ , a coin toss moves us to $k - 1$ or $k + 1$ with probabilities $q$ , $p$ respectively; and where the probability of returning to the origin from there is $P_{k - 1}$ , $P_{k + 1}$ respectively. Therefore:

$P_{k} = q P_{k - 1} + p P_{k + 1}$ How do we solve this? Guess a solution of the form $P_{k} = A λ^{k}$ . Substituting:

$A λ^{k} = q A λ^{k - 1} + p A λ^{k + 1}$ $λ = q + p λ^{2}$

This is just a quadratic with roots $λ = 1$ , $q / p$ . Our solution

$P_{k} = A + B (q / p)^{k}$

has to match boundary conditions $P_{0} = 1$ , $P_{k \to \infty} = 0$ . Assuming $q / p < 1$ this implies $A = 0$ , $B = 1$ . For $q / p = 1$ , we can just consider the limit as $q / p \to 1$ , i.e. 1. Probabilities cannot be $> 1$ , and therefore the result is the same for $q / p > 1$ .

In conclusion, if we are 1 step away from the origin:

$P_{1} = q / p$ if $q / p < 1$

$P_{1} = 1$ if $q / p = 1$

$P_{1} = 1$ if $q / p > 1$

Andre

By Stephen Laverack on Sunday, September 29, 2002 - 09:21 pm:

Well, here's my method - please be gentle!
Call my start point O and successive points to the right A, B, C, D, E .....
With 2 spins there is 1 route (OAO)
With 4 spins there is 1 route (OABAO)
With 6 spins there are 2 routes (OABCBAO, OABABAO)
With 8 spins there are 4 routes (OABCDCBAO, OABCBCBAO, OABCBABAO, OABABABAO)
With 10 spins I labouriously found 8 routes (1 if E is my end point, 3 if D is my end point, 3 if C is my end point and 1 if B is my end point).
And then I decided the pattern continued as powers of 2, fitting with Pascal's Triangle (is this my mistake?)
Sum these answers to give:
(1/4)+(1/16)+(1/32)+(1/64)+ .....
And you can see the (1/8) term is missing so the sum is not (1/2) it is (3/8). So by symmetry the final answer is 2x(3/8) = (3/4).

Stephen

By Andre Rzym on Monday, September 30, 2002 - 08:26 pm:

Stephen,

This is a perfectly valid approach which, if pursued, should lead to the answer we found above.

I think you have missed out a few paths. I see the pattern as (t=2 means 2 spins etc.):

t=2 : 1 way to return to origin (we agree)
t=4 : 1 way to return to origin (we agree)
t=6 : 2 ways to return to origin (we agree)
t=8 : 5 ways to return to origin (I think you have left out OABABCBAO)
t=10 : 14 ways to return to origin

The easiest way to generate these numbers is to build a Pascal triangle-like table, and focus, instead, on the number of ways to get to a given point without having touched O. So in column ?O? we just have zeros. How many ways can we get to B at time t? It is the sum of 2*(number of ways of getting to B at t-2) [because we could then either toss heads then tails or tails then heads] and (number of ways of getting to D at t-2) [because we could then toss tails then tails]. How many ways can we get to D [the same argument applying to F,H etc] at time t? It is the sum of (number of ways of getting to B at t-2) [because we could then toss heads then heads] and 2*(number of ways of getting to D at t-2) [because we could then either toss heads then tails or tails then heads] and (number of ways of getting to F at t-2) [because we could then toss tails then tails]

This generates a triangle as follows [I have included moves on both sides of the origin, labelling them -B,-D etc]

	-H	-F	-D	-B	O	B	D	F	H
t=0					1
t=2				1	0	1
t=4			1	2	0	2	1
t=6		1	4	5	0	5	4	1
t=8	1	6	14	14	0	14	14	6	1

Thus, for example, at t=8 there are 14 paths to D without returning to the origin along the way [computed as 14=5+2*4+1]

Now, if we are to arrive at O for the first time at t (assuming the first move was forwards), necessarily we must have been at B at t-2 and subsequently tossed tails, tails. Therefore, reading from the above table, we see that the number of ways of touching the origin for the first time is (1),1,2,5,14... Therefore the probability of returning to the origin is at least

2*(1/4+1/16+2/64+5/256+14/1024)=0.753

If you are interested, you could try to guess the formulae for elements in the table above [Hint: Try subtracting the above triangle from rows 1,3,5 etc of the normal Pascals triangle. You might recognise what is left ...]

Andre

By Stephen Laverack on Monday, September 30, 2002 - 10:05 pm:

Andre

Oh no I can't count!!

Many thanks for your patient help and explanations.
Now for the three dimensional version!! (roll a die and move in one of 6 directions)

Stephen