The reflection principle

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.

3 Responses to “The reflection principle”

  1. […] Monde puzzle The puzzle in Le Monde is quite straightforward (!) this weekend: it can be rewritten as to figure out the […]

  2. There is a nice paper by MARC RENAULT,
    “Four Proofs of the Ballot Theorem”,
    about this problem and some generalizations.

    I gave it to my students in the Stochastic Processes course and three out of ten solved it

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 717 other followers