April 2007 IBM Ponder This Challenge

[f97tosc]

I think we can resolve this by considering a reversed time process. That is, let the frog be (note: I am not writing start) at integer 0 at time 0. We now define two frog processes, one following the frog going forward in time, and one following the frog backwards in (negative) time. Neither process has an end, and both obey the specifications of the problem. We seek the intersection of the integers missed by the two processes, in the limits of small and big t.

The forward process is defined directly by the problem.

So the question is, can we define a backward process which is unique, Markovian, and consistent with the forward process? By consistent, we mean that given any times t1 and t2 and integers n1 and n2, there is no way to (statistically) distinguish between a tape of the forward process going from (t1,n1) and (t2,n2) or a backward process going from (t2,n2) to (t1,n1). I contend that this is possible but am too tired to work out the transition probabilities etc right now.

In any case, if we do this, then the fraction of integers missed in (-infty, 0] must be the same (if the backward process was consistent) as the fraction of integers in [0,infty), and so the fraction missed is Y.