View Single Post
  #1  
Old 11-27-2007, 09:56 PM
pzhon pzhon is offline
Senior Member
 
Join Date: Mar 2004
Posts: 4,515
Default Random walk on a symmetric interval

I stumbled on an amusing fact about random walks. Does it agree with your intuition?

Suppose you play a freezeout where you and your opponent start with n chips each. You wager a chip at a time, winning with probability p. Claim: Whether you win is independent of the time it takes to complete the freezeout. That is, the conditional probability that you win in t steps does not depend on t (when it makes sense). It's always equal to the probability of winning overall. In particular, the probability of winning is the probability of winning given that the freezezout is over in n steps: p^n / (p^n + (1-p)^n).

The same is true for Brownian motion with drift.

Here is a quick proof for the discrete version: The reflection of any path to victory in t steps is a path to defeat, and vice versa. This bijection changes the probability of a winning path by changing n extra victories to defeats, which multiplies the probability by ((1-p)/p)^n, so the probability of losing is ((1-p)/p)^n times the probability of winning. [img]/images/graemlins/diamond.gif[/img]

The analogous statement is false for asymmetric intervals. If your friend plays a (limit) freezeout against someone, and you see that at some point, your friend is ahead, then you do get some information about the outcome as you wait (without watching).
Reply With Quote