Problem 11 Solution

Think of this problem instead as one of a random walk along a number line. Let 0 be the starting point, p be the probability of moving to the right, and q be the probability of moving to the left.

Let B=probability of ever moving one to the left from where you are.

Let A=probability of revisiting current square from the right.

B = q + Aq + A²q + A³q + ... = q/(1-A).

A=pB --> B=A/p --> B=A/(1-q).

q/(1-A) = A/(1-q) --> A=q,1-q.

However, A must be less than or equal to both p and q, thus the reasonable solution is A=min(q,1-q).

Redo the above only reverse the words left and right and A will still equal min(q,1-q). One ramification of this is that the probability of revisiting 0 is the same from both the left as the right. This stands to reason since any path has a mirror image on the other side of equal probability. So the answer is 2*min(q,1-q). Where I am a little uncomfortable is dismissing the other solution of A. I believe I can do so but can not put into words why.

Below are the results of computer trials which have verified the answer above. For each probability p 100,000 trials were conducted, in which a trial ended when either the number of heads equalled the number of tails, or the difference was more than 25. It seems reasonable to assume that for p<=.4 if the difference ever equals 25 it is very unlikely that the gap ever be closed. A 'win' means the number of heads was ever equal to the number of tails. The number of losses would be 100,000 minus the number of wins.

  p    wins 
-----  ------
 0.4   80058
 0.3   59799
 0.2   39957
 0.1   19803

Thanks to Guy de Kindler for providing the problem and Richard Tucker for the solution.

Michael Shackleford, A.S.A.

MathProblems.info home