Archive for reflection principle

random walk on a torus [riddle]

Posted in Books, Kids, pictures with tags , , , , , , , , , on September 16, 2016 by xi'an

Galgate, Lancastershire, July 19, 2011The Riddler of this week(-end) has a simple riddle to propose, namely given a random walk on the {1,2,…,N} torus with a ⅓ probability of death, what is the probability of death occurring at the starting point?

The question is close to William Feller’s famous Chapter III on random walks. With his equally famous reflection principle. Conditioning on the time n of death, which as we all know is definitely absorbing (!), the event of interest is a passage at zero, or any multiple of N (omitting the torus cancellation), at time n-1 (since death occurs the next time). For a passage in zero, this does not happen if n is even (since n-1 is odd) and else it is a Binomial event with probability

{n \choose \frac{n-1}{2}} 2^{-n}

For a passage in kN, with k different from zero, kN+n must be odd and the probability is then

{n \choose \frac{n-1+kN}{2}} 2^{-n}

which leads to a global probability of

\sum_{n=0}^\infty \dfrac{2^n}{3^{n+1}} \sum_{k=-\lfloor (n-1)/N \rfloor}^{\lfloor (n+1)/N \rfloor} {n \choose \frac{n-1+kN}{2}} 2^{-n}

i.e.

\sum_{n=0}^\infty \dfrac{1}{3^{n+1}} \sum_{k=-\lfloor (n-1)/N \rfloor}^{\lfloor (n+1)/N \rfloor} {n \choose \frac{n-1+kN}{2}}

Since this formula is rather unwieldy I looked for another approach in a métro ride [to downtown Paris to enjoy a drink with Stephen Stiegler]. An easier one is to allocate to each point on the torus a probability p[i] to die at position 1 and to solve the system of equations that is associated with it. For instance, when N=3, the system of equations is reduced to

p_0=1/3+2/3 p_1, \quad p_1=1/3 p_0 + 1/3 p_1

which leads to a probability of ½ to die at position 0 when leaving from 0. When letting N grows to infinity, the torus structure no longer matters and the probability of dying at position 0 implies returning in position 0, which is a special case of the above combinatoric formula, namely

\sum_{m=0}^\infty \dfrac{1}{3^{2m+1}}  {2m \choose m}

which happens to be equal to

\dfrac{1}{3}\,\dfrac{1}{\sqrt{1-4/9}}=\dfrac{1}{\sqrt{5}}\approx 0.4472

as can be [unnecessarily] checked by a direct R simulation. This √5 is actually the most surprising part of the exercise!

morning run

Posted in pictures, Running with tags , , , on April 14, 2016 by xi'an

morninrun

The reflection principle

Posted in Books, Statistics with tags , , , , on February 7, 2010 by xi'an

In the weekend magazine of Le Monde, there always is one mathematical puzzle that often is easy to solve but sometimes is harder (like the puzzles involving arcane triangular geometry!) and occasionally just impossible (because the puzzle is missing one crucial assumption). The puzzle of this week is a direct application of the reflection principle exposed in Chapter III of Feller’s An Introduction to Probability Theory and Its Applications, Vol. 1, which is my favourite probability book. (More precisely, the answer is (almost) given in problem 1, page 95 of this book.)

Given a sequence of 2n heads and tails ending with exactly n heads, what is the probability that the sequence always remained in favour of heads, i.e. that the number of heads was larger than or equal to the number of tails from trial one to trial 2n? The number of non-negative paths of length 2n ending up in zero is the same as the number of (strictly) positive paths of length 2n+1 ending up in one (see Figure 1, page 69, in Feller). Now, by the reflection principle (Feller, Lemma, page 72), this number is

\dfrac{N_{2n+1-1,1-1}-N_{2n+1-1,1+1}}{N_{2n,0}} with N_{n,x}=\displaystyle{{n\choose \frac{n+x}{2}}}

being the number of paths of length n ending up in x (and N_{2n,2} being the number of paths hitting the zero value at least once after the starting time). The probability of a non-negative sequence is therefore

\mathbb{P}(S_t\ge 0\,,\,1\le t\le 2n\mid S_{2n}=0) = \dfrac{1}{(n+1)}.

This has a potential connection with Laplace’s succession rule, but I cannot make it straight away because the underlying events of not visiting -1 are not independent…

If you want to check this by simulation, a simple R program is

Nsim=10^6; n=4
cont=0;gain=0
while (gain<Nsim){
vale=cumsum(sample(c(-1,1),2*n,rep=TRUE))
gain=gain+(vale[2*n]==0)
cont=cont+(vale[2*n]==0)*(min(vale)>-1)
}
print(cont/Nsim)

If you have never read An Introduction to Probability Theory and Its Applications, Vol. 1, you should consider doing it: it makes for a very pleasant read, while making combinatorics enjoyable and it also constitutes a wealth of problems that I use extensively when teaching at Polytechnique.