April 2007 IBM Ponder This Challenge

[jason1990]

[ QUOTE ]
I don't think you can deduce S is stationary from what you've done here. If t were restricted to say [-10,10], then we could easily construct a suitable X and S process.

[/ QUOTE ]
But time is not restricted to [-10,10]. The fact that time extends infinitely in the negative direction is essential to the conclusion. Under the hypothesized conditions, we know that

u_{-t-3}(i) = (q_3(i,i)/p_3(i,i)) u_{-t}(i)

for all i and all t >= 0. Let c(i) = q_3(i,i)/p_3(i,i), so that

u_{-3n}(i) = c(i)^n u_0(i).

Take any i such that u_0(i) > 0. Assume c(i) > 1. Then for n sufficiently large, u_{-3n}(i) > 1, a contradiction. Hence c(i) <= 1. But

\sum_i u_0(i) = 1 = \sum_i u_{-3n}(i) = \sum_i c(i)^n u_0(i),

so each c(i) = 1. This shows that u_{-3n} = u_0 for all n, and so the process S, restricted to times which are multiples of 3, has the same distribution at all times. This is clearly not possible, given the transition function p.

By the way, I just came across this link, http://www.math.uah.edu/stat/markov/TimeReversal.xhtml, which may explain things better than I. One of the conclusions from the first section is that the time-reversed Markov chain is a time-homogeneous Markov chain if X_0 has an invariant distribution. In our case, there is no invariant distribution. But there is an invariant measure. However, it is not unique, so there is more than one way to construct the process in the negative time direction.

[marv]

[ QUOTE ]
[ QUOTE ]
I don't think you can deduce S is stationary from what you've done here. If t were restricted to say [-10,10], then we could easily construct a suitable X and S process.

[/ QUOTE ]
But time is not restricted to [-10,10]. The fact that time extends infinitely in the negative direction is essential to the conclusion. Under the hypothesized conditions, we know that

u_{-t-3}(i) = (q_3(i,i)/p_3(i,i)) u_{-t}(i)

for all i and all t >= 0. Let c(i) = q_3(i,i)/p_3(i,i), so that

u_{-3n}(i) = c(i)^n u_0(i).

Take any i such that u_0(i) > 0. Assume c(i) > 1. Then for n sufficiently large, u_{-3n}(i) > 1, a contradiction. Hence c(i) <= 1. But

\sum_i u_0(i) = 1 = \sum_i u_{-3n}(i) = \sum_i c(i)^n u_0(i),

so each c(i) = 1. This shows that u_{-3n} = u_0 for all n, and so the process S, restricted to times which are multiples of 3, has the same distribution at all times. This is clearly not possible, given the transition function p.

[/ QUOTE ]

OK.

[jason1990]

[ QUOTE ]
We can define a backwards process in this case by noting that the increments in S are IID,

[/ QUOTE ]
Yes. In other words, p(i,j) depends only on i - j. Whenever this is the case, the uniform measure will be an invariant measure, in which case...

[ QUOTE ]
we can add up their negatives in reverse order.

[/ QUOTE ]
In other words, we can form the reverse chain by using the transitions q(i,j) = p(j,i). We can obviously do the same thing with a symmetric random walk, with equally likely steps +1 and -1. But in that case, things are much cleaner, since the uniform measure is the unique invariant measure (up to constant multiples). So adding their negatives in reverse order is the only way to construct the reverse chain.

But in our case, we have other invariant measures, such as u(i) = [(1 + \sqrt{5})/2]^i. So we can also form the reverse chain by using the transitions q(i,j) = p(j,i)u(j)/u(i).

[pzhon]

[ QUOTE ]

In other words, if you look at a sequence going from (t_0,i_0) to (t_n,i_n), there is no way for you to statistically determine whether it was generated by the forward process (as described in the original puzzle) or by a time reversal of the backward process described above.

[/ QUOTE ]
This is true for any probabilities p and 1-p. You always lose the information on the drift when you pin both endpoints of a Brownian motion. This works equally well when you condition on two locations within the region with positive time. (You should find a difference when t_0 is negative and t_n is positive, which may be enough for you to discard that construction.)

This is very far from saying that you can't discuss the properties of a typical walk from -infinity to +infinity. It sounds like you are raising objections on the negative time side that apply equally to the positive side (by reversing time and the locations).

I interpret the problem as saying that the steps are independent, and have probability 1/2 each of being -1 and 2. This applies equally to the next step as to the previous step. I don't specify the location at time 0. Time doesn't have to be labelled by Z, just by a Z-torsor, a set with a principal Z-action. (In fact, the same is true of the line itself.) We're not interested in determining the probability that the frog is at a location at time 0. We're interested in the properties of the path. There are many limiting constructions which do not converge to a sensible probability, but such that the properties of the paths converge.

Random tilings of the entire line or plane are often discussed by mathematical tiling theorists and mathematical physicists, who discuss the Gibbs measure. There are some technical difficulties, but are these what you are interested in? Would you object to discussing a random tiling of the line with tiles of width 1 and 2 in equal proportion?

This problem describes a virtual tiling of the line with tiles of width -1 and 2 in equal proportion. This adds more technical difficulties. Is your interest the difference between a tiling (where everything is covered once) and a virtual tiling (where locations are covered once with multiplicity, where there are negative multiplicities, but almost surely only finitely many tiles cover a point)?

[jason1990]

[ QUOTE ]
[ QUOTE ]

In other words, if you look at a sequence going from (t_0,i_0) to (t_n,i_n), there is no way for you to statistically determine whether it was generated by the forward process (as described in the original puzzle) or by a time reversal of the backward process described above.

[/ QUOTE ]
This is true for any probabilities p and 1-p.

[/ QUOTE ]
You are right. In hindsight, I now think that the example in my post you are replying to does not really illustrate anything. But I still think the discussion I presented about different invariant measures has meaningful content. In this failed example, I was trying to formalize the idea of the "tape running backwards" in a way which avoided a discussion of invariant measures with infinite mass. Perhaps that is not possible.

[ QUOTE ]
This is very far from saying that you can't discuss the properties of a typical walk from -infinity to +infinity.

[/ QUOTE ]
In case it was not clear, this is not at all what I am trying to claim.

[ QUOTE ]
It sounds like you are raising objections on the negative time side that apply equally to the positive side (by reversing time and the locations).

[/ QUOTE ]
There is an inherent asymmetry between positive and negative time. The puzzle tells us the transition probabilities for a forward time step. It is up to us to deduce the transition probabilities for a negative time step.

You appear to be assuming that, if we flip the time and space axes, then we should get a process which has the same law as the original. I contend that this is not implied by the hypothesis that the frog jumps forward by +2 or -1 with equal probability. Symmetry under "flipping" is an additional assumption we might choose to impose on the process, and it amounts to a particular choice of invariant measure.

[ QUOTE ]
I interpret the problem as saying that the steps are independent, and have probability 1/2 each of being -1 and 2. This applies equally to the next step as to the previous step.

[/ QUOTE ]
I agree that this is a reasonable interpretation. I contend that there are other reasonable interpretations. As I stated before, this interpretation is equivalent to performing the standard construction of a reverse-time Markov chain, where you use the uniform measure as your invariant measure. In the case of a symmetric walk with steps +1 and -1, this invariant measure is unique and this is the only was to reverse the chain. Here is a quote from one of f97tosc's posts:

[ QUOTE ]
Actually the backward process is quite simple: If the frog's position at time t is n, then by Bayes' theorem its position at t-1 is n+1 with probability

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

where P(n+1) and P(n-2) are the a priori probabilities that the frog was at n+1 or n-2 at time t-1. If we have no a priori information about the frog before the time t (which is the implication of a backward process), then by symmetry P(n+1)=P(n-2), and so the transition probabilities going backwards are simply go to n+1 with probability 0.5

[/ QUOTE ]
This construction implicitly assumes that the prior probabilities of the position of the frog at time t-1 are all the same. In other words, it uses the uniform measure for the prior probabilities. This is justified because the uniform measure is an invariant measure for this process.

(Incidentally, this is not justified by some kind of indifference principle. In cases where one is time-reversing a Markov chain with a unique, non-uniform stationary distribution, one must use the stationary distribution for the prior probabilities. So the prior probabilities must be taken from an invariant measure.)

But in this case, there are other invariant measures to choose from. We could, for example, take P(n) = c^n, where c = [(1 + \sqrt{5})/2]. This would also be justified by the fact that this measure is invariant for our process. If we do that, then we get P = c/2, as I have previously described. 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. In other words, the prior probabilities should be an increasing function of n.

[ QUOTE ]
Time doesn't have to be labelled by Z, just by a Z-torsor, a set with a principal Z-action.

[/ QUOTE ]
This is interesting. Are you saying that you have a Z-torsor X, and a family of random variables {S_t: t in X}, which model the frog's jumping process? If so, I would be interested in reading about it.

[ QUOTE ]
(In fact, the same is true of the line itself.)

[/ QUOTE ]
I would guess that the issue I am describing would still occur even in that case. We could take an invariant measure P(x) for x in X such that P(x)/P(y)=c^g, whenever y.g=x. Honestly, though, I know nothing about torsor-valued Markov processes or Markov processes indexed by torsors. But I would be happy to learn.

[ QUOTE ]
Random tilings of the entire line or plane are often discussed by mathematical tiling theorists and mathematical physicists, who discuss the Gibbs measure. There are some technical difficulties, but are these what you are interested in? Would you object to discussing a random tiling of the line with tiles of width 1 and 2 in equal proportion?

[/ QUOTE ]
Well, I suppose I would not object. But I do not know anything about random tilings. Really, though, my perspective on this is from the theory of Markov processes. My main interest is in exploring the different ways of making sense of a Markov process defined on an infinite time-line.

[PairTheBoard]

Watching you guys work on this together is like taking a peek into Gauss' brain.

I would like to see a satisfactory solution. It seems to me this speaks to the philisophical argument sometimes made about the necessity of an Intitial Cause. I forget which famous guy first proposed it but the idea is that since every Effect has a Cause, "therefore" you must have an Initial Cause. I've always thought the "therefore" was just bs. 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).

So if you guys can't satisfactorily model this mathematically I might have to conclude something philisophically radical.

PairTheBoard

[Pokerlogist]

For fun(!), I just ran a quick and dirty simulation that counted the number of missed integers. The frog started at -100,000 and was forced to stop after +100,000. It randomly hopped -1 or +2.

The proportion of missed integers was .57.
This exactly agrees with Jason's answer. Nice [img]/images/graemlins/smile.gif[/img]

[jason1990]

From my previous post:

[ QUOTE ]
In this failed example, I was trying to formalize the idea of the "tape running backwards" in a way which avoided a discussion of invariant measures with infinite mass. Perhaps that is not possible.

[/ QUOTE ]
Here is another attempt. Let us do what marv suggested and restrict time to [-10,10]. We know that

P(S_{t+1} = i-1 | S_t = i) = 1/2.

Let us try to compute the reverse transition

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

Recalling that p_t(i,j) = P(S_t = j | S_0 = i), we can write this as q(t,i) = N/D, where

N = P(S_{t-1} = i+1, S_t = i)
= \sum_j P(S_{-10} = j, S_{t-1} = i+1, S_t = i)
= \sum_j P(S_{-10} = j)p_{t+9}(j,i+1)p(i+1,i)
= (1/2)\sum_j P(S_{-10} = j)p_{t+9}(j,i+1), and

D = P(S_t = i) = \sum_j P(S_{-10} = j)p_{t+10}(j,i).

We see, then, that the transition q(t,i) is not uniquely determined without assuming something about the distribution u(j) = P(S_{-10} = j). What shall we assume about it? Well, we know the frog has been jumping for a long time before reaching t = -10. So one less jump should not matter. In other words, whatever we assume for S_{-10} should hold equally well for S_{-11}. That is, we want

u(j) = P(S_{-10} = j)
= P(S_{-11} = j+1)(1/2) + P(S_{-11} = j-2)(1/2)
= (u(j+1) + u(j-2))/2.

Unfortunately, there is no solution to this recursion with the property that \sum_j u(j) = 1. So we cannot find a satisfying probability distribution to impose on S_{-10}. We can, however, do an approximation. Note that the positive solutions to the above recursion can be written in the form

u(j) = k_1 + k_2 c^j,

where c = (1 + \sqrt{5})/2. We will therefore take two approaches in what follows.

Approach 1. Let us assume that S_{-10} is uniformly distributed on some large interval I of length L. If you like, imagine a sequence of intervals whose union is the entire set of integers. It does not matter whether these intervals are symmetric about the origin or not. The origin plays no special role here. This approach amounts to taking the solution (k_1,k_2) = (1,0).

Now, for fixed i, p_{t+9}(j,i+1) will be zero for all j outside of some bounded interval. Hence, once I is large enough,

N = (1/2)\sum_j u(j)p_{t+9}(j,i+1)
= (1/2L)\sum_j p_{t+9}(j,i+1)
= (1/2L)\sum_j p_{t+9}(0,i+1-j)
= (1/2L)\sum_j p_{t+9}(0,j) = 1/2L, and

D = \sum_j u(j)p_{t+10}(j,i)
= (1/L)\sum_j p_{t+10}(0,i-j) = 1/L.

Hence, the reverse jump of +1 occurs with limiting probability q(t,i) = N/D = 1/2. [img]/images/graemlins/spade.gif[/img]

Approach 2. Let us assume that S_{-10} is distributed on some large interval I of length L, and its distribution u(j) is proportional to c^j. As in Approach 1, this distribution is also translation invariant, in the sense that only the length L matters. The actual location of the interval I does not affect this distribution, and the origin plays no special role here either. (One way to see this is to observe that u(j) is also proportional to c^{j-a}, where a is left endpoint of the interval I.) This approach amounts to taking the solution (k_1,k_2) = (0,1).

Let M = M(I) denote the sum over all j in I of c^j, so that u(j) = (c^j)/M. In general, as above, when I is sufficiently large,

\sum_j u(j)p_s(j,i) = (1/M)\sum_j c^j p_s(0,i-j)
= (c^i/M)\sum_j c^{j-i} p_s(0,i-j)
= (c^i/M)\sum_j c^{-j} p_s(0,j).

I will leave it as an exercise to prove by induction that

\sum_j c^{-j} p_s(0,j) = 1 for all s.

(Use the relations p_{s+1}(0,j) = \sum_i p(0,i)p_s(i,j) and p_s(i,j) = p_s(0,j-i).) It now follows that

N = (1/2)\sum_j u(j)p_{t+9}(j,i+1) = c^{i+1}/2M, and
D = \sum_j u(j)p_{t+10}(j,i) = c^i/M.

Hence, in this case, the reverse jump of +1 occurs with limiting probability q(t,i) = N/D = c/2. [img]/images/graemlins/spade.gif[/img]

As I mentioned previously, I think reasonable arguments, both mathematical and heuristic, exist for justifying both of these approaches.

[jason1990]

[ QUOTE ]
For fun(!), I just ran a quick and dirty simulation that counted the number of missed integers. The frog started at -100,000 and was forced to stop after +100,000. It randomly hopped -1 or +2.

The proportion of missed integers was .57.
This exactly agrees with Jason's answer. Nice [img]/images/graemlins/smile.gif[/img]

[/ QUOTE ]
In order to "honestly" get my answer, you should have started the frog at 0, not -100,000. I suspect that you only got my answer because you stopped the frog the first time he reached +100,000. The real frog would have kept jumping and backtracked over a lot of those missed sites, giving you f97tosc's answer.

[jason1990]

[ 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.