Course à l'égalité

Rouletabille

J'ai une pièce de monnaie truquée, la probabilité de "Face" est $p$, avec $0<p\leq \frac{1}{2}$. Je la lance plusieurs fois de suite, jusqu'à ce que j'obtienne autant de "Face" que de "Pile". La probabilité que cet événement se produise est si je ne me trompe : $2p$. Cela signifie que si $p = \frac{1}{2}$ ceci se produira quasi-certainement, mais non si $p < \frac{1}{2}$, ce qui est au fond assez naturel.
J'ai une démonstration de ceci, mais elle n'est pas si simple, et la simplicité du résultat me fait penser qu'il y aurait peut-être quelque chose de plus simple. Qu'en dites-vous ?
Bonne soirée.
06/02/2015

Siméon

Bonsoir,

J'obtiens le même résultat que toi, mais je n'ai pas de preuve simple non plus. J'ouvrirai un livre sur les marches aléatoires quand j'aurai le temps.

Siméon

Sauf erreur, le résultat se déduit simplement du problème du ballot. Joli problème en tout cas !

Rouletabille

Le "problème du ballot" se dénomme en français si je ne me trompe "problème du scrutin". Il n'est lui-même pas si simple et fait intervenir les nombres de Catalan, et c'est ainsi que j'ai procédé. S'il n'y a pas plus simple, tant pis. Je vais en faire un problème de colle puisque désormais, pour la première fois dans l'histoire, nous avons des probas au programme des CPGE scientifiques.
Bonne journée.
R.

JLT

Le cas $p<1/2$ doit se déduire de la convergence de la série $\sum \dfrac{(2n)!}{(n!)^2}(p(1-p))^n$ mais ce n'est pas très simple.

joel_5632

bonjour

C'est une marche aléatoire

Une personne jette une pièce, si elle tombe sur pile la personne avance d'un pas, si c'est face, elle recule d'un pas.

Quelle est la probabilité que cette personne revienne à son point de départ (équivalent à la probabilité qu'elle obtienne autant de pile que de face) ?

si p = 1/2, la marche est symétrique, alors oui cette probabilité est égale à 1

Il y a une preuve dans ce document:
marchesZ

Rouletabille

En effet c'est ainsi que j'ai procédé. C'est lié au dénombrement de trajets sous-diagonaux sur un quadrillage, avec le magnifique principe de réflexion de Désiré André, et les nombres de Catalan, qui sont sans doute les nombres qui ont le plus d'interprétations combinatoires. Cela marche aussi pour p=1/2. Ces expertises me donnent à penser qu'on ne peut simplifier ceci.

Reste à en faire un sujet de colle. L'imagerie en dénombrement de trajets s'y prête mal, aussi vais-je trouver autre chose, je vous raconterai.

C'est en tous cas un exemple où l'on décrit une suite d'expériences aléatoires avec une condition d'arrêt, mais où celle-ci n'est pas quasi-certaine. Cela peut servir je pense.

Bonne journée de froidure.
R.

Siméon

La preuve dite "par réflexion" est très simple, très courte, et n'utilise pas explicitement les nombres de Catalan. Cf Wikipedia.

Pour rappel : http://webspace.ship.edu/msrenault/ballotproblem/French Andre.pdf

depasse

Bonsoir

Tout content d'avoir imaginé une méthode élémentaire pour résoudre ce problème, je suis fort déçu qu'elle ne me conduise pas au résultat annoncé: $2p$.
Si vous pouviez jeter un oeil et pointer où ça cloche, vous me rendriez service!

Je reprends la métaphore des montées ($P$) et descentes($F$). Je pars de la mer, je franchis $s$ sommets, je reviens à la mer. A la fin je multiplie par $2$ vu que la montagne se reflète dans la mer.

Soit $P^{p_1}F^{f_1}P^{p_2}F^{f_2}......P^{p_s}F^{f_s}$ ma montagne avec ses $s$ sommets; l'application qui l'envoie sur le couple
$(P^{f_1}F^{f_1}, P^{p_1-f_1+p_2}F^{f_2}......P^{p_s}F^{f_s})$ est bijective. On peut donc dire qu'une montagne de $s$ sommets est une montagne de $1$ sommet suivie d'une montagne de $s-1$ sommets.

Soit $p_s$ la probabilité d'une montagne à $s$ sommets.
On a $p_s=Sp_{s-1}$ où $S$ est la somme de la série géométrique de raison $p(1-p)$ privée du $1$.

La probabilité $prob$ recherchée est le double de la somme des $p_s$ ($s>0$) qui forment une progression géométrique de raison $S$ privée de $1$, soit
$prob=2\frac{S}{1-S}$ et $S=\frac{p(1-p)}{1-p(1-p)}$,

d'où $S=\frac{2p(1-p)}{1-2p(1-p)}$

Cordialement
Paul

aléa

C'est un problème de barrière classique: la probabilité cherchée est $p+(1-p)x_{-1}$, où $x_n$ est la probabilité qu'une marche aléatoire biaisée partant de $n$ touche $0$ avant d'aller à en $-\infty$.

On a la récurrence $x_n=px_{n+1}+(1-p)x_{n-1}$. Avec les conditions au bord $x_0=1$ et $\lim_{n\to -\infty} x_n=0$, on a
$x_n=(\frac{1-p}{p})^n$, d'où $x_{-1}=\frac{p}{1-p}$ et la proba cherchée est $2p$.

Rouletabille

Il est bien-connu que le nombre de suites de $F$ et $P$ avec $k$ fois $F$ et $h$ fois $P$ est : $(_{~~k}^{k+h})=(_{~~h}^{k+h})$.
Pour notre problème, il faut trouver, pour $k>h$, le nombre $c_{k,h}$ de ces suites telles que le nombre de $F$ soit toujours supérieur au nombre de $P$ au cours de la succession des termes. Par exemple $c_{4,2}=5$ car on a les suites : $FFFFPP, FFFPFP, FFFPPF, FFPFFP, FFPFPF$.

La plus jolie méthode pour traiter ce genre de problème est d'interpréter une suite de $F$ et $P$ comme un trajet sur un quadrillage, $F$ vers la droite et $P$ vers le haut (faire la figure, moi je ne sais). Si $A$ et $B$ sont deux points du quadrillage, de coordonnées $(x_A,y_A)$ et $(x_B,y_B)$, avec $x_{A}\leq x_{B}$ et $y_{A}\leq y_{B}$, le nombre de trajets $AB$ est : $(_{~~~~~~~x_{B}-x_{A}}^{x_{B}-x_{A}+y_{B}-y_{A}})=(_{~~~~~~~y_{B}-y_{A}}^{x_{B}-x_{A}+y_{B}-y_{A}})$.
Si l'on dénomme "diagonale" la droite $\Delta$ d'équation $y=x$, alors $c_{k,h}$ est le nombre de trajets sous-diagonaux joignant l'origine au point $B$ de coordonnées $(k,h)$. C'est en fait le nombre de ces trajets sous-diagonaux joignant le point $A(1,0)$ à ce point $B(k,h)$.
Et c'est ici qu'intervient la belle idée de Désiré André.
Nous savons dénombrer tous les trajets $AB$, leur nombre est : $(_{~~k-1}^{k+h-1})$. Cherchons à dénombrer ces trajets qui coupent la diagonale $\Delta$. À chacun d'eux, associons le trajet obtenu en remplaçant la partie de ce trajet, située entre le point $A$ et sa première intersection avec $\Delta$, par le symétrique de cette partie par rapport à $\Delta$. Le point symétrique de $A$ par rapport à $\Delta$ est le point $A'(0,1)$. On définit ainsi une bijection involutive entre entre les trajets $AB$ rencontrant $\Delta$ et les trajets $A'B$ rencontrant $\Delta$. Mais les les trajets $A'B$ rencontrant $\Delta$, ce sont exactement les trajets $A'B$ tout court puisque $A'$ et $B$ sont de part et d'autre de $\Delta$. Leur nombre est donc : $(_{~~~~~k}^{k+h-1})$.
C'est un peu compliqué à expliquer ainsi, un dessin le montre mieux.
On en conclut : $c_{k,h}=(_{~~k-1}^{k+h-1})-(_{~~~~~~k}^{k+h-1})$.

Malheureusement, je ne pense pas qu'on puisse poser ceci tel quel à des étudiants dans le cadre d'un problème. On peut leur en faire un exposé et leur faire admirer le génie de Désiré André, on ne eut leur demander de redécouvrir ceci. Si l'on veut en faire un problème, il faut donc rédiger autrement l'énoncé.

discret

Une très bonne introduction aux chemins minimaux dont parle Rouletabille, avec les théorèmes d'André et de Chung-Feller, se trouve dans l'ouvrage de Louis Comtet, Analyse Combinatoire Tome Premier, PUF, 1970, pages 30-31.

P.2

Les étudiants de licence n'aiment pas tellement les ingénieuses méthodes combinatoires (moi non plus). Voici une solution plus proche de la théorie de la mesure. Soit $X_1,\ldots,X_n,\ldots$ iid de loi $\Pr(X_n=1)=p<1/2,\ \Pr(X_n=-1)=q=1-p$ et $S_n=X_1+\cdots+X_n.$ On admet la loi des grands nombres $S_n/n\rightarrow p-q$ presque sûrement, qui entraîne $S_n\rightarrow -\infty.$ On pose $T_i=\inf\{n; S_n=i\}$ pour $i=0,1$ avec $T_i=\infty$ si c'est vide. On pose $T_1(N)=\inf(T_1,N).$ Alors$$1=\mathbb{E}\left(\left(\frac{q}{p}\right)^{S_n}\right)=\mathbb{E}\left(\left(\frac{q}{p}\right)^{S_{T_1(N)}}\right)=a_N+\frac{q}{p}\Pr(T_1\leq N)$$ avec $a_N=\mathbb{E}\left(\left(\frac{q}{p}\right)^{S_{N}}1_{T_1>N}\right).$ Par convergence dominée $a_N\rightarrow 0$ puisque $T_1>N$ inplique $S_N\leq 0$ et puisque $S_N\rightarrow -\infty.$ Donc $\Pr(T_1<\infty)=p/q.$ Pour terminer $$\Pr(T_0<\infty)=\Pr(S_1=1)+\Pr(S_1=-1)\Pr(T_1<\infty)=p+q\times \frac{p}{q}=2p.$$

aléa

La preuve par réflexion est quand même la plus simple à mon avis. La voici en français moderne:

Soient $(X_n)_{n\ge 1}$ des variables aléatoires iid avec $p=P(X_1=1)=1-P(X_1=-1)$. On pose $S_n=X_1+\dots X_n$ et $T=\inf\{n\ge 1; S_n=0\}$. On suppose $p<1/2$.

Par un argument de symétrie $P(X_1=1,T=n)=(X_1=-1,T=n)$ pour tout $n$, d'où $P(X_1=1,T<+\infty)=(X_1=-1,T<\infty)$, d'où $P(T<+\infty)=2P(X_1=1,T<+\infty)$.

Mais la loi forte des grands nombres entraîne que $P(T<+\infty|X_1=1)=1$, d'où le résultat voulu.

Rouletabille

La Combinatoire n'est pas qu'un recueil de recettes ingénieuses, c'est une discipline mathématique à part entière, illustrée comme rappelle discret par Louis Comtet, et par bien d'autres mathématiciens (Claude Berge, Paul Erdös, ...). J'espère qu'il existe des secteurs de notre système d'enseignement où ses connaissances se transmettent, avec des étudiants et des professeurs qui l'apprécient.

Malheureusement ce n'est pas le cas des Classes Préparatoires aux Grandes Ecoles, dans le programme de qui la Combinatoitre est réduite à la portion congrue. C'est pourquoi il me semble inapproprié de proposer dans ces classes le raisonnement que j'ai décrit dans mon prédédent message, trop sophistiquée dans son imagerie géométrique.

On peut se rabattre sur la méthode suivante. Donnant toujours la même définition de $c_{k,h}$, on peut prouver sans mal que :
$c_{k,h}= c_{k,h-1}+ c_{k-1,h}$, $c_{k,k-1}= c_{k,k-2}$, $c_{k,0}=1$, ce qui permet de dresser rapidement le tableau à double entrée des $c_{k,h}$ dans des limites raisonnables. Et qui permet aussi de démontrer par récurrence la formule $ c_{k,h}=(_{~~k-1}^{k+h-1})-(_{~~~~~k}^{k+h-1})$. Mais si l'on peut ainsi prouver cette formule lorqu'on l'a, ceci ne dit pas comment la trouver ...

Ce tableau triangulaire des $c_{k,h}$ est parfaitement connu et labellisé : https://oeis.org/A009766, alors que les simples nombres de Catalan sont : https://oeis.org/A000108. Ce sont bien sûr les $c_{k,k-1}= c_{k,k-2}$.

Bon dimanche d'hiver.
08/02/2015

Rouletabille

Venons-en au problème posé initialement. Pour $n \in \mathbb N^*$, on cherche la probabilité $p_n$ pour que l'on ait $n$ "Face" et $n$ "Pile" au bout de $2n$ lancers et jamais auparavant. C'est la réunion des deux événements :
- au cours des $2n-1$ premiers lancers on a $n$ fois "Face", $n-1$ fois "Pile" et toujours plus de "Face" que de "Pile", et le dernier lancer donne "Pile" ;
- au cours des $2n-1$ premiers lancers on a $n$ fois "Pile", $n-1$ fois "Face" et toujours plus de "Pile" que de "Face", et le dernier lancer donne "Face".
Il en résulte : $p_{n}=2c_{n,n-1}p^{n}(1-p)^{n}$
Et rappelons : $c_{n,n-1}=(_{~n-1}^{2n-2})-(_{~~~n}^{2n-2})=\frac{(2n-2)!}{n!(n-1)!}=\frac{1}{n}(_{~n-1}^{2n-2})$, nombre de Catalan que nous noterons $c_n$.

La série entière $ \displaystyle f(t)=\underset{n=1}{\overset{+\infty }{\sum }}c_{n}t^{n}=\underset{n=1}{\overset{+\infty }{\sum }}\frac{(2n-2)!}{n!(n-1)!}t^{n}$ a un rayon de convergence égal à $\frac{1}{4}$ (ça tombe bien) et elle est normalement convergente sur $[-\frac{1}{4},\frac{1}{4}]$. Sa somme est : $f(t)=\frac{1}{2}(1-\sqrt{1-4t})$ pour $t \in [-\frac{1}{4},\frac{1}{4}]$ .
La probabilité que l'on arrive à obtenir autant de "Face" que de "Pile" au cours d'un nombre indéterminé de lancers est donc :
$ \displaystyle \underset{n=1}{\overset{+\infty }{\sum }}p_{n}=\underset{n=1}{\overset{+\infty }{\sum }}2c_{n}p^{n}(1-p)^{n}=2f(p(1-p))=2p$ si $0<p\leq \frac{1}{2}$.

On peut définir une variable aléatoire $X$ égale au nombre de lancers au bout desquels on a autant de "Face" que de "Pile", avec $X=0$ si ceci ne se produit pas.
Si $p=\frac{1}{2}$ alors $P(X=0)=0$, mais la variable aléatoire $X$ n'a pas d'espérance.
Si $0<p<\frac{1}{2}$ alors $P(X=0)=1-2p>0$, et la variable aléatoire $X$ a des moments de tous ordres, on peut s'amuser à calculer espérance et variance.

Voilà, c'est un cadeau pour mes collègues de Math. Spé., qui peuvent en faire un problème pour leurs élèves. Je ne sais si c'est écrit en français post-moderne, mais eux me comprendront je pense.

Bonne journée.
08/02/2015

[small]La Ballade en vieil langage Françoys
...........................................
Princes à mort sont destinez,
Et tous autres qui sont vivans :
Si sont courciez ou attinez,
Autant en emporte ly vens.[/small]

aléa

Bon, la loi des grands nombres n'est pas vraiment nécessaire.

$P(X_1=1,T<+\infty)=P(X_1=1)-P(X_1=1,T=+\infty)$.

Soit $\alpha>0$. Pour tout $n$, on a $P(X_1=1,T=+\infty)\le P(S_n\ge 0)=P(e^{\alpha S_n}\ge 1)\le E(e^{\alpha S_n})=f(\alpha)^n$, avec $f(\alpha)=pe^{\alpha}+(1-p)e^{-\alpha}$. $f(0)=1$ et $f'(0)=2p-1<0$, donc si on choisit $\alpha>0$ suffisamment petit, $f(\alpha)<1$ et c'est fini.

depasse

Bonsoir,

Je ne doute pas que je fais une erreur de raisonnement (ou de calcul) dans mon précédent message: Vos nombreuses preuves mènent incontestablement à $2p$.
Pour autant, je reste aveugle sur mon erreur et je me permets de vous embêter une seconde fois et d'espérer que vous me la situerez:-).

Paravent: JLT, dans son message, parle de $\sum
\dfrac{(2n)!}{(n!)^2}(p(1-p))^n$ qui me semble devoir être symétrique en $p$ et $1-p$ et donc indépendante du fait que $p$ soit plus petit ou grand que $1/2$, ce qui est aussi le cas de ma formule pour $prob$.

Merci beaucoup
Paul

JLT

Tu es sûr que ta bijection en est vraiment une ? De quel ensemble vers quel ensemble ?

depasse

Mon erreur est très vraisemblablement là où tu la devines: il ne me reste qu'à m'en persuader.
Grand merci pour ta rapide réponse.
Paul

depasse

Persuadé je suis!
merci
Paul

pldx1

Bonjour,

Voyons ce que l'on peut faire avec des moyens élémentaires. Pour commencer, l'équilibre ne peut se produire qu'au bout d'un nombre pair ($=2m$) de lancers. Si l'on considère la représentation arborescente du jeu de pile ou face standard, nous obtenons, au bout de $5$ étapes (=10 lancers), les pondérations: \[ \left[1,10,45,120,210,252,210,120,45,10,1\right] \] à partir de la pondération $\left[1\right]$. Cela s'appelle le triangle de Pascal.

Mais dans le présent problème, nous devons considérer, à chaque étape $j=1,2,3,4,5$, que le nombre central (soit $x_{j}$) correspond à une condition d'arrêt. Nous devons donc le remplacer par $0$ avant de continuer. Cette perturbation se propage à son tour selon le triangle de Pascal. Dans le cas $m=5$, gérer l'ensemble des perturbations revient donc à soustraire les pondérations suivantes: \[ \left(\begin{array}{r|crcccccccrr} x_{1} & 0 & 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 & 0\\ x_{2} & 0 & 0 & 1 & 6 & 15 & 20 & 15 & 6 & 1 & 0 & 0\\ x_{3} & 0 & 0 & 0 & 1 & 4 & 6 & 4 & 1 & 0 & 0 & 0\\ x_{4} & 0 & 0 & 0 & 0 & 1 & 2 & 1 & 0 & 0 & 0 & 0\\ x_{5} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{array}\right) \] chacune multipliée par le $x_{j}$ qui lui correspond.

On voit donc que $252=70x_{1}+20x_{2}+6x_{3}+2x_{4}+1x_{5}$. Bien entendu, cette remarque vaut pour chaque valeur de $m>0$ et nous avons donc la récurrence: \[ \forall m>0\::\:\binom{2m}{m}=\sum_{k=1}^{k=m}\binom{2k-2}{k-1}\, x_{k} \] Passons aux séries génératrices, c'est à dire posons: \begin{eqnarray*} s\left(z\right) & = & \sum_{k=0}^{k=\infty}\binom{2k}{k}\, z^{k}=1/\sqrt{1-4z}\\ g\left(z\right) & = & \sum_{k=1}^{k=\infty}x_{k}z^{k} \end{eqnarray*} La récurrence donne $s\left(z\right)\times g\left(z\right)=s\left(z\right)-1$ et donc g$\left(z\right)=1-\sqrt{1-4z}$.


Appelons $A$ (comme absorbant) l'évènement "l'équilibre s'est produit". On obtient sa probabilité en substituant $z=p\left(1-p\right)$ dans $g\left(z\right)$. Cela se simplifie (sous l'hypothèse $p<0.5$) et l'on obtient $Pr\left(A\right)$$=2p$. Si l'on utilise les formules usuelles et que l'on simplifie les radicaux (toujours sous l'hypothèse $p<0.5$), l'espérance, la variance et le facteur de forme de la variable "$m$ quand $A$ a lieu" sont: \[ \mu=\frac{1-p}{1-2p}\;;\;\sigma^{2}=\frac{p\left(1-p\right)}{\left(1-2\, p\right)^{3}}\ ;\ \frac{\mu^{2}}{\sigma^{2}}=\frac{\left(1-p\right)\left(1-2p\right)}{p} \] Si l'on préfère les expressions symétriques en $p$ et $q=1-p$, on a: \[ \mu=\frac{1+\left|p-q\right|}{2\left|p-q\right|}\ ;\ \sigma^{2}=\frac{pq}{\left|p-q\right|^{3}} \] Vérification amusante: "$m=1$ quand $A$ a lieu" devient quasi certain lorsque $p\rightarrow0$.

Évidemment, on peut aussi assaisonner la mayonnaise avec une pincée de boréliens, quelque gouttes de TCL et un zeste de l'ingrédient préféré du lecteur. On peut même expliciter les $x_{n}$ de façon à les identifier au cas où on les croiserait à nouveau.

Cordialement, Pierre.

Edit: ce n'était pas la meilleure idée possible de désigner l'état absorbant $A$ par la lettre $\sigma$, en conflit avec la notation usuelle de l'écart-type.

Rouletabille

Il me semble avoir résolu la question "avec des moyens élémentaires", sans le feu d'artifice(s) de loi des grands nombres, de théorie de la mesure, de convergence dominée, de TLC, de boréliens, et autres belles notions supérieures.

Il me semble bien avoir entendu parler de ce triangle de Pascal, merci, il me semble un peu savoir ce qu'est un arbre, mais je ne vois pas où vont cette "représentation arborescente", ces "pondérations", ces "perturbations" qui se "propagent" et qu'il faut "gérer" et pour ce faire "soustraire les pondérations suivantes". Je ne vois pas là de "moyens élémentaires", mais une panoplie de techniques qui ne me semblent pas du tout "élémentaires".

Je rappelle ma solution "avec des moyens élémentaires", et qui le sont vraiment. Soit $X$ le nombre de lancers au bout desquels on a autant de "Face" que de "Pile", en prenant $X=0$ si un tel événement ne se produit pas. En effet "l'équilibre ne peut se produire qu'au bout d'un nombre pair ($=2n$ ) de lancers" ( il me semblait bien l'avoir vu aussi ...), et pour tout $n\in \mathbb{N}^*$, on a : $P(X=2n)=2c_{n}p^{n}(1-p)^{n}$, où $c_{n}=(_{~n-1}^{2n-2})-(_{~~n}^{2n-2})=\frac{(2n-2)!}{n!(n-1)!}=\frac{1}{n}(_{~n-1}^{2n-2})$, qui est le nombre de Catalan, bien connu.

Au cas où ceci ne serait pas connu de certains, notamment de jeunes, j'ai donné des explications en détail dans plusieurs messages précédents. Une fois trouvée cette fonction de distribution, il est facile de répondre à toutes les questions qui peuvent se poser, comme probabilité d'atteindre l'égalité, espérance, variance.

Tout ceci peut se traiter avec le nouveau programme de CPGE scientifiques, ça c'est certain, et peut-être en prépa-HEC ou Veto en adaptant les arguments.

Bonne soirée.
09/02/2015

Barnabé5

Rouletabille, au lieu de ronchonner et de tout ramener à tes chères classes de spéciales, réjouis toi que ton intéressante question ait suscité plusieurs réponses. On est là pour s'amuser, non? Et si les moyens utilisés sont trop compliqués, il y a d'autres exemples: 14 euros dans ma poche et 9 pièces de 1 et 2 euros, combien de pièces de chaque? Vas tu protester parce que j'utilise un système de deux équations au lieu des raisonnements tordus qu'on nous faisait utiliser en 6ème (je suis très vieux)?

Rouletabille

@Barnabé

Si je signale le traitement possible de ce problème dans le cadre des classes prépas, c'est que professionnellement c'est le secteur que je connais et où j'interviens encore, bien que récemment septuagénaire.

De plus, c'est bien là ce me semble le cadre pour traiter ce problème d'une façon vraiment élémentaire avec le minimum de matériel mathématique.

J'aimerais savoir ce qu'on fait en fac, du moins avec les étudiants qui sont de vrais étudiants, qui ne sont pas là seulement pour le restau-U, la carte de séjour, et autres avantages. J'aimerais connaître les programmes des deux premières années, et même des suivantes pourquoi pas ? Je présume que cela change un peu d'une Université l'autre, mais dans des limites tout de même.

Par ailleurs si quelqu'un a un lien vers le programme actuel de l'agrégation, cela m'arrangerait.

J'ai posé ce sujet parce que c'est un sujet que j'ai sous le coude depuis de nombreuses années, et je n'avais jamais su comment le poser dans le cadre des programmes que j'ai enseignés dans les diverses classes qui m'ont été confiées. Je me suis décidé à en faire un sujet traitable en colle en Math Spé parce que nous avons désormais dans le même programme le calcul des probabilités, les séries entières et les équations différentielles. Par malheur c'est un peu faible côté Combinatoire, faiblesse qui est apparemment partagée par d'autres ... Mais bon, je leur ferai cadeau de la préparation combinatoire. Et je l'ai posé ici pour avoir l'expertise de collègues plus calés que moi en Calcul des Probabilités, pour voir si rien d'essentiel ne m'avait échappé. Ce qui semble bien le cas, merci à tous.

Bonne journée, encore maussade.
10/02/2015

jandri

Pour le programme de l'agrégation il suffit d'aller sur les sites.
site agrégation externe
programme agrégation externe

site agrégation interne
programme agrégation interne

Rouletabille

Merci à jandri pour les programmes d'agreg.
Pour en revenir aux contributions savantes précédentes, j'aimerais avoir des références bibliographiques qui me permettent de les connaître. Je présume qu'on trouve des choses sur les marches aléatoires dans l'ouvrage dont j'ai beaucoup entendu parler : De l'Intégration aux Probabilités, d' Olivier Garet et Aline Kurtzmann ;-), que je viens de me décider à acquérir, nonobstant le tiers provisionnel, puisque décidément c'est le seul moyen de le lire. Y trouverai-je des lueurs sur les "arborescences", leurs "pondérations", "perturbations" et leurs inquiétantes "propagations" ? Je verrai vendredi lorsqu'Amazon me livrera mon achat. Sinon, quelqu'un pourrait peut-être m'indiquer une source où ces intéressantes notions sont présentées, je verrai alors si c'est aussi "élémentaire" que ça.
Bonne journée.
R.

aléa

@Rouletabille: si tu mets ensemble les deux posts que j'ai faits, tu as une solution qui est complètement Bac+2, sans utiliser la loi forte des grands nombres.
Bien sûr, contourner la loi forte des grands nombres n'est pas naturel, mais découpé en questions, ça me semble très faisable.
Il faut peut être un peu guider les élèves pour voir la bijection entre
$\Omega_n^+=\{x\in\{-1,+1\}^n,\sum_{i=1}^n x_i=0\text{ et }\sum_{i=1}^j x_i>0\text{ pour }0<j<n\}$
et
$\Omega_n^-=\{x\in\{-1,+1\}^n,\sum_{i=1}^n x_i=0\text{ et }\sum_{i=1}^j x_i<0\text{ pour }0<j<n\}$.

Rouletabille

Encore un mot sur le problème.
Je rappelle qu'on a une pièce de monnaie qui donne "Face" avec probabilité $p$, et "Pile" avec la probalilité $1-p$, avec $0<p\leq \frac{1}{2}$. On lance cette pièce jusqu'à ce qu'on obtienne autant de "Face" que de "Pile" et l'on désigne par $X$ le nombre de lancers au bout desquels ceci se produit, en prenant $X=0$ si ceci ne se produit pas.
Nous avons vu que pour $n \in \mathbb N^*$, on a : $P(X=2n)=2c_{n}p^{n}(1-p)^{n}$, où $c_n$ est le nombre de Catalan :
$c_{n}=(_{~n-1}^{2n-2})-(_{~~~n}^{2n-2})=\frac{(2n-2)!}{n!(n-1)!}=\frac{1}{n}(_{~n-1}^{2n-2})$.
Nous avons vu que : $ \displaystyle f(t)=\underset{n=1}{\overset{+\infty }{\sum }}c_{n}t^{n}=\frac{1}{2}(1-\sqrt{1-4t})$ avec rayon de convergence $ \frac{1}{4}$.
Nous avons vu qu'il en résulte : $ \displaystyle P(X>0)=\underset{n=1}{\overset{+\infty }{\sum }}P(X=2n)=\underset{n=1}{\overset{+\infty }{\sum }}2c_{n}p^{n}(1-p)^{n}=2f(p(1-p))=2p$.
Si $0<p<\frac{1}{2}$, alors : $\displaystyle E(X)=\underset{n=1}{\overset{+\infty }{\sum }}2nP(X=2n)=4p(1-p)\underset{n=1}{\overset{+\infty }{\sum }}nc_{n}(p(1-p))^{n-1}$$=4p(1-p)f^{\prime }(p(1-p))=\frac{4p(1-p)}{\sqrt{1-4p(1-p)}}=\frac{4p(1-p)}{1-2p}$.
Et de même pour la variance, on part sur :
$\displaystyle E(X(X-2))=\underset{n=1}{\overset{+\infty }{\sum }}2n(2n-2)P(X=2n)=\underset{n=2}{\overset{+\infty }{\sum }}8n(n-1)c_{n}(p(1-p))^{n}$$=8p^{2}(1-p)^{2}f^{\prime \prime }(p(1-p))$.
Et ainsi de suite ...
Malheureusement la variance n'est pas jolie.
.................................................................................................................
J'ai fait ces rappels pour qu'on puisse vérifier s'il y a ou non des erreurs de calcul. J'ai tenté de réfléchir sur le message de "pldx1" ou du moins ce que j'en ai compris. La bonne idée qui j'ai retenue est de conditionner la variable aléatoire $X$ par l'événement << on arrive à autant de "Face" que de "Pile" >>, dans le cas où $0<p<\frac{1}{2}$. Cet événement, que je préfère désigner par $A$, est de probabilité $P(A)=2p$.
Pour $n \in \mathbb N^*$, on a : $P(X=2n|A)=\frac{P(X=2n)}{P(A)}$. D'où :
$\displaystyle E(X|A)=\underset{n=1}{\overset{+\infty }{\sum }}2nP(X=2n|A)=\underset{n=1}{\overset{+\infty }{\sum }}2n\frac{P(X=2n)}{P(A)}=\frac{E(X)}{P(A)}=\frac{2(1-p)}{1-2p}$.
Je trouve presque la même chose que "pldx1" mais avec un facteur 2.
En poursuivant je calcule la variance $V(X|A)=E(X^{2}|A)-E(X|A)^{2}$ et là c'est bien plus joli que $V(X)$ tout court puisque je trouve : $V(X|A)=\frac{4p(1-p)}{(1-2p)^{3}}$, mais toujours un facteur 4 de trop par rapport à "pldx1". Je me sais sujet aux erreurs de calcul et j'aimerais savoir ce qu'il en est.
Bonne journée.
R.
10/02/2015

pldx1

Bonjour,

@ Rouletabille. Pour ce qui est de la notation $\sigma$ qui fait double emploi, tu as raison et encore plus raison de proposer $A$ comme absorbant. Je vais rectifier.

Pour ce qui est des facteurs 2, cela vient de $n=2m$. Autrement dit, tu retrouves les résultats que j'ai donnés.

Pour le reste, il s'agit simplement du fait que l'action d'un opérateur linéaire se propage linéairement. Cela ne me semble pas être si inaccessible que cela.

Cordialement, Pierre.

Rouletabille

@ pldx1
Très content que nous soyons d'accord. J'aurais dû mieux lire et voir que tu prenais comme variable aléatoire la moitié de la mienne.
Pour le reste, je suis tout à fait persuadé en effet que les notions que tu manies ne sont pas inaccessibles. Simplement, je ne les connais pas et j'aimerais par exemple un ouvrage de référence sur le sujet, papier ou Internet.
Bonne journée, le temps a l'air de s'améliorer.
R.

pldx1

Bonjour,

Je vais essayer de reformuler ma présentation des choses, en essayant d'être le moins effrayant possible pour un éventuel débutant L1L2.

On part du fait que, avant de faire quoi que ce soit, on a la certitude que rien n'a encore été fait. Nous notons cela $1$ parce que $1$ est la mesure habituelle de la certitude. Ensuite de quoi, nous lançons la pièce deux fois. Il peut sortir $s=1$, soit $PP$ avec probabilité $p^{2}$, ou $s=0$ soit $\left\{ PF,FP\right\} $ avec la probabilité $2pq$ soit $s=-1$ avec la probabilité $q^{2}$. Vu que $q=1-p$, il serait inefficace de noter cela $p^{2}+2pq+q^{2}$ puisque cela ne ferait que redonner $1$, perdant ainsi toute information utile.

Mais nous pouvons noter cela $

\def\pon#1{\mathcal{P}_{#1}}

$$\pon 1\times\mathcal{W}_{1}\doteq\left[1,2,1\right]\times\,^{t}\!\left[p^{2},pq,q^{2}\right]$. Les $\mathcal{W}_{k}$ (avec W comme power) sont les puissances des probabilités élémentaires $p,q$ tandis que les $\pon k$ (avec P comme pondération) sont les multiplicateurs par lesquels on pondère les puissances. Comment passe-t-on d'une ligne $\pon k$ à la ligne suivante $\pon{k+1}$? Cela est étudié en détail dans le livre de Blaise P. qui démontre que, pour un seul lancer, cela s'obtient par l'opérateur shift and add. Cet opérateur est linéaire. Comme nous allons de deux en deux, l'opérateur d'évolution faisant passer d'une ligne à la suivante est donc $\Phi=$(shift and add)^2. Par composition, cet opérateur est linéaire lui aussi.

Détaillons comment les valeurs de $\pon 2$ se propagent à $\pon 3$ dans le jeu de pile ou face ordinaire. On applique $\Phi$, ce qui revient à ajouter shift^2, deux fois shift et self. Remarque: on complète par les zéros nécessaires au bon alignement, c'est le prix à payer lorsque l'on veut suivre la mode $C_{n}^{k}$ plutôt que la mode $\binom{n}{k}$. Cela donne: \[ \begin{array}{ccccccc} 1 & 4 & 6 & 4 & 1 & 0 & 0\\ 0 & 1 & 4 & 6 & 4 & 1 & 0\\ 0 & 1 & 4 & 6 & 4 & 1 & 0\\ 0 & 0 & 1 & 4 & 6 & 4 & 1\\ \hline 1 & 6 & 15 & 20 & 15 & 6 & 1 \end{array} \] Cela ne semble pas si stratosphérique que cela et l'on obtient:




Il reste maintenant à tenir compte du fait que quand c'est fini, cela ne continue pas. Anders gesagt, un état absorbant absorbe tout ce qui passe par là. Dans le jeu que nous décrivons ici, l'arborescence ne se poursuit pas au delà du $2$ de $\pon 1\doteq\left[1,2,1\right]$. Nous prenons note de la valeur de l'élément central, soit $x_{1}=2$, et nous le remplaçons par $0$, ce qui fait que la pondération $\pon 1$ est remplacée par $\pon 1'=\left[1,0,1\right]$. L'arborescence continue alors son évolution à partir des bourgeons survivants. Par quelle nouvelle valeur $\mathcal{P}'_{2}$ l'ancienne pondération $\pon 2$ va-t-elle être remplacée lorsque l'on perturbe $\pon 1=\left[1,2,1\right]$ en $\pon 1'=\left[1,0,1\right]$? Nous pouvons bien sûr faire le calcul direct selon:

\[ \begin{array}{ccccc} 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 1\\ \hline 1 & 2 & 2 & 2 & 1 \end{array} \]

Mais nous pouvons aussi tenir compte du fait que l'opérateur $\Phi$ est linéaire. Nous avons donc \[ \Phi\left(\pon 1'\right)=\Phi\left(\pon 1-x_{1}\pon 0^{*}\right)=\Phi\left(\pon 1\right)-x_{1}\Phi\left(\pon 0^{*}\right)=\pon 2-x_{1}\pon 1^{*} \] le {*} étant l'opérateur de rallongement symétrique (un $0$ additionnel de chaque côté). La valeur centrale $x_{2}=2$ correspond à l'arrivée dans l'état terminal. On a donc finalement: \[ \pon 2'=\pon 2-x_{1}\pon 1^{*}-x_{2}\pon 0^{**} \] Et cela recommence aux étapes suivantes.



Il est bien possible qu'il soit effrayant d'appeler "perturbation" la quantité $\pon 1'-\pon 1$ qui mesure le/la {accroissement, altération, bouleversement, changeation, ébranlement, métamorphose, modifiance, mutation, rectification, remaniement, transformation, variatude, y osotros} de la quantité $\pon 1$.

En fait, il est bien possible que la notion même de changement soit effrayante. Mais le changement est le mode d'existence du monde sub-lunaire et peut être même des autres. Faudrait-il supprimer le calcul des variations sous prétexte que, de temps à autre, quelques potentats sont raccourcis au point de nécessiter un changement dans le système des poids et mesures ?

Quoiqu'il en soit, l'équation aux variations donnée ci-dessus se propage de proche en proche par récurrence. Mais, surtout, sa propagation jusqu'à l'infini conduit à une relation portant sur les séries génératrices des éléments centraux, conduisant à la relation déjà donnée: \[ g\left(z\right)\doteq\sum_{k=1}^{k=\infty}x_{k}z^{k}=1-\sqrt{1-4z} \]

Puisqu'on en est à décrire les pondérations, une technique intéressante consiste à regrouper tous les éléments d'une ligne en un seul objet: on multiplie chaque masse par une variable $\xi$, élevée à une puissance égale à deux fois la balance du nombre de $P$ et de $F$. On peut donc coder $\mathcal{P}_{1}$ par $C_{1}=1\xi{}^{+2}+2\xi^{0}+1\xi^{-2}$, $\mathcal{P}_{2}$ par $C_{2}=1\xi^{+4}+4\xi^{+2}+6\xi^{0}+4\xi^{-2}+1\xi^{-4}$, etc. Cela s'appelle le triangle de Pascal isocèle, par opposition au triangle de Pascal rectangle (au fer à gauche).

On constate que la linéarité, jointe aux propriétés de l'opérateur shift, fait que \[ C_{k}\left(\xi\right)=\left(\xi^{2}+2+\xi^{-2}\right)^{k}=\left(\xi+\xi^{-1}\right)^{2k} \] permettant de retrouver le fait que les coefficients binomiaux sont les coefficients des puissances d'un binôme. Cela non plus ne devrait pas être trop effrayant. Mieux encore, posons \begin{eqnarray*} S\left(\xi,z\right) & = & \sum_{k=0}^{k=\infty}C_{k}\, z^{k}= \dfrac {1}
{1-z\left(\xi+\xi^{-1}\right)^{2}}\\ G\left(\xi,z\right) & = & \sum_{k=0}^{k=\infty}C'_{k}z^{k} \end{eqnarray*} la récurrence ci-dessus donne \[ G\left(\xi,z\right)=S\left(\xi,z\right)\times\left(1-g\left(z\right)\right)=\dfrac{\sqrt{1-4\, z}}{1-z\left(\xi+\xi^{-1}\right)^{2}} \]

Si l'on veut multiplier chaque pondération par sa probabilité, cela donne \[ G\left(\xi\sqrt{\frac{p}{q}},zpq\right)=\dfrac{\sqrt{1-4\, zpq}}{1-z\left(p\xi+q\xi^{-1}\right)^{2}} \] Le coefficient de $z^{m}$ décrit les probabilités des états possibles du système au bout de $m$ étapes sachant que $A$ n'a pas encore eu lieu.

Concluons par quelques additions de contrôle. Posons $G^{*}\left(z\right)=G\left(\sqrt{p/q},zpq\right)=\sqrt{1-4zpq}\div\left(1-z\right)$ et $g^{*}\left(z\right)=g\left(zpq\right)$. Nous avons alors la relation \[ \frac{1}{1-z}=G^{*}\left(z\right)+\frac{g^{*}\left(z\right)}{1-z} \] On retrouve le fait que, pour chaque valeur de $m$, le nombre $1$ est la somme des probabilités des états où l'on est encore en jeu (le choix $\xi=1$ sert à faire cette addition) et de la probabilité d'être déjà tombé dans l'état absorbant (la division par $1-z$ sert à additionner les probabilités d'avoir été absorbé à une étape $m'$ ou à une autre, avec $m'\leq m$).

Cordialement, Pierre.

Liste des Figures