View Single Post
  #28  
Old 04-13-2007, 12:36 PM
jason1990 jason1990 is offline
Senior Member
 
Join Date: Sep 2004
Posts: 932
Default Re: April 2007 IBM Ponder This Challenge

I just thought of an example which I think better illustrates what I am trying to say at the end of my previous post.

Define X_0 = 0. In the forward time direction, X jumps -1 or +2 with equal probability. In the negative time direction, X jumps +1 or -2 with probabilities c/2 and 1/(2c^2), respectively.

You get to observe a segment of the path of this process that consists of n time steps. You know that it lies either entirely on the positive time axis or entirely on the negative time axis, but you do not know which. You also know the initial location of the path is i_0, and the final location is i_n. Can you statistically determine which side of the time axis you are on?

Suppose you are on the positive side of the time axis. Conditioning only on the initial location, each path of length n going from i_0 to i_n has probability 2^{-n}. So conditioning on both initial and final locations, the probability of each path is 1/N, where N is the number of such paths.

Now suppose you are on the negative side of the time axis. Pick a path of length n going from i_0 to i_n. Let x be the number of (forward) jumps of size +2 in this path, and let y be the number of (forward) jumps of size -1. Then x + y = n and 2x - y = d := i_n - i_0. Conditioning only on the final location, this path has probability

(c/2)^y(1/(2c^2))^x = 2^{-n}c^{-d}.

This is true for all such paths. Hence, conditioning on both the initial and final locations, the probability of each path is 1/N, where N is the number of such paths.

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.

The constant c can be determined from the relations

c/2 + 1/(2c^2) = 1 and c > 0.

The solutions are c = 1 and c = (1 + \sqrt{5})/2. If c = 1, then we have a process for which the fraction of missed sites is the same on both sides of the time axis. If c = (1 + \sqrt{5})/2, then we do not. This is the ambiguity I was (perhaps unsuccessfully) trying to describe.
Reply With Quote