April 2007 IBM Ponder This Challenge

[jason1990]

I think I see a connection. Let Y be your answer (0.146) and let M be my answer (0.427). Then M = (1 - Y)/2.

I claim to have calculated M = the fraction of all the integers that the frog will eventually HIT. I see I misread the original problem on the IBM website. So my answer should be 1 - M = 0.573 = the fraction of all the integers that the frog will eventually MISS.

You have calculated Y = the probability, starting at 0, that the frog misses state k, for k near +infinity. Hence, Y is the fraction of states above his starting point that he will miss. However, since he will reach a bounded minimum, the fraction of states below his starting point that he will miss is 1. So the fraction of all the integers that he will miss is 0.5 + Y/2 = 1 - M.

[f97tosc]

Yeah good point, I think the discrepancy boils down to exactly how the frog starts off its epic journey, and that wasn't exactly well defined in the problem statement.

The answer 1-M = 0.5+Y/2 (using your notation here) essentially assumes, as you write, that there (a.s.) exist some lowest integer below which all integers are missed.

But the problem statement says that the frog "is hopping on the integers from minus infinity". So I think that, loosely speaking, rather than thinking of the frog as starting off at some particular integer, we can say that there is no point below which the frog hasn't been when he reaches 0. That is, every point can be treated as k, again using your notation. And then Y is the answer.

[jason1990]

I agree that the initial conditions in the problem are ambiguous. I interpreted the statement "hopping on the integers from minus infinity to plus infinity" as "hopping on the integers, with no a priori restriction as to how negative or how positive his location can become."

How would we rigorously define a stochastic process which models this frog's movements and which starts at -infinity? We could try to take this literally, and add a point at infinity to the integers. But then, what is the distribution of the frog's first jump? He must eventually make a first jump to a finite integer. After that initial jump, there will be a lowest integer below which all integers are missed.

Or we could try to take some limiting procedure, by considering a sequence of processes where he starts at x, and let x go to -infinity. But again, for each fixed process in the sequence, there will be a lowest integer below which all integers are missed. If his starting point is any fixed integer, or even any integer-valued random variable, then the answer will be 1 - M. So I cannot see how we could take a limit in any reasonable way and get Y.

In fact, this reminds me a bit of the martingale betting system. Any reasonable limiting procedure shows that it is a disaster, whereas naively "starting at infinity" seems to show that it is a goldmine.

[f97tosc]

[ QUOTE ]
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

[/ QUOTE ]

I think you need to distinguish between on the one hand eventually being 1 or 2 below, and on the other hand reaching 1 below without having first reached 2 below (or vice versa).

For eventually reaching 1 or 2 below, then potentially both can happen, so I don't think that is what you mean.

On the other hand, if you mean reaching 1 below without having first reached 2 below, or vice versa, then it is not obvious, in fact I think it is false, that they are equally likely.

[fnord_too]

[ QUOTE ]
[ QUOTE ]
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

[/ QUOTE ]

I think you need to distinguish between on the one hand eventually being 1 or 2 below, and on the other hand reaching 1 below without having first reached 2 below (or vice versa).

For eventually reaching 1 or 2 below, then potentially both can happen, so I don't think that is what you mean.

On the other hand, if you mean reaching 1 below without having first reached 2 below, or vice versa, then it is not obvious, in fact I think it is false, that they are equally likely.

[/ QUOTE ]

I do mean the one you arive at first. Let me see if I can prove it.

For any integer k, prove that ariving at k-1 before k-2 has the same probability as ariving at k-2 before k-1.

Assume one can arrive at k-1 first more often than you can arive at k-2 first. Then, for (k+1) one arrives at (k+1)-2 more often than you are ariving at (k+1)-1, which is a contradicion. Ergo P(K-1) <= P(K-2).

Ok, getting rid of that '<' is not trivial. I need to think about this some more.

[alThor]

[ QUOTE ]
On the other hand, if you mean reaching 1 below without having first reached 2 below, or vice versa, then it is not obvious, in fact I think it is false, that they are equally likely.

[/ QUOTE ]

Upon reconsideration, I think you're right, which throws off my ROR solution above.

What confuses me, however, is the fact that we satisfy 1-M = 0.5+Y/2 in the two solutions posted.

The solution for "Y" makes sense to me, and I consider that to be the answer to the "right" question (i.e. the best well-defined question one can form based on the wording, starting at zero and only looking forward).

However the equation (1-M) = 0.5 + 0.5Y assumes that "half" the integers are below zero (or any arbitrary lower bound), while half are above. What confuses me is that the "percentage of integers that are below zero" isn't well defined. (E.g. One can map the odd positives into all the negatives, and thereby "prove" that two thirds of the integers are positive.)

So how did the solution for M happen to satisfy 1-M = 0.5+Y/2? The solution for M must have had a hidden assumption that half the integers are negative?

[Siegmund]

I came at it yet another slightly different way... and ran into an infinite series I couldn't add up, but it happens to agree exactly with the difference equation solution posted here. As a result, I now have one of the more bizarre combinatorics results I have ever seen.

Let's begin by considering another question: what is the probability that the frog will ever return to the square on which he is currently standing?

He can get there after 3 jumps, RLL LRL or LLR, with probability 3/8.

He can get there after 6 jumps, Rx2 and Lx4, 15 ways out of 64, but 3x3 of these paths repeat the 3-jump patterns twice, and only 6 are new ways.

In general, (3k choose k) ways to return after 3k jumps, but only 2/(3k-1) of these are "new".

The sum of (3k choose k) * 2/(3k-1) *2^(-3k), from 1 to infinity, gives us the probability the frog will return to his current position. Call this P.

Then the number of times the frog will return to his current position is a geometric distribution with parameter P, and the expected number of times the frog will visit a position, given that he visits it at least once, is 1/(1-P).

We also can see that the frog's average speed is 1/2 to the right... that is, his expected number of visits to each position must be 2.

Therefore, he must visit 2*(1-P) of the squares an average of 1/(1-P) times each, and never visit the remaining 2P-1 squares at all.

As it happens, P~.572949017, which is jason's 1-M, and 2P-1 comes out to f97's Y.

What a roundabout way to show that sum[3k choose k)*2/(3k-2)*2^(-3k), {k,1,Infinity}] = (9-3sqrt(5))/4. The difference-equation route is certainly an elegant way to get the exact answer... but hopefully this shows the connection between the two correct methods posted.

[jason1990]

[ QUOTE ]
So how did the solution for M happen to satisfy 1-M = 0.5+Y/2? The solution for M must have had a hidden assumption that half the integers are negative?

[/ QUOTE ]
This assumption is encoded in the fact that I used a kind of principal value limit. Let F(L) denote the fraction of sites between -L and L which the frog misses. Then F(L) -> 1 - M as L -> infinity. If you take, for example, the limit of the fraction of missed sites in the box [-L,2L], you will get a different limit. In this sense, the "fraction of all integers" is another ambiguity in the problem statement.

[ QUOTE ]
The solution for "Y" makes sense to me, and I consider that to be the answer to the "right" question (i.e. the best well-defined question one can form based on the wording, starting at zero and only looking forward).

[/ QUOTE ]
Since I seem to be the odd man out in my interpretation, perhaps you could help me understand yours. Specifically, where does the frog start in your interpretation? Does he start at the origin? Does he start randomly and, if so, with what distribution? Does he start "at -infinity" and, if so, what does that mean formally? Does he even start at time n = 0, or does time extend infinitely in both directions?

[Siegmund]

Rereading jason's solution, this is making a bit more sense: jason has started his frog at 0, and asked how many points in (-L,L) get visited as L gets large. The vast majority of points left of the frog's starting point never get visited, since the frog drifts to the right.

That is, the fraction of points in (-L,0) that get visited approaches 0 as L becomes large, trivially; while the fraction of points in (0,L) approaches ~0.854 as L becomes large (and this is the one that takes all the work.)

Yes, the original post was a bit ill-defined.

[jason1990]

[ QUOTE ]
Rereading jason's solution, this is making a bit more sense: jason has started his frog at 0, and asked how many points in (-L,L) get visited as L gets large. The vast majority of points left of the frog's starting point never get visited, since the frog drifts to the right.

That is, the fraction of points in (-L,0) that get visited approaches 0 as L becomes large, trivially; while the fraction of points in (0,L) approaches ~0.854 as L becomes large (and this is the one that takes all the work.)

Yes, the original post was a bit ill-defined.

[/ QUOTE ]
I just want to clarify something I said earlier. If the frog starts at any fixed point x, then the fraction of points in [-L,0] that get visited will also go to 0, since L will eventually be very far to the left of x. So this "principal value" limit is 1 - M, no matter where he starts. It then follows that it is also 1 - M if his starting point has any probability distribution on the integers. So starting the frog at 0 is not necessary for this result.

Moreover, the limit, as (L_1,L_2) -> (-infinity, infinity), of the fraction of missed sites in [L_1,L_2] does not exist.

The only way I can see to get around this is to somehow start the frog "at -infinity." I am not claiming that it is impossible to rigorously make sense of this. I just cannot presently see a sensible way to do it.