April 2007 IBM Ponder This Challenge

[PairTheBoard]

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

ok. I think I'm starting to get it. So in this simulation, using the measure, let me temp denote it u_c^i, proportional to c^i, your distribution for initial locations of the frog would be very heavily weighted up around the [45,50] part of the [0,50] interval. Heuristically this is saying that when we first look at the frog we are much more "likely" to see him relatively to the right than to the left parts of the Integers? Now, in the simulation using u_c^2, those paths that end up in [10,45] are going to be heavily represented and biased by the huge number of frogs starting in [46,50] that had the somewhat rare frog-experience of progressing backwards against their natural drift. Thus, in counting -1 and +2 jumps over all the frog 5-jump paths we will see more -1 jumps than +2 jumps. In fact, as the simulation expands we should see the ratios approach .8 and .2 respectively.

If I understand this correctly, this gives me a better idea of what the measures u(i) are doing and how they affect the
q(i,j).

However, it's not exactly what I had in mind for a simulation. I was thinking of a simulation fashioned after the problem's description of the frog jumping from
-infinity to +infinity which would produce the measure u_c^2 in a natural way. Can you think of a simulation that would do this?

[ QUOTE ]
[ 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 I understand that. But I'm looking for a heuristic for why the measure u_c^2 produces those local probabilities. From the Simulation example above it appears that the q(i,j) are coming from the right sided weighting that u_c^2 gives to initial sighting of the frog. Another way to look at it is from the perpective of the Poison Cloud of Frogs you describe below. The distribution is stationary with more frogs jumping -1 back to location i than +2 forward to location i because there are just more frogs at i+1 than at i-2.



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

This is very suprising to me, which just goes to show that intuition can only take you so far. The math speaks for itself. Looking at the measure with parameter k,

u(i) = 1 + kc^i

with a Large Scale view, the graph looks the same regardless of how small you choose k. If you make k smaller, just step back and take an even Larger Scale view of it. On the right you're going to see a line with an extremely high positive slope. Translating this to the Poison stacks of frogs you descibe below for the Cloud of Frogs you might see had they all began at
-infinity, with the Large Scale View the Fuzziness nearly disappears. And to the right where you see an extremely high slope to the line 1+kc^i, it sure seems like you are going to see a lot more frogs jumping -1 back to i than +2 forward to it. Thus, still producing a positive backward drift. Although, on the left where 1+kc^i locally looks uniform, you would not expect to see the positive backward drift. It's hard to believe that produces a consistent local q(i,j).

So I must be misunderstanding something. I really need something more though, than the explanation that the math just works out that way for how u(i) produces q(i,j).

================


I may respond more to the rest of your post(s) in a while. However, I'd like to hear what you think the implications are of this idea.

Suppose instead of conditioning on where we see the frog at our initial reference time, We instead condition on the First Time the Frog enters the interval [0,1].

PairTheBoard

[jason1990]

[ QUOTE ]
Looking at the measure with parameter k,

u(i) = 1 + kc^i

with a Large Scale view, the graph looks the same regardless of how small you choose k. If you make k smaller, just step back and take an even Larger Scale view of it. On the right you're going to see a line with an extremely high positive slope. Translating this to the Poison stacks of frogs you descibe below for the Cloud of Frogs you might see had they all began at -infinity,

[/ QUOTE ]
They did not all necessarily begin at -infinity. More on this below.

[ QUOTE ]
with the Large Scale View the Fuzziness nearly disappears. And to the right where you see an extremely high slope to the line 1+kc^i, it sure seems like you are going to see a lot more frogs jumping -1 back to i than +2 forward to it.

[/ QUOTE ]
This confuses me, since "back" and "forward" can refer to time and/or space.

[ QUOTE ]
Thus, still producing a positive backward drift. Although, on the left where 1+kc^i locally looks uniform, you would not expect to see the positive backward drift. It's hard to believe that produces a consistent local q(i,j).

[/ QUOTE ]
Okay, this is a great point. First of all, you are using the word "local," but I think you really mean "homogeneous" or "translation invariant." A time-homogeneous Markov process has a transition function q(i,j) which does not depend on t. It may also be the case that q depends only on j-i. This implies, for example, that the probability of jumping from i to i+1 does not depend on i. You might want to call this "spatially homogeneous." But it may be better just to call this a process with iid increments.

Only in the cases k_1 = 0 or k_2 = 0 do you get a reverse-time process which has iid increments. For other choices, the reverse-time transition function depends on both i and the jump size. (This, however, does not necessarily mean that the origin plays any special role. If you redefine your origin to be i_0, you simply need to redefine your k_2 to be k_2 c^{i_0}.)

For u(i) = 1 + kc^i, we get

q(i,i+1) = (1 + kc^{i+1})/(2 + 2kc^i), and
q(i,i-2) = (1 + kc^{i-2})/(2 + 2kc^i).

Now, every single frog in that Poisson cloud is going to be moving forward in time according the rules in the original puzzle. But they will be moving backward in time according the transition function above, which depends on i. Those frogs that we presently see in a very dense part of the cloud will move backward in time with an immediate positive spatial drift. This ought to carry them (back in time) farther into the denseness of the cloud, and their drift ought to increase toward some finite maximum. So those frogs ought to have "come from +infinity." Of course, there is some probability that they will initially move against their mean drift. In that case, there will be some "reinforcement," since by moving in the negative space direction, they will decrease their mean drift, making it even easier for them to continue moving against their mean drift. So it is not clear to me right now where these frogs came from. I would still expect that the frogs in the very dense parts of the cloud came from +infinity.

We can do the same analysis with the frogs that we presently see in a very sparse part of the cloud. They will move backward in time with an immediate negative spatial drift. This ought to carry them (back in time) farther into the sparseness of the cloud, and their drift ought to decrease toward the finite minimum -1/2. So those frogs ought to have "come from -infinity." But again there is the possibility that, despite their mean negative drift, they move (back in time) in the positive spatial direction, which changes their drift and helps them to possibly continue moving in this direction. Again, I expect the frogs in the very sparse parts of the cloud to have come from -infinity. This actually looks very interesting.

This cloud model is an example of an evolving point process. When we ask about the motion of a particular particle in the point process, we are asking about a so-called "tracer particle." These can be complicated and interesting models. In this case, the cloud itself remains stationary. The frogs in the cloud all behave identically in the forward time direction. But their behaviors are different in the backward time direction.

[ QUOTE ]
I may respond more to the rest of your post(s) in a while. However, I'd like to hear what you think the implications are of this idea.

Suppose instead of conditioning on where we see the frog at our initial reference time, We instead condition on the First Time the Frog enters the interval [0,1].

[/ QUOTE ]
I do not think I will have time to chew on this for a while. But you may ask yourself what it is you want to condition. Is it the nonprocess S defined on the measure space with infinite mass? Is it a particular frog in the Poisson cloud? If the latter, which frog? I assume you would want to choose a frog that came in from -infinity, but there may be many of them. Although they all have the same behavior in the forward time direction, they do not all have the same behavior in the backward time direction.

[f97tosc]

jason1990,

Sorry for the delayed response. Also excuse me if the points raised here have been addressed elsewhere in this (long) thread by now.

It seems like you put a lot of thought into this. I think I agree with most or everything you write, except I think it would be strange to select a non-uniform u.

First of all, if u is not uniform, and the observer starts looking at negative t, then he will find that the fraction of +2 jumps will converge (in the limit of many observations of negative t) towards something else than 0.5. How is this consistent with the problem?

On perhaps a related note, you write in another post that:

"I contend that this is a perfectly reasonable interpretation of the backward time steps. On the mathematical side, it is reasonable since there is no reason to prefer one invariant measure over another. It may even be reasonable on the heuristic side. One might informally argue that, since the frog has positive drift, then when we enter the frog's world without any prior information, we should be more likely to see him at large positive numbers than at large negative numbers."

But the measure u is more than just a belief about where the frog starts at time 0; it says that however far back in time we go, we always expect (and see) the frog being more or less inclined to take +2 or -1 steps. Moreover, this inclination is independent of time, except at the threshold t=0 (which was only supposed to be an arbitrary observation point, btw). I think it is problematic to use an invariant measure that is non-uniform in space, but stationary (in time); it is difficult to motivate by some sort of general background information about the frog moving from lower to higher numbers with increasing time.

[jason1990]

I was preparing another long post with some new conclusions when I saw this. So I will first reply here and then post what I was working on.

[ QUOTE ]
It seems like you put a lot of thought into this. I think I agree with most or everything you write, except I think it would be strange to select a non-uniform u.

First of all, if u is not uniform, and the observer starts looking at negative t, then he will find that the fraction of +2 jumps will converge (in the limit of many observations of negative t) towards something else than 0.5. How is this consistent with the problem?

[/ QUOTE ]
First, let me point out that there are 2 aspects of the problem with which we would like to be consistent: (1) the frog jumps forward in time by +2 or -1 with equal probability, and (2) the frog came from -infty.

Now, the questions that have interested me here are these. How can we rigorously construct the frog's movement backward in time? Is a particular such construction forced on us by either (1) alone or by (1) and (2) together?

I am satisfied by the Poisson cloud construction. We can construct this cloud as a legitimate (Markov) stochastic process taking values in the space of point configurations, i.e. the set of functions from the integers to the nonnegative integers. We can construct it for all time, both positive and negative, by making it have a stationary distribution. The stationary distributions are the ones that have a Poisson number of particles at each site with parameter u(i), and with each site being independent. We can then consider tracer particles in this system if we want to consider individual frogs.

I personally do not find it strange to use a non-uniform u. All stationary distributions for the cloud seem equally legitimate to me. With a non-uniform u, a tracer particle will jump +2 and -1 with equal probability in the forward time direction, but when we look back in time the proportion of +2 jumps does not converge to 0.5, as you pointed out. I find this surprising and interesting, but it is definitely consistent with (1). "The math speaks for itself," as PairTheBoard said.

However, are any of these non-uniform distributions consistent with (1) and (2) together? This I will address in my next post.

[jason1990]

Well, it appears I lacked the willpower to stop chewing on this. But hopefully I now have the final story and can stop thinking it. I will give a very brief summary and then the final conclusions, which are "obvious" but still kind of cool (IMO).

We have the frog process, X_t, where t is any integer. Without loss of generality we take X_0 = 0. The forward process is F_t = X_t for t nonnegative. It is a Markov chain with

P(F_{t+1} = j | F_t = i) = p(i,j),

where p(i,j) = 0.5 when j-i = 2 or -1, and 0 otherwise. The backward process is B_t = X_{-t} for t nonnegative. We have many choices for how to model B_t. In general, we choose nonnegative k_1 and k_2, not both zero, and define u(i) = k_1 + k_2 c^i, where c = (1 + \sqrt{5})/2. We then define

P(B_{t+1} = j | B_t = i) = q(i,j) := p(j,i)u(j)/u(i).

The choice k_2 = 0 makes q(i,j) = 0.5 for j-i = -2 or 1, and 0 otherwise. This is arguably the most natural choice. In this case, B_t -> -infty, so the frog came from -infty.

The choice k_1 = 0 leads to q(i,i+1) = c/2 and q(i,i-2) = 1/(2c^2). In this case, B_t -> infty, so the frog came from infty. Hence, this choice cannot model a frog hopping from -infty to infty.

The rest of this post will be devoted to the remaining cases, in which we can assume without loss of generality that u(i) = 1 + kc^i for some k > 0. Let

L(i) = P(B_t -> -infty | B_0 = i), and
R(i) = P(B_t -> infty | B_0 = i).

By coupling B_t to a chain with iid increments, it can be shown that

(1) L(i) + R(i) = 1,
(2) L(i) -> 0 as i -> infty, and
(3) L(i) -> 1 as i -> -infty.

One way to view this result is in the context of the Poisson cloud described earlier. Some of those frogs came from infty, some came from -infty. If we pick a particular frog, then the probability he came from infty will depend on the density of the cloud at the point where we find him.

Now suppose we pick a frog, and we somehow know he came from -infty. What are his backward jump probabilities when we condition on this information? In other words, we would like to compute

Q(i,j) := P(B_1 = j | B_0 = i and B_t -> -infty).

We can compute this with Bayes Theorem, but first we must compute L(i). For this, note that

L(i) = \sum_j q(i,j)L(j)
= \sum_j p(j,i)u(j)L(j)/u(i).

Multiplying both sides by u(i) shows that v(i) := u(i)L(i) is an invariant measure. Hence, v(i) = k_1 + k_2 c^i for some constants k_1 and k_2. Using properties (2) and (3), we conclude that v(i) = 1 for all i. In other words, L(i) = 1/u(i). We therefore have

Q(i,j) = q(i,j)L(j)/L(i) = q(i,j)u(i)/u(j) = p(j,i),

which is the "natural" choice we started with.

In other words, if you pick a frog in the Poisson cloud, his reverse-time behavior will be governed by the relatively complicated transition function

[ QUOTE ]
q(i,i+1) = (1 + kc^{i+1})/(2 + 2kc^i), and
q(i,i-2) = (1 + kc^{i-2})/(2 + 2kc^i).

[/ QUOTE ]

If he is presently at location i, then he will have come from -infty with probability 1/(1 + kc^i) and from infty with probability kc^i/(1 + kc^i). But if we happen to know that he came from -infty, then conditioned on this information, his reverse-time jump probabilities are simply q(i,i+1) = q(i,i-2) = 0.5.

[PairTheBoard]

Fantastic work jason. Solved and Well Solved. Very Satisfying too. Does IBM have a place where solutions can be sent? If you don't want to submit it I think somebody should at least send them a link to this thread.


What threw me off was our exchange in Your Post Here .



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

I assumed that in your computaion of the drift,

q(0,1) - 2q(0,-2) = (-1 + k(c - 2c^{-2}))/(2 + 2k)

that your choice of location i=0 did not matter. Everything being "invariant and all" that i=0 was arbitrary and any other choice for i would produce the same expression for the reverse-time drift. That's what contradicted my intuition for when u(i)=1+kc^2 and k is non-zero. That for a fixed k sufficiently small the reverse-time drift would be negative at all locations i. With the math for that being a mystery to me, I wanted to look at the Poisson cloud where I could more easily apply my intuition.

While thinking about this during the last couple of days I was going to ask you why the q(i,i+1)-q(i,i-2) did not depend on i in the single frog model but did depend on i in the Poisson Cloud model. I can now see what my misunderstanding was. From your last post for the case u(i)=1+kc^i the drift in both models depends on i and the models are consistent in this calculation. And it behaves as I thought it should. Although at first I was only looking at large positive values of i and didn't think about what happened for large negative values of i.

I am very pleased with your result. I think it gives a really Full Picture of what's going on. Thanks for your efforts.

PairTheBoard

[jason1990]

[ QUOTE ]
What threw me off was our exchange in Your Post Here .

[/ QUOTE ]
That is probably my fault and I apologize for that. I was a bit confused myself at that point. It did not occur to me while writing that post that there might be p, 0 < p < 1, such that the frog goes to infty with probability p, and to -infty with probability 1 - p. I am so used to thinking in terms of 0-1 laws, that the possibility slipped my mind. That was actually a pretty stupid oversight on my part.

[ QUOTE ]
Does IBM have a place where solutions can be sent? If you don't want to submit it I think somebody should at least send them a link to this thread.

[/ QUOTE ]
From a certain perspective, the narrative of this thread might go something like this: 2+2 members quickly solve IBM's puzzle. Then one of them invents his own puzzle and rambles on about it for several pages. So I could see how they might not be interested in all this "extracurricular" analysis. But send them the link if you want to.

[Paul Smith]

At the end, what is specifically the value of fraction of integers not visited by the frog?

[jason1990]

[ QUOTE ]
At the end, what is specifically the value of fraction of integers not visited by the frog?

[/ QUOTE ]
If the frog started his journey at time t = 0 at integer i = 0, then there will be an integer N such that he misses all integers to the left of N. The fraction of integers to the right of N which he misses will be (7 - 3\sqrt{5})/2 = 0.146. If you consider the integers to the left of N as half of all integers, then the overall fraction missed is (9 - 3\sqrt{5})/4 = 0.573. If you weight them differently, you get a different answer.

If the frog never started his journey, so that he has been jumping forever, then there are 3 models which are consistent with the fact that he jumps +2 or -1 with equal probability. They can be characterized as follows:

(1) He came from -infty.
(2) He came from +infty.
(3) He came from either -infty or +infty with probabilities p and 1 - p, respectively.

In Model 1, the fraction of missed integers is (7 - 3\sqrt{5})/2.

In Model 2, there will be an integer N such that he misses all integers to the left of N, and misses none of the integers to the right of N.

In Model 3, the fraction of missed integers is random. If we condition on him coming from -infty, then the fraction is not random and agrees with Model 1. If we condition on him coming from +infty, then the result is the same as in Model 2.

In the end, therefore, if we assume the frog has been jumping forever and that he came from -infty (which means either Model 1 or Model 3 with conditioning), then the fraction of missed integers is (7 - 3\sqrt{5})/2.

[PairTheBoard]

[ QUOTE ]
From a certain perspective, the narrative of this thread might go something like this: 2+2 members quickly solve IBM's puzzle. Then one of them invents his own puzzle and rambles on about it for several pages. So I could see how they might not be interested in all this "extracurricular" analysis. But send them the link if you want to.


[/ QUOTE ]

I disagree that your work was extracurriclar. A calculation was made early in the thread which turned out to give the correct answer. But making it rigorous is another thing. I feel I have a much better sense of what's going on after seeing the work you did.

I sent the following email to the IBM Challenge people, and cc'ed a copy to Mason.
=========================
I thouht your readers might be interested in the discussion of this problem on the 2+2 Probability Forum. I believe a very nice, rigorous solution was arrived at by the end of the thread through a group effort, with most of the hard math done by the poster jason1990. While the correct answer can be arrived at fairly easily, making it rigorous is another thing. I believe a lot more light is shed on the problem in the rigor. Hope you enjoy it.

Here is a link to the 2+2 Thread:

http://forumserver.twoplustwo.com/showfl...e=0&fpart=1


I've cc'ed Mason Malmuth, the owner of the 2+2 Forums. You might want to correspond with him on how best to publish the solution if you choose to do so. I can't see any problem in at least publishing the link.

Sincerely,

PairTheBoard
======================

Hope that meets with everyone's approval.

PairTheBoard