## random walk on a torus [riddle]

Posted in Books, Kids, pictures with tags , , , , , , , , , on September 16, 2016 by xi'an The 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!

## no U-turn sampler [guest slides]

Posted in Statistics with tags , , , , , on April 17, 2013 by xi'an

Yesterday at the “Bayes in Paris” reading group, my student Marco Banterle presented his analysis of the NUTS paper by Marc Hoffmann and Andrew Gelman I discussed on the ‘Og a while ago. Here are his slides, which could have kept occupied for the whole afternoon, had not Michael started his course one hour later!