April 2007 IBM Ponder This Challenge

[Pokerlogist]

I found a bug in program [img]/images/graemlins/blush.gif[/img] and corrected it. This time the same proportion occurred no matter if the frog went from -100,000 to +100,000 or from 0 to +100,000. BTW, in the first case the frog hopped 401,812 times.

Either way the proportion of missed integers was .146.
This matches f97tosc's proportion. So now gets the nod [img]/images/graemlins/smile.gif[/img].

[jason1990]

[ QUOTE ]
I found a bug in program [img]/images/graemlins/blush.gif[/img] and corrected it. This time the same proportion occurred no matter if the frog went from -100,000 to +100,000 or from 0 to +100,000. BTW, in the first case the frog hopped 401,812 times.

Either way the proportion of missed integers was .146.
This matches f97tosc's proportion. So now gets the nod [img]/images/graemlins/smile.gif[/img].

[/ QUOTE ]
I just simulated 400,000 steps of this walk, starting at 0. I ran the simulation 100 times. The lowest the walk ever reached was -9. So if you started it at 0, it should have skipped nearly all the numbers between -100,000 and 0, meaning the proportion should have been at least 0.5.

Perhaps when you started it at 0, you only counted the proportion of missed sites between 0 and +100,000; whereas when you started it at -100,000, you counted the proportion of missed sites between -100,000 and +100,000. If that is the case, then you basically just did the same experiment twice. You may want to look back at how I computed 0.573 to see what that number actually represents.

No one is disputing that the proportion of missed sites to the right of the starting point is 0.146. What we are discussing is what happens to the left of the starting point. After all, the puzzle asks for the proportion of all integers which are missed, and this includes those to the left of the starting point. If the frog does not move "backwards in time" (which we are discussing), then, in the limit, 100% of the sites on the left are missed. If you consider those sites to constitute half of all the integers, then the total proportion of missed sites is 0.5 + (0.146)/2 = 0.573.

[Pokerlogist]

Thanks for the explanation. As you stated I did limit the integer range to between (-100,000,100,000) and (0,+100,000) so that is how I got .146. I thought this was correct simply because integers less than negative infinity (or greater than positive infinity) are not supposed to exist. I confess I may be out of date on this topic and don't feel qualified to enter a debate on it.

This might be a good read:
http://discovermagazine.com/1995/dec...typlusonea599/

[PairTheBoard]

[ QUOTE ]
[ QUOTE ]
What's the problem with a Universe existing from time -infinity to +infinity where the laws of Cause and Effect consitently work locally in time? In this case, the local Law of Cause and Effect is that if the Frog is somewhere in time (Cause) he jumps -1 or +2 with equal probability (Effect).

[/ QUOTE ]
There is nothing wrong with this in general. The question I am posing is this: if you know the rule for moving forward in time, what is the rule for moving backward? If the process you are describing has a unique invariant distribution, then the answer is unique: the probability of moving backward from i to j is u(j)/u(i) times the probability of moving forward from j to i, where u is the invariant distribution.

The frog puzzle poses a technical difficulty. Since there is no invariant distribution, we must use an invariant measure. But this is not a major problem. The real issue I keep mulling over is the fact that the invariant measure is not unique. So the rule for moving backward is not uniquely specified by the rule for moving forward.

If you look at my long post here, you can see that the time interval I chose, [-10,10], is not important. The same thing works for any time interval [t_1,t_2]. So I am really describing processes that have no special time or space origin, and which follow the frog's rule for moving forward. But the two processes have different rules for moving backward.

[/ QUOTE ]

I may have missed it, but using the two measures you described were you able to calculate the fraction of missed Integers for each of them? Assuming you can do that, are there simulations you can describe that would simulate the frog under the two measures?

I've got the vague notion that to break the Philisophical argument that Cause-Effect implies a First Cause, you ought to be able to create a -infinity to +infinity Universe sort of "All at Once". Yet in this Frog Universe you seem still bound by the First Cause Principle in the way you are using a Point of Reference for the Frog and then creating the Universe both backwards and forwards from that Point of Reference. You are sort of using the point of Reference as a First Cause for both Forward Effects and Backward Effects. So I liked the sound of pzhon's idea of Tiling the Integers all at once with +2 and -1 Frog Jump tiles. I'd be interested to see if that could be translated into a reasonable model for the Frog Universe as described in the puzzle.

PairTheBoard

[jason1990]

I suspect there may still be some confusion. I did not mean to imply that "integers less than negative infinity" have anything to do with this discussion. If the frog starts at negative infinity (whatever that may mean) then there are no integers to the left of his starting point. What I am wondering about are the possible ways in which we might model a frog which starts at negative infinity. There appears to be more than one "natural" approach to this, and these different approaches lead to different processes.

[jason1990]

[ QUOTE ]
you ought to be able to create a -infinity to +infinity Universe sort of "All at Once".

[/ QUOTE ]
There may be multiple constructions which would satisfy your urge to see the frog's universe created all at once. For me, one such construction would be a stochastic process {..., S_{-2}, S_{-1}, S_0, S_1, S_2, ...} which satisfies P(S_{t+1} = j | S_t = i) = p(i,j) for all t, i, and j. I do not know if such a process exists. But here is what I do know.

(1) The existence of such a process is equivalent to the existence of the corresponding probability distributions. That is, it suffices to find probability measures u_t(i) such that

u_{t+1}(j) = \sum_i u_t(i)p(i,j).

Such a family of probability measures is called an "entrance law." If we are given an entrance law, then the process S can be defined by placing a probability measure on the set of all functions from the integers to the state space. This probability measure is the unique probability measure such that the probability of the set of paths w(t) satisfying

w(t_1) = i_1, ..., w(t_n) = i_n,

where t_1 < ... < t_n, is

u_{t_1}(i_1)*p_{t_2-t_1}(i_1,i_2)*...*p_{t_n-t_{n-1}}(i_{n-1},i_n).

In the general case, if the Markov chain has a stationary distribution u, then an entrance law is given by u_t = u for all t. In the frog case, this does not apply, since there is no stationary distribution. (There are, however, invariant measures, as described previously.) I have just started reading about entrance laws in the paper, "Entrance laws for Markov chains" by J. Theodore Cox, in the Annals of Probability, 5(4), 1977, 533--549.

(2) In the general case, suppose p(i,j) > 0 for all i and j, and the Markov chain is not positive recurrent. If there exists T and a > 0 such that

\sum_{t=1}^T p_t(i,i) > a for all i,

then there is no entrance law. This does not apply in the frog case either. However, if we change the frog's jumps so that p(0,2) and p(0,-1) are both slightly less than 1/2, and distribute the remaining mass appropriately to the the other integers, then this result would imply there is no entrance law.

(3) If we also require that S has a reverse jump law, i.e. we require that there exists a function q, which does not depend on t, such that

P(S_{t-1} = j | S_t = i) = q(i,j),

then S will not exist. This additional requirement would imply that u_{3t} is independent of t, which is not possible in the frog's universe. This was shown in a previous post.

(4) If we are willing to be more abstract, then we can define a suitable "process" S that does everything we want. As in (1), it would be defined by placing a measure on the set of all functions from the integers to the state space. This measure, however, would not be a probability measure. It would be the unique measure such that the measure of the set of paths w(t) satisfying

w(t_1) = i_1, ..., w(t_n) = i_n,

where t_1 < ... < t_n, is

u(i_1)*p_{t_2-t_1}(i_1,i_2)*...*p_{t_n-t_{n-1}}(i_{n-1},i_n),

where for u we take an invariant measure. In the frog puzzle, this means we choose nonnegative numbers k_1 and k_2, not both zero, and define u(i) = k_1 + k_2 c^i, where c = (1 + \sqrt{5})/2.

(5) In the setting of (4), we can ask about the reverse jump laws. If we have some candidate q(i,j), which we think models the reverse jump laws, then we can test it as follows.

STEP 1. Choose an invariant measure u and construct S as in (4). Reverse S.
STEP 2. Using the same invariant measure u, construct S as in (4), but with p(i,j) replaced by q(i,j).
STEP 3. Check that the "processes" (i.e. the measures on the set of all functions from the integers to the state space) obtained in Steps 1 and 2 are the same (up to constant multiples).

If your candidate is q(i,i+1) = q(i,i-2) = 1/2, then these 3 steps will be successful only if you choose u by setting k_2 = 0. If you choose u by setting k_1 = 0, then the successful candidate will be q(i,i+1) = c/2, q(i,i-2) = 1/(2c^2). In general, the jump law q and the invariant measure u are related by q(i,j) = p(j,i)u(j)/u(i).

(6) If we construct a "process" S as in (4), and then "condition" it on the event {S_{t_0} = i_0}, then what we obtain is a legitimate stochastic process, defined on an actual probability space. When we look forward in time from t_0, the conditioned process is a Markov chain with transition function p. When we look backward in time, it is a Markov chain with transition function q.

[ QUOTE ]
I may have missed it, but using the two measures you described were you able to calculate the fraction of missed Integers for each of them?

[/ QUOTE ]
For u(i) = 1, the fraction missed is 0.146, and I think this is generally agreed upon.

For u(i) = c^i, the situation is dramatically different. If my algebra is correct, the resulting process actually has a positive drift in the negative time direction. I find this very counterintuitive and one of the most interesting aspects of this example. It means the frog is "entering from positive infinity," i.e. S_{-infty} = +infty. (One might reasonably argue that this goes against the wording of the original puzzle.) As for the frog's missed sites in that case, it means his entire path, going in both time directions, will be bounded below. I have not calculated the fraction of missed integers above this infimum.

Another interesting example would be to choose a combination of k_1 and k_2, with k_2 > 0, such that the frog has a negative drift in the negative time direction. For such a choice, the frog would enter from negative infinity, i.e. S_{-infty} = -infty, which is consistent with "hopping on the integers from minus infinity to plus infinity." However, the asymptotic fraction of missed integers would be different, depending on whether you looked forward in time or backward in time. I have not done any calculations for any such choice.

[ QUOTE ]
are there simulations you can describe that would simulate the frog under the two measures?

[/ QUOTE ]
Since we are talking about "probabilities" that add up to infinity, I do not know how relevant a simulation might be. You could try generating the frog's position on an interval, say [0,50], and then running its jumps forward for some time, say 5 time steps. You could then throw away any paths that did not end up in [10,45]. Those that end up in [10,45] will not have been affected by the fact that you originally put no mass outside of [0,50]. According to these paths, you may as well have filled the entire integer lattice with your measure. When you're done, you reverse all those paths and try to estimate the probabilities of +1 jumps versus -2 jumps. In one case, you could use the uniform distribution on [0,50]. In another case, you could use a distribution proportional to c^i.

However, there is really no need for a simulation in this case. I have worked out analytically what those probabilities will be in a previous post.

[ QUOTE ]
You are sort of using the point of Reference as a First Cause for both Forward Effects and Backward Effects.

[/ QUOTE ]
I hope that the preceding explanation helps clarify the use of the point of reference. It appears only in the conditioned process in (6). It may not be accurate to call it a "first cause" for the future and the past. We use the present state of the world to try and deduce things about the past, as well as predict things about the future. But that does not mean we regard the present as the cause of everything.

Of course, there is a sort of first cause in the general construction. Namely, the process S is not uniquely specified until you specify u. I think it is worth reemphasizing that this lack of uniqueness does not hold for all processes. As I have said before, if the jumps were +1 and -1 with equal probability, then u(i) = 1 would be the unique invariant measure and there would be no choice to make in (4). On the other hand, it may not be accurate to call u a first cause either. It may be better to say that u is part of the law of the process. The behavior of the process is described by two objects, p and u. (In the case of the symmetric random walk, p determines u, so the entire law is encoded by p.)

[PairTheBoard]

I'm doing my best to follow along with you here. I hope my observatons are not too naive.

[ QUOTE ]
where for u we take an invariant measure. In the frog puzzle, this means we choose nonnegative numbers k_1 and k_2, not both zero, and define u(i) = k_1 + k_2 c^i, where c = (1 + \sqrt{5})/2.


[/ QUOTE ]

Can you give a heuristic for what u(i) is measuring? My impression is that it is sort of the relative (loosely speaking) "chance" of seeing the frog at locations i. Except when? Any time? Maybe you could be more specific in your simulation,

[ QUOTE ]
You could try generating the frog's position on an interval, say [0,50], and then running its jumps forward for some time, say 5 time steps. You could then throw away any paths that did not end up in [10,45]. Those that end up in [10,45] will not have been affected by the fact that you originally put no mass outside of [0,50]. According to these paths, you may as well have filled the entire integer lattice with your measure. When you're done, you reverse all those paths and try to estimate the probabilities of +1 jumps versus -2 jumps. In one case, you could use the uniform distribution on [0,50]. In another case, you could use a distribution proportional to c^i.


[/ QUOTE ]

How would you be using those distributions in the simulation? For the frog's intitial position? So in the general situation u(i) gives a nonprobabilty measure for frog locations at any time we want to start looking?

Anyway, the frog forces u(i) = k_1 + k_2c^i where c is about 1.6

So no matter what you use for k_1,k_2, as long as k_2 is non-zero u(i) is going to have nearly all its weight pushed up toward the +infinity side. And so once you condition on an actual location for the frog at your initial reference time u(i) produces a probabilty distribution for where the frog has been that's heavily weighted toward the +infinity side? Which is why in,

q(i,i+1) = c/2, q(i,i-2) = 1/(2c^2)

you get the chance the frog came from the right to be about .8 while the chance he came from the left about .2

You get the chance he came from the right higher because u(i) being weighted on +infinity causes the probabilty distribution for where the frog has been to be weighted to the right?

Thus you get a counter intuitive positive drift looking back in time to where the frog's been. I think since c>1, as long as you give k_2 any non-zero value, u(i) is going to be dominated by the c^i term and you will continue getting this nonintuitive result.

I can see the heuristic where if the frog has been jumping since
-infinity time up to the reference time we're conditioning on, we might expect his locations in past finite times to be weighted to the right, since he is drifting right.

However, consider something like this. Suppose the problem posed said the frog marches from -infinity to +infinity according to the rule that he always jumps +1. What fraction of integers does he visit? I think we all agree it would be 100%. I'm curious whether you would apply two measures u(i) to that problem? The same heuristic holds I think. There should be a right sided bias to where we expect to see the frog. Even more so in fact than in the +1/2 drift of the original frog.

Suppose further that instead of just one frog always marching +1 we had an infinite stream of frogs, one right after another, all marching +1 from -infinity to +infinity. What would we see when we looked at the scene at our reference time? A stream of frogs marching to the right. And since no reference time can be prefered over another with respect to a -infinity starting gate there's really no bias as to where we'd expect to see the front of the marching frogs. And it would be apparent that they each visit each integer.

I wonder what we would see if instead of marching frogs it was a steady stream of -1,+2 jumping frogs. Wouldn't we expect to see a sort of fuzzy streatched out cloudy stream of jumping frogs drifting to the right, on their way to visiting that fraction of integers to their right as calulated by f97tosc. And will not each of them have already visited that fraction of integers on their left as their compatriot frogs far in the rear are about to visit on their right? What I don't think we would expect to see is a huge pile up of frogs up near +infinity. Any more than we would see such a pile up with the +1 marching frogs even though they are progressing in that direction even faster.

The thing is, with a single frog, even if he's a +1 marching frog, it's hard for us to see him coming from -infinity. But with the single marching frog I don't think we'd have any problem modeling his march from -infinity by looking at his march from location i_0 and calculating the fraction of integers he will visit on his march to the right. Then let i_0 go to -infinity. We wouldn't worry about his not visiting integers to his left from any of the starting locations we look at because we know he is marching to the right. Why not view the -1,+2 jumping frog the same way?

In other words, throw out the case where k_2 is non-zero as simply not fitting the problem and claim mathematical rigor according to the only choice that's left.

PairTheBoard

[jason1990]

[ QUOTE ]
Can you give a heuristic for what u(i) is measuring? My impression is that it is sort of the relative (loosely speaking) "chance" of seeing the frog at locations i. Except when? Any time? Maybe you could be more specific in your simulation,

[ QUOTE ]
You could try generating the frog's position on an interval, say [0,50], and then running its jumps forward for some time, say 5 time steps. You could then throw away any paths that did not end up in [10,45]. Those that end up in [10,45] will not have been affected by the fact that you originally put no mass outside of [0,50]. According to these paths, you may as well have filled the entire integer lattice with your measure. When you're done, you reverse all those paths and try to estimate the probabilities of +1 jumps versus -2 jumps. In one case, you could use the uniform distribution on [0,50]. In another case, you could use a distribution proportional to c^i.


[/ QUOTE ]

How would you be using those distributions in the simulation? For the frog's intitial position? So in the general situation u(i) gives a nonprobabilty measure for frog locations at any time we want to start looking?

[/ QUOTE ]
That is right. It is a stationary measure. In general, if you want to reverse a Markov chain and have the result be another (time homogeneous) Markov chain, you must have the Markov chain be stationary.

[ QUOTE ]
Anyway, the frog forces u(i) = k_1 + k_2c^i where c is about 1.6

So no matter what you use for k_1,k_2, as long as k_2 is non-zero u(i) is going to have nearly all its weight pushed up toward the +infinity side.

[/ QUOTE ]
This is not really relevant. Suppose you see the frog at a particular location i at some time t. The probability of the reverse jumps are governed only by the relative probabilities that the frog was, at time t-1, at location i+1 versus i-2. What is going on at infinity or -infinity is irrelevant for this particular jump. The invariant measures tell us how to assign these relative probabilities in a way which does not depend on t.

[ QUOTE ]
I think since c>1, as long as you give k_2 any non-zero value, u(i) is going to be dominated by the c^i term and you will continue getting this nonintuitive result.

[/ QUOTE ]
The drift in the negative direction is

q(0,1) - 2q(0,-2) = u(1)p(1,0)/u(0) - 2u(-2)p(-2,0)/u(0)
= (u(1) - 2u(-2))/(2u(0)).

Take u(i) = 1 + kc^i. Then this becomes

(-1 + k(c - 2c^{-2}))/(2 + 2k).

This is a continuous function of k, so for k sufficiently small (yet positive), the drift will still be negative.

Again, it is simply the relative weights that determine the transition function q and, hence, the drift.

[ QUOTE ]
However, consider something like this. Suppose the problem posed said the frog marches from -infinity to +infinity according to the rule that he always jumps +1. What fraction of integers does he visit? I think we all agree it would be 100%. I'm curious whether you would apply two measures u(i) to that problem?

[/ QUOTE ]
In this case, the transition function is p(i,i+1)=1. So an invariant measure must satisfy u(i) = u(i-1). The only invariant measure, therefore, is the uniform measure. So the only way to reverse this chain is to simply jump the frog by -1 each step.

[jason1990]

[ QUOTE ]
I wonder what we would see if instead of marching frogs it was a steady stream of -1,+2 jumping frogs.

[/ QUOTE ]
I think, perhaps, that the use of the phrase "steady stream" suggests that you are implicitly still thinking of a uniform distribution, which represents the choice k_2 = 0. If you look at a window in space and happen to see a cloud of frogs which is uniformly distributed, then it will remain so. This is true. But if you happen to see a cloud of frogs which is distributed according to u(i) for some k_2 > 0, then this will also be stable.

[jason1990]

Here is a cloud-of-frogs model. Choose an invariant measure u(i). On each spatial point i, place a random number of frogs, N(i), where N(i) is Poisson with parameter u(i). (Note that since v(i) := u(i+1) is also invariant, the choice of spatial origin is, in fact, arbitrary.) Now let each frog jump +2 or -1 with equal probability. Pick a site i. What is the distribution of the number of frogs at site i after one time step? (Call this N_+(i).)

If we condition on N(i-2) and N(i+1), then N_+(i) will be binomial with parameters S = N(i-2) + N(i+1) and p = 1/2. Hence,

P(N_+(i) = m) = \sum_{k=m}^\infty P(S = k)(k choose m)2^{-k}.

Since S is Poisson with parameter L = u(i-2) + u(i+1), this becomes

P(N_+(i) = m) = e^{-L}\sum_{k=m}^\infty (L/2)^k/(m!(k-m)!)
= [e^{-L}(L/2)^m/m!]\sum_{k=m}^\infty (L/2)^{k-m}/(k-m)!
= [e^{-L}(L/2)^m/m!]e^{L/2}
= e^{-L/2}(L/2)^m/m!

So, after one time step, N_+(i) is Poisson with parameter L/2. But since u is an invariant distribution,

L/2 = (u(i-2) + u(i+1))/2 = u(i),

and the distribution of N_+(i) is the same as that of N(i).