April 2007 IBM Ponder This Challenge

[pzhon]

Many reading this forum may like this month's Ponder This challenge from IBM, which can be viewed as a probability problem:
<ul type="square">
This month's puzzle concerns a frog who is hopping on the integers from minus infinity to plus infinity. Each hop is chosen at random (with equal probability) to be either +2 or -1. So the frog will make steady but irregular progress in the positive direction. The frog will hit some integers more than once and miss others entirely. What fraction of the integers will the frog miss entirely? Please find an exact answer.[/list]

[neverforgetlol]

Someone who's good at stochastic processes might figure it out

[f97tosc]

We can reformulate the problem to the question "what is the probability that the frog will not eventually land on 0, assuming it starts from minus infinity?".

Given that the frog is in n, denote the probability that it will eventually reach 0 as P(n).

Then generally

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

or equivalently

P(n+3)-2P(n+1)+P(n)=0

This is a difference equation with the characteristic equation

r^3-2r+1=0

This has the solutions (guess the first root, factor it out, and solve for the
others)

r1=1
r2=-1/2 + sqrt(5)/2
r3=-1/2 - sqrt(5)/2

Now P(n)=C1*r1^n + C2*r2^n + C3*r3^n

Where C1, C2, and C3 are constants.

We can determine the constants from edge conditions. However, the edge conditions are different for n&gt;0 and n&lt;0, and so we will consider them separately, starting with n&gt;0.

For n&gt;0, C3 has to be zero, since r3 is negative and has the largest absolute value; otherwise we would evetually get negative probabilities.

Similarly, since |r2|&lt;1, but r1=1 and P(inf)=0, we must have that C1=0. Finally, the edge condition P(0)=1 gives us C2=1.

Hence, for n&gt;0, P(n)= (-1/2+sqrt(5)/2)^n, and specifically, P(1)=-1/2+sqrt(5)/2


Now for n&lt;=1, we have the same characteristic equation, but different edge conditions, and different constants as follows:

P(n)=D1*r1^n + D2*r2^n + D3*r3^n

r1,r2, and r3 are the same as for the n&gt;0 case. Since |r2|&lt;1, the second term would make the probability &gt;1 for sufficiently low n,and so D2=0.

This time we have the edge conditions P(0)=1, and P(1)= -1/2+sqrt(5)/2, which we determined in the n&gt;1 case.

Putting these together we have

P(0)=D1 +D3 =1
P(10= D1 + (-1/2 -sqrt(5)/2)*D3 = -1/2 + sqrt(5)/2.

This is two linear equations for two unknowns, which can be solved for
D1 = 2 sqrt(5)/(3+sqrt(5))

As stated in the beginning, we seek

1-P(-infty)=

=1-D1

=1- 2 sqrt(5)/(3+sqrt(5))

=(7-3sqrt(5))/2 ~= 0.146

[lastcardcharlie]

Just to be pedantic (it's late), "minus infinity" and "plus infinity" are not integers.

[alThor]

This problem (and your solution) remind me of the risk-of-ruin problems with integer payoffs. Such problems have been solved, e.g. when you lose one unit or win k units (2 in this case).

So one can also view the problem this way: consider the first time you "pass" any integer (say zero). There is a 50% chance that you hit it, and a 50% chance you jumped over it. If you jumped over it (and landed on one), you can ask the ROR question where you start with a bankroll of one unit, and are playing a game where you lose one or win two. Then,

P(hit zero) = .5 + .5*(ROR)

Solving the ROR uses the same style of difference equations you did, so this isn't really far from your answer; just making an observation on the connection.

[f97tosc]

This was actually how I started to think about the problem but after I solved for "ROR" I realized that I don't think it is true that you initially "pass" the integer with 50% chance. And indeed, when I solved for the approach side as well, the answer I got was different. Of course I could have made an error somewhere when solving those equations, but I am quite skeptical of the 50% pass claim now.

[jason1990]

I get a different answer. Let S_n be the position of the frog, with S_0 = 0. Let A(k) be the event that the frog eventually visits site k, and let I(k) = 1 if A(k) occurs and 0 otherwise. Define

R_L = (2L)^{-1}\sum_{k=-L}^L I(k).

Technically, we must prove that this converges almost surely as L goes to infinity, and calculate the limit. Let us first take expectations:

ER_L = (2L)^{-1}\sum_{k=-L}^L P(A(k)).

For k &gt; 0, let t(k) be the first time S_n hits -k, and let s(k) be the first time S_n hits or passes k. Because of the upward drift, S_n goes to infinity almost surely. Hence, s(k) is finite with probability one, but there is a positive probability that t(k) is infinity. Define

q_k := P(A(-k)) = P(t(k) finite)
p_k := P(S_{s(k)} = k + 1).

Note that p_k is the probability that the frog passes k on the way up. Hence, by the Markov property,

P(A(k)) = (1 - p_k) + p_k q_1.

We therefore have

(*) ER_L = (2L)^{-1}[1 + \sum_{k=1}^L q_k
+ \sum_{k=1}^L (1 - p_k + q_1 p_k)].

Now to compute q_k and p_k. Let f = (-1 + \sqrt{5})/2 = 0.618, and define M_n = f^{S_n}. It is easy to check that M_n is a martingale. By standard methods (using optional sampling and dominated convergence), this shows that q_k = f^k.

For p_k, note that

p_1 = 1/2 + (1/2)p_2
p_2 = (1/2)p_3
p_n = (1/2)p_{n-2} + (1/2)p_{n+1}, for n &gt; 2.

If we define p_0 = 0 and p_{-1} = 1, then we have

p_{n+1} = 2p_n - p_{n-2}, for n &gt; 0.

The general solution to this recurrence is

p_n = c_1 + c_2 f^{-n} + c_3 (-f)^n.

Since each p_n is a probability (and thus between 0 and 1), we must have c_2 = 0. Using p_0 = 0 and p_{-1} = 1, we get c_1 = f^2 and c_3 = -f^2. Hence,

p_n = f^2 + (-1)^{n+1} f^{n+2}.

(Note that this implies the limiting passing probability is f^2 = 0.382.) Finally, using (*), we get

lim ER_L = (1/2)(1 - f^2 + q_1 f^2)
= (1/2)(1 - f^2 + f^3)
= (-5 + 3\sqrt{5})/4 = 0.427.

Some additional argument is now required to show that R_L converges almost surely to this limit. I suspect this can be done using straightforward estimates on the covariances of the I(k)'s.

[f97tosc]

Hmmm... maybe your approach is right but I think the answer is wrong... we can bound the answer as follows.

Define
P1 = P(frog never passes 0)
P2 = P(frog never passes 1)
P3 = P(frog passes first 1, then 0)

Since these are mutually exclusive, we have P1+P2+P3&lt;=1.

Also by symmetry, P1=P2.

Furthermore, P3&gt;P1, because these two together form the event that the frog hasn't stopped at 0 when it first reaches 1, and if this happens, the frog is more likely (&gt;50%) to eventually go back to 0 as in P3, than to never go back to 0, as in P1.

Then 1 &gt;= P1+P2+P3 &gt; 3 P1

P1&lt;1/3

Hence, at the very most 1/3 of integers can be skipped.

[fnord_too]

Post deleted by fnord_too - brain fart

[fnord_too]

I think this may be solvable the following way:
At some point you will will be 1 or 2 away from every number on the low side (i.e. before you pass or hit any number you will be exactly one or two less than it). For each of these two equally likely occurences there are sequences that land you on the exact number. So you should be able to take both of these starting conditions for an arbitrary number and determine the chance of hitting that number.

For instance, consider 2. At some point you are on 0 or 1 (each equally likely, I can prove that if necessary).

From zero, there are several ways to hit 2, but they are grouped around the number of actions, so:
1 action F - 50%
4 Actions BBFF, BFFB, BFBF 18.75%
8 Actions I think is the next
and so on.

Intuitively, I think this forms a nice managable infinite series, and there is a similar one for starting 1 away. Solve both of those and average the P's and that is the answer. It would take me a long time to get into the right mindset to crunch through that, but I think it is a good approach.