Ray's Random Walk

So, I was thinking about just how good Sam and Ray can do by simply taking the random strategy. Sam always guesses the right answer and Ray simply guesses randomly. Its easy to see that this strategy has at least 50% chance to work, since you might just get the first one right and quit (of course the argument about just repeating the strategy n times to make $n fails, but whatever). So I started to wonder, the probability of at some point getting to $1 within the first k steps is lower than 1 and can not decrease as k goes upward. Thus in the limit as k goes to infinity it must converge to some real number, what real number does it converge to?

I suppose I could post it as a logic problem, but I'd rather just work out the solution right now, as its actually sort of tricky. Also I'm not 100% about my proof anyway, so maybe somebody can point out to me a flaw or something.

First, lets reformulate the problem:

Consider a random walk on the integers, starting at 0. At each step, we have a 1/2 chance to move up one step from n to n+1 and a 1/2 chance to move down 2 steps from n to n-2. What is the probability that we ever reach 1?

If you are concerned about the ambiguity of the term "ever reach", then define f(k) to be the probability of reaching 1 within the first k steps (well defined, nondecreasing, and bounded above by 1). Now ask what is the limit of f(k) as k tends to infinity.

Suppose we let P(n) represent the probability of ever reaching point n, we are interested in P(1) given that P(0)=1. Notice that P(n) will obey the relation:

P(n)=1/2P(n-1)+1/2P(n+2)

Its not so easy to prove that statement rigorously (I'm not even confident I know how to), but it is intuitive to say that to be at n, you came in from n-1 or n+2.

Next we must define the 'derivative' function:

d(n)=P(n+1)-P(n)

Then, we can rearrange our earlier equation to

P(n)-P(n-1)=P(n+2)-P(n)
d(n-1)=d(n)+d(n+1)

d(n) seems to obey some sort of "reverse Fibonacci" relationship, d(n) is determined as the sum of d(n+1) and d(n+2). Equivalently, and in a way that makes more sense:

d(n+1)=d(n-1)-d(n)

So, it is clear d(n) would be uniquely determined by any initial two values. There is a clean relationship you can use to find d(n) given d(0) and d(1) (similar to the one for the Fibonacci Squence in terms of the golden ratio), I will give an outline of the derivation.

Define a vector D(n) by [d(n+1),d(n)]. Then D(n+1)=A D(n), where A is the matrix [[-1,1],[1,0]]. You can diagonalize A into UTU^-1, so that D(n)=AⁿD(0)=UTⁿU^-1D(0). Tⁿ is easy to calculate, as T is diagonal.

This will give you a relationship of d(n) in terms of d(1) and d(0). The golden ratio φ will show up everywhere (φ=(sqrt(5)+1)/2 and obeys φ=1+1/φ).

We can lock down d(0) and d(1) by using the boundary conditions. It is clear that P(n) must be a non-increasing function for n>0, because in order to reach 5, you must pass through 4 first, so P(5) cannot be greater than P(4). This means that P(n) must converge to some number as n tends to infinity. This guarantees that d(n), as the difference of successive P(n) terms, must converge to zero.

If one has been following along with the math and actually found the exact expression for d(n) (its not very pretty, so I didn't want to illustrate it), you find that it has terms of φⁿ and φ^-n. The condition d(n) converges to zero as n tends to infinity guarantees that the coefficient of φⁿ must vanish, giving us d(1)=d(0)/φ, and cleans up the relationship to

d(n)=d(0)/φⁿ

Now we must only lock down d(0). We know that P(n) is the sum of the first n d(i) values plus P(0) (which is 1). But this sum is an easy geometric sum:

P(n)=1+d(0)(1-φ^-n)/(φ -1)
=1+d(0)φ(1-φ^-n)

So, as n tends to infinity, P(n) tends to 1+d(0)φ. It seemed pretty self-evident to me that P(n) either tends to zero or one, but I have found a pretty convincing argument for zero.

After the first N steps, you will have moved right a spaces and left 2*(N-a) spaces (a is a number between 0 and N). You have ended on space 3a-2N, and this is clearly positive if a>2N/3. The probability of any particular value of a is (N choose a)/2^N. The probability of ending to the right of zero is the sum of that as a goes from 2N/3 to N. This is the sum of the right third of the Nth row of Pascals triangle, divided be the sum of the whole Nth row. This will tend to zero as N tends to infinity (as the right third and the left third are equal in size, but the middle third is always bigger, eventually much bigger).

From this, I would conclude that P(n) tends to zero as n tends to infinity (not rigorous mind you, but I'm convinced). This guarantees that d(0) is -φ^-1 and so:

P(n)=φ^-n for n>0

Note that we needed the argument that P(n) is nondecreasing as we go to infinity, which fails for n<0, so I don't know what the behavior is there. In conclusion, if you use the random strategy in the Sam and Ray problem to try to get $n, it will work with probability φ^-n.