\documentclass[10pt,openright,makeidx,twoside]{article}
\usepackage{geometry}
\geometry{verbose,a4paper,tmargin=0.5in,bmargin=1in,lmargin=1in,rmargin=1in}
\usepackage{epic,eepic}
%\usepackage{aeguill} % au lieu de [T1]{fontenc}
%\usepackage[cyr]{aeguill} % si pas de fontes polonaises !
%dvips -Pcmz essai.dvi -o % m'expliquer pourquoi ps2pdf donne un meilleur pdf
%\usepackage{times}
%\usepackage{utopia}
%\usepackage{helvet}
\usepackage{charter}
%\usepackage{newcent}
%\usepackage{bookman}
%\usepackage{avant}
%\usepackage{palatino}
%\usepackage{chancery}
\usepackage{fancybox,epsfig,array}
\usepackage[sumlimits,namelimits]{amsmath}
\usepackage{amssymb,amsfonts,amsxtra,eucal,multicol,indentfirst}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage[francais]{babel}
\usepackage[dvips]{graphicx}
%\usepackage[dvips]{color}
%\usepackage[pdftex]{graphicx}
%\pdfcompresslevel=9
%\usepackage{psnfss} % charge les polices postscript
\markboth{Allumettes de Banach}{Probabilités}
\pagestyle{myheadings}
\usepackage{minitoc}
\usepackage{enumerate}
\usepackage{hyperref}

\makeindex 
\newcounter{exemples}[section]
\newcounter{remarques}[section]
\newtheorem{axiom}{Axiome}
\newtheorem{theorem}{Propriété}[section]
\newtheorem{lemma}[theorem]{Lemme}
\newtheorem{definition}[theorem]{Définition}
\newtheorem{example}[exemples]{Exemple}
\newtheorem{remark}[remarques]{Remarque}
\title{Les allumettes de Banach}
\date{}
\begin{document}
\def\d{\displaystyle}
\def\comment#1{}
\def\Comment#1{#1}
\def\note{\footnote{Ce texte est différent de l'énoncé classique. Habituellement l'arrêt n'a lieu qu'au moment où l'on ouvre une boîte vide (cf. cas 2). Les espérances mathématiques des deux problèmes sont liées par la relation $E_2(n)=E(n+1)-1$.}}

\parindent=0pt
\maketitle

\abstract{

Ce document accompagne la \href{http://jeux-et-mathematiques.davalan/proba/allu/index.html}{page~Web}  consacrée aux simulations du problème des deux boîtes d'allumettes de Banach.\\
On pourra comparer les valeurs obtenues lors de ces simulations aux valeurs théoriques calculées ci-dessous.\\
Le problème modifié est étudié en premier et la solution est trouvée par deux logiciels de calcul symbolique MuPAD et Maxima.\\

}

\section{Problème modifié (cas 1)}
\subsection{Énoncé.}
Banach,\footnote{Ce texte est différent de l'énoncé classique. Habituellement l'arrêt n'a lieu qu'au moment où l'on ouvre une boîte vide (cf. cas 2). Les espérances mathématiques des deux problèmes sont liées par la relation $E_2(n)=E(n+1)-1$.}
qui était fumeur, avait deux boîtes d'allumettes, l'une dans la poche gauche, l'autre dans la poche droite.\\
Chaque fois qu'il allumait sa pipe, il puisait au hasard dans l'une des boîtes.
Immanquablement, au bout d'un certain temps, il prenait la dernière allumette 
d'une boîte.\\
On suppose que les deux boîtes sont changées simultanément et qu'elles contiennent initialement le même nombre \( n\) d'allumettes.\\
Quel est, en moyenne, le nombre d'allumettes restantes, dans l'autre boîte, dès que l'une est vide ?\\
\begin{figure}[h]
\hspace*{0mm}\centerline{\epsfig{figure=Banach3.eps,height=8cm,clip=}}
\begin{center}
\caption{{\it Simulations}}
\label{fig:boites}
\end{center}
\end{figure}

\subsection{Solution}
\begin{figure}[h]
\Comment{
\centerline{
\setlength{\unitlength}{1mm}
%
{
\begin{picture}(40,40)(0,0)
\thicklines
\multiput(20,0)(2.5,2.5){8}{\path(0,0)(-20,20)}
\multiput(20,0)(-2.5,2.5){8}{\path(0,0)(20,20)}
\put(20,0){\circle*{2}}
\put(32.5,27.5){\circle*{2}}
\put(30,25){\circle{2}}
\put(34,27){$(n, n-p)$}
\put(41,19){$(n,0)$}
\put(0,0){Gauche}
\put(22,0){$(0,0)$\ Droite}
%\put(30,0){Droite}
\end{picture}
}
}
}
\comment{
\begin{center}
\includegraphics[height=5cm]{quad.png}
\end{center}
}
\def\N{{\mathbb N}}
\caption{{\it Marche aléatoire dans un carré de $\N\times\N$}}
\label{fig:Marche}
\end{figure}
En notant G $=(0,1)$ ou D$=(1,0)$ le retrait d'une allumette de la boîte gauche ou droite, les 
événements sont les mots de la forme DGGDGDDDGD...GDG ou les chemins (Fig: \ref{fig:Marche}) correspondants sur le quadrillage depuis l'origine $(0,0)$ jusqu'à l'un des bords
supérieurs du quadrillage ci-dessus, $(n,n)$ excepté.\\
Lorsqu'il reste $p$ allumettes dans l'une des boîtes et aucune dans l'autre,
ces suites ont pour longueur \( n+ (n-p)\).\\
La lettre  de droite du mot (la dernière lettre écrite) est G ou  D selon que la boîte vide est celle de gauche ou de droite.\\
Lorsque la dernière lettre du mot est G (resp. D), les suites contiennent
$n$ fois la lettre G (resp. D) et  $n-p$ fois l'autre lettre D (resp. G).\\
Il faut tenir compte du fait que dans chaque cas la lettre finale du mot
est imposée.
Le nombre de telles suites est dans chacun des deux cas le
nombre de combinaisons de $n-1$ lettres parmi $2n-p-1$.\\
Chacune de ces suites, de longueur $2n-p$ est obtenue
avec une probabilité égale à $\d 2^{-(2n-p)}$.\\
L'espérance mathématique $E(n)$ est donc égale à
\[ \d E(n) = 2\times \sum_{p=1}^{p=n}  p\times\frac {\tbinom{2n-p-1}{n-1}}{2^{2n-p}}
\d = \sum_{p=1}^{p=n} p\times\frac {\tbinom{2n-p-1}{n-1}}{2^{2n-p-1}}\]\label{identite}

\subsection{Calculs}
Quelques calculs effectués par le système de calcul formel très répandu \href{http://pari.math.u-bordeaux.fr/}{PARI$_{\text{GP}}$} sont indiqués à la figure (Fig: \ref{fig:PARI}). Des résultats de simulations sont donnés à la figure (Fig: \ref{fig:Simulations})

\begin{figure}[h]
\begin{verbatim}
               ? E(n)=sum(p=0,n,p*binomial(2*n-p-1,n-1)/2^(2*n-p-1));
               ? E(5)
               %1 = 315/128
\end{verbatim}
\caption{\it Calculs à l'aide de PARI/GP} 
\label{fig:PARI}
\end{figure}

\begin{figure}[h]
$$
\begin{array}{|r | c | c |}
\hline
n & E(n) & \text{moyennes de}\\
 & \text{(valeurs attendues)} & 50 \text{\ simulations} \\
\hline
5  &  2.4609375 &2.34\\
10 & 3.52394104  &3.34\\
20 & 5.014827505  &4.38\\
30 & 6.154690381  &5.42\\
40 & 7.114230302  &6.9\\
50 & 7.958923739  &7.98\\
\hline
\end{array}$$
\caption{{\it Valeurs obtenues lors des simulations}}
\label{fig:Simulations}
\end{figure}

\subsection{Expression sous la forme d'un produit de fractions}

On peut montrer que \( \d\frac{E(n+1)}{E(n)} =\frac{2n+1}{2n}=1+\frac{1}{2n}\)\\
Les algorithmes permettant d'obenir une formule close pour l'identité (\ref{identite}) sont décrits dans le livre \href{http://www.cis.upenn.edu/~wilf/AeqB.html}{A=B} de \href{http://mat.fmf.uni-lj.si/osebje/profesorji/Petkovsek.html}{Marko~Petkovsek}, \href{http://www.cis.upenn.edu/~wilf/index.html}{Herbert~Wilf} et \href{http://www.math.temple.edu/~zeilberg/}{Doron~Zeilberger}.\\
On obtient alors très facilement l'espérance mathématique ci-après (\ref{fig:Esperance}).
\begin{figure}[h]
\[
\begin{array}{|c| c | c | c | c | c | c |}
\hline
n & 1 & 2 & 3 & 4 & 5 & 6\\
\hline
E(n)=\frac{1.3.5.7...(2n-1)}{1.2.4.6...(2n-2)} & 1 & \frac{3}{2} & \frac{15}{8}&\frac{35}{16}&\frac{315}{128}&\frac{693}{256}\\
\hline
\end{array}
\]
\caption{{\it Espérance mathématique}}
\label{fig:Esperance}
\end{figure}
\begin{figure}[h]
{\small
\begin{verbatim}
              *----*    MuPAD 2.0.0 -- The Open Computer Algebra System
              ...
              >> ?sum
              sum -- definite and indefinite summation
              ...
              Background
               o The function sum implements Abramov's algorithm for rational functions,
                 Gosper's algorithm for hypergeometric functions, and Zeilberger's
                 algorithm for the definite summation of holonomic functions.
              ...
              >> a(n):=sum(p*binomial(2*n-p-1,n-1)/2^(2*n-p-1),p=0..n)
                                                 n
              (4 n binomial(2 n - 1, n - 1) + 4 2  binomial(n - 2, n - 1) -
                   n                            2 n
              4 n 2  binomial(n - 2, n - 1)) / 2
              >> expand((1-n)*binomial(n - 2, n - 1))
                                                   0
\end{verbatim}
}
\caption{{\it Calcul de l'espérance par MuPAD 2.0.0}}
\label{fig:MuPAD}
\end{figure}\\

\begin{figure}[h]
\vskip0.5cm
{\small
\begin{verbatim}
              Maxima 5.9.0 http://maxima.sourceforge.net
              ...
              (C1) describe(nusum);
              Info from file /usr/local/info/maxima.info:
               - Function: NUSUM (exp,var,low,high)
                   performs indefinite summation of exp with respect to var using a
                   decision procedure due to R.W. Gosper.  exp and the potential
                   answer must be expressible as products of nth powers, factorials,
                   binomials, and rational functions.  The terms "definite" and
                   "indefinite summation" are used analogously to "definite" and
                   "indefinite integration".  To sum indefinitely means to give a
                   closed form for the sum over intervals of variable length, not
                   just e.g. 0 to inf.  Thus, since there is no formula for the
                   general partial sum of the binomial series, NUSUM can't do it.
              ...
              (C2) nusum(p*binomial(2*n-p-1,n-1)/2^(2*n-p-1),p,0,n);

              Dependent equations eliminated:  (1)
                                       4 n BINOMIAL(2 n - 1, n - 1)
              (D2)                     ----------------------------
                                                    2 n
                                                   2
\end{verbatim}
}
\caption{{\it Calcul de l'espérance par Maxima}}
\label{fig:Maxima}
\end{figure}


Les numérateurs et dénominateurs successifs sont les suites \href{http://www.research.att.com/projects/OEIS?Anum=A001803}{A001803} et \href{http://www.research.att.com/projects/OEIS?Anum=A046161}{A046161} de l'\href{http://www.research.att.com/~njas/sequences/Seis.html}{Encyclopédie} des suites entières de Sloane. La suite \href{http://www.research.att.com/projects/OEIS?Anum=A002457}{A002457} correspond à $4^{n-1} E(n)$ qui est aussi égal à $\d \frac{(2n-1)!}{(n-1)!^2}$.\\
(On trouvera quelques références sur le site, en particulier les marches aléatoires sont évoquées).\\
À partir de la somme \(\d E(n)=\sum_{p=0}^{p=n} p\times\frac {\tbinom{2n-p-1}{n-1}}{2^{2n-p-1}}\), les logiciels de calcul symboliques \href{http://www.mupad.de/}{MuPAD} (Fig: \ref{fig:MuPAD}) et \href{http://maxima.sourceforge.net/}{Maxima} (Fig: \ref{fig:Maxima}) calculent l'expression \( \d E(n)=\frac{4n\tbinom{2 n - 1}{ n - 1}}{2^{2n}} =4^{-(n-1)}\frac{(2n-1)!}{(n-1)!^2}\).\\
% \[ {{4\,n\,{2\,n-1\choose n-1}}\over{2^{2\,n}}}\leqno{\tt (D1)}\]

%\( \d E(n)=\frac{1.3.5.7\ldots(2n-1)}{1.2.4.6\ldots(2n-2)} =
%\frac{1.3.5.7\ldots(2n-1)\times 2.4.6\ldots (2n-2)}{(2.4.6\ldots(2n-2))^2}
%=\frac{(2n-1)!}{(2^{n-1}\times (n-1)!)^2}=\frac{(2n-1)!}{4^{n-1}\times (n-1)!^2}\).
\label{identite2}\( \d  E(n)=\frac{(2n-1)!}{4^{n-1}\times (n-1)!^2}
= \frac{(2n-1)!}{(2^{n-1}\times (n-1)!)^2}
= \frac{1.3.5.7\ldots(2n-1)\times 2.4.6\ldots (2n-2)}{(2.4.6\ldots(2n-2))^2}
= \frac{1.3.5.7\ldots(2n-1)}{1.2.4.6\ldots(2n-2)}\).

%\comment{
\subsection{Fonction génératrice}
Comme \(\d \frac{1}{\sqrt{1-x^2}}=1+\frac{1}{2}x^2+\frac{1.3}{2.4}x^4+\frac{1.3.5}{2.4.6}x^6+\ldots+\frac{1.3.5\ldots(2n-1)}{2.4.6\ldots2n}x^{2n}+\ldots\) \\

on trouve aisément à l'aide d'une dérivation et une multiplication par \( x^2\) que\\
\( \d x^2\:(1-x^2)^{\frac{-3}2} = 1\:x^2 + \frac 3 2 x^4 + \frac{15}8 x^6 + \frac{35}{16}x^8 + \frac{315}{128}x^{10} + \frac{693}{256}x^{12} +\ldots+\frac{3.5.7\ldots(2n-1)}{2.4.6\ldots(2n-2)}x^{2n} +\ldots\),\\
\( \d x\:(1-x)^{\frac{-3}2} = 1\:x + \frac 3 2 x^2 + \frac{15}8 x^3 + \frac{35}{16}x^4 + \frac{315}{128}x^{5} + \frac{693}{256}x^{6} +\ldots+\frac{3.5.7\ldots(2n-1)}{2.4.6\ldots(2n-2)}x^{n} +\ldots\)\\
dont le coefficient de $x^n$ est $E(n)$.\\
\( \d x\:(1-x)^{\frac{-3}2}\) est donc la fonction génératrice de l'espérance $E(n)$.
%}
\section{Problème classique (cas 2)}
\subsection{Espérance mathématique déduite du cas précédent}
Si on ajoute une allumette (fictive) dans chaque boîte on passe du problème classique au problème modifié, il suffit de retrancher $1$ de l'espérance $E(n+1)$ du problème modifié à $n+1$ allumettes par boîte, pour obtenir celle $E_2(n)=E(n+1)-1$ du problème classique à $n$ allumettes. L'allumette fictive étant par exemple celle que l'on (ne) prend (pas) à la dernière ouverture de la boîte.\\

\( \d E_2(n)=E(n+1)-1 = -1 +\sum_{p=1}^{p=n+1} p\times\frac {\binom{2n-p+1}{n}}{2^{2n-p+1}} =
\sum_{p=1}^{p=n+1} (p-1)\times\frac {\binom{2n-p+1}{n}}{2^{2n-p+1}}
=\sum_{k=0}^{k=n} k\:\tbinom{2n-k}{n}\:2^{-(2n-k)}\)\\
(La somme des probabilités est $1$).\\
On obtient aussi \( \d E_2(n)= E(n+1)-1=\frac{1.3.5.7...(2n+1)}{1.2.4.6...(2n)}-1 =\frac{2n+1}{2^{2n}}\:\tbinom{2n}{n}-1\) qui est bien plus simple que
la relation de récurrence 
\( \d E_2(n) = \frac{2n+1}{2n}\,E_2(n-1)+\frac{1}{2n}\).
\subsection{Solution directe}
En considérant les chemins du quadrillage (Voir \ref{fig:Marche}), on montre d'abord que \( \d E_2(n)=\sum_{k=0}^{k=n} k\:\tbinom{2n-k}{n}\:2^{-(2n-k)}\)\\
On considère la série \( \d \sum_{i \geq 0} z^i = \frac{1}{1-z} \). \\
En dérivant $n$ fois on obtient 
\( \d \sum_{i \geq 0} \tbinom{n+i}{n} z^i = \frac{1}{(1-z)^{n+1}} \).\\
Puis en faisant $i=n-k$ et $\d z=\frac 1 2$ on a
\( \d \sum_{k \geq 0}^n \tbinom{2n-k}{n} 2^{-(n-k)} = 2^{n+1} \).\\

\subsection{Fonction génératrice}
La fonction génératrice est \(\d (1-x)^{\frac{-3}2}-(1-x)^{-1} =
\frac 1{(1-x)\sqrt{1-x}}-\frac 1{1-x}=\frac 1{1-x}\left (\frac 1{\sqrt{1-x}} -1\right)\).\\
Les espérances $E_2(n)$ sont les coefficients des $x^n$ dans le développement en série \(\d\sum_n E_2(n)x^n\) de cette fonction génératrice.
\begin{figure}[t]
\begin{verbatim}
        ? taylor((1-x)^(-3/2)-(1-x)^(-1),x)
        %1 = 1/2*x + 7/8*x^2 + 19/16*x^3 + 187/128*x^4 + 437/256*x^5 +
        1979/1024*x^6 + 4387/2048*x^7 + 76627/32768*x^8 + 165409/65536*x^9 +
        707825/262144*x^10 + 1503829/524288*x^11 + 12706671/4194304*x^12 +
        26713417/8388608*x^13 + 111868243/33554432*x^14 +
        233431331/67108864*x^15 + O(x^16)
\end{verbatim}
\caption{{\it Fonction génératrice}}
\label{fig:Generatrice}
\end{figure}

Un calcul de PARI$_{\text{GP}}$ (Fig: \ref{fig:Generatrice}) donne bien les valeurs attendues.

\subsection{Fonction génératrice d'une loi de probabilité}
Au chapitre 8 sur les Probabilités discrètes du livre 
\href{http://www.calindex.com/livre-sciences-techniques-mathematiques-mathematiques-par-matieres-mathematiques-informatique-mathematiques-concretes.html}{Mathématiques concrètes} de R.L. Graham , Donald E. Knuth , O. Patashnik  le problème est résolu à l'exercice 48 en considérant 
a) une fonction génératrice double \(\d P(w,z)=\sum_{m,n}p_{m,n}w^mz^n\) où $p_{m,n}$ est la probabilité que les deux boîtes soient vides lorsque la première choisie est vide (les deux boîtes contenant initialement $m$ et $n$ allumettes), 
b) la probabilité $\d P_{k,m,n}$ que la seconde boîte contienne exactement $k$ allumettes lorsque la première choisie est vide.\\
La question c) permet d'obtenir la formule close 
\(\d \sum_{k} k\:P_{k,m,n} = \frac{2n+1}{2^{2n}}\:\tbinom{2n}{n}-1\) allumettes dans la seconde boîte en utilisant la propriété 
\(\d\sum_{k\geq m}\binom{m+k}{k}2^{-k}=2^m\).\\
Les auteurs signalent que l'espérance vaut \(\d 2\sqrt{n/\pi}-1+\mathrm O(n^{-1/2})\)  (Fig: \ref{fig:asympt}). 

\begin{figure}[h]
$$
\begin{array}{|r | c | c |}
\hline
n & E_2(n) & 2\sqrt{n/\pi}-1 \\
 \hline
10& 2.70014& 2.56825 \\
50& 7.03851& 6.97885 \\
100& 10.326& 10.2838 \\
200& 14.9876& 14.9577 \\
300& 18.5685& 18.5441 \\
400& 21.5887& 21.5676 \\
500& 24.2502& 24.2313 \\
600& 26.6568& 26.6395 \\
700& 28.8701& 28.8541 \\
800& 30.9303& 30.9154 \\
900& 32.8655& 32.8514 \\
1000& 34.6959& 34.6825 \\
\hline
\end{array}$$
\caption{{\it Valeurs approchées}}
\label{fig:asympt}
\end{figure}
%\newpage
{\small
\tableofcontents
}
%
{\small
\listoffigures
}
%\printindex
\end{document}
