dimanche 2 décembre 2012

marche aléatoire.


En mathématiques, en économie, et en physique théorique, une marche au hasard est un modèle mathématique d'un système possédant une dynamique discrète composée d'une succession de pas aléatoires, ou effectués « au hasard ». On emploie également fréquemment les expressions marche aléatoire, promenade aléatoire ou random walk en anglais. Ces pas aléatoires sont de plus totalement décorrélés les uns des autres; cette dernière propriété, fondamentale, est appelée caractère markovien du processus, du nom du mathématicien Markov.





On emploie également fréquemment les expressions marche aléatoire, promenade aléatoire ou random walk en anglais. Ces pas aléatoires sont de plus totalement décorrélés les uns des autres ; cette dernière propriété, fondamentale, est appelée caractère markovien du processus, du nom du mathématicien Markov. Elle signifie intuitivement qu'à chaque instant, le futur du système dépend de son état présent, mais pas de son passé, même le plus proche. Autrement dit, le système « perd la mémoire » à mesure qu'il évolue dans le temps. Pour cette raison, une marche aléatoire est parfois aussi appelée « marche de l'ivrogne ».

Cette modélisation mathématique permet de rendre compte de certains phénomènes naturels, dont l'exemple le plus fameux est le mouvement brownien, correspondant par exemple aux mouvements en apparence aléatoires des particules présentes dans le fluide intérieur d'un grain de pollen.

En mathématiques ou en informatique, on étudie souvent des marches au hasard sur des réseaux réguliers ou sur des graphes plus complexes. C'est par exemple la méthode utilisée par le moteur de recherche Google pour parcourir, identifier et classer les pages du réseau internet.

------------------------------------------------------------
La marche aléatoire unidimensionnelle symétrique

Considérons une expérience de Pile ou Face. Pour $ N$ jets successifs, on peut prendre comme univers le produit $ \Omega_N=\set{\text{P},\text{F}}^N$. Considérons alors la variable aléatoire $ S_k$ égale à la différence entre le nombre de Pile et de Face obtenus lors des $ k$ premiers jets. On peut écrire


$\displaystyle S_k = \sum_{j=1}^k X_j$   où $\displaystyle X_j = \begin{cases}\phantom-1 & \text{si le $j$-\\lq eme jet donne Pile\;,}\\ -1 & \text{si le $j$-\\lq eme jet donne Face\;.}\\ \end{cases}$(3.1)


La marche aléatoire unidimensionnelle symétrique est la suite des $ S_k$ obtenue dans le cas

$\displaystyle \prob{X_j=1} = \prob{X_j=-1} = \frac12\;,$(3.2)


les $ X_j$ étant supposés indépendants. Les réalisations du processus sont des suites $ \set{S_k(\omega)}$ d'entiers telles que $ S_0(\omega)=0$ et $ S_{k+1}(\omega)-S_k(\omega)=\pm1$(fig_marche1). La probabilité de chaque suite de longueur $ k$ est $ 2^{-k}$.



\begin{figure}{\small {\bf Figure 3.1. } Une r\'ealisation d'une marche al\'eatoire $S_k(\omega)$.}\end{figure}

Commençons par établir quelques propriétés élémentaires de la variable aléatoire $ S_k$.

\begin{prop}\hfill \begin{enum} \item L'image de $S_k$\ est $S_k(\Omega_N)=\set{... ...end{equation}\item On a $\expec{S_k}=0$\ et $\Var(S_k)=k$. \end{enum}\end{prop}

D´EMONSTRATION.
\begin{enum} \item Suit du fait que $S_0=0$\ et $S_{k+1}-S_k\in\set{-1,1}$. \it... ...c{X_i}=0$\ et $\Var(X_i)=1$, on a $\expec{S_k}=0$\ et $\Var(S_k)=k$. \end{enum}
$ \qedsymbol$

La Proposition 3.1.1 implique que $ S_k$ est nul en moyenne, mais que ses fluctuations sont d'ordre $ \sqrt{k}$. En particulier, la probabilité que le processus se trouve en 0 au $ k$-ème pas est donnée par


$\displaystyle \prob{S_k=0} = \begin{cases}0 & \text{si $k$\ est impair\;,} \\ ... ...ac{(2\ell)!}{2^{2\ell}(\ell!)^2} & \text{si $k=2\ell$\ est pair\;.} \end{cases}$(3.3)


Remarquons que la formule de Stirling implique que pour $ \ell$ grand,

$\displaystyle \prob{S_{2\ell}=0} \sim \frac1{2^{2\ell}} \frac{\sqrt{4\pi\ell}\e... ...l}(2\ell)^{2\ell}}{2\pi\ell\e^{-2\ell}\ell^{2\ell}} = \frac1{\sqrt{\pi\ell}}\;.$(3.4)


Cependant, la loi de chaque $ S_k$ ne détermine pas le processus, les $ S_k$ n'étant pas indépendants. Voici d'abord quelques propriétés simples du processus considéré dans son ensemble:

\begin{prop}\hfill \begin{enum} \item \defwd{Propri\'et\'e de Markov:}\/ Pour to... ...d{S_k=n}{S_\ell=m} = \prob{S_{k-\ell}=n-m}\;. \end{equation}\end{enum}\end{prop}

D´EMONSTRATION. Nous pouvons décomposer

$\displaystyle S_k = S_\ell + Y\;, \qquad Y = \sum_{j=\ell+1}^k X_j\;.$(3.5)


L'indépendance des $ X_i$ implique que $ Y = S_k-S_\ell$ est indépendante de $ X_1,\dots,X_\ell$, donc aussi de $ S_1,\dots,S_\ell$. Il suit que
$\displaystyle \pcond{S_k=n}{S_\ell=m_\ell,\dots,S_1=m_1}$$\displaystyle = \frac{\prob{Y=n-m_\ell,S_\ell=m_\ell,\dots,S_1=m_1}} {\prob{S_\ell=m_\ell,\dots,S_1=m_1}}$   
$\displaystyle = \prob{Y=n-m_\ell}\;.$(3.6)


Par le même raisonnement, nous avons également

$\displaystyle \pcond{S_k=n}{S_\ell=m_\ell} = \prob{Y=n-m_\ell}\;.$(3.7)


Finalement,

$\displaystyle \prob{Y=n-m} = \biggprob{\sum_{j=\ell+1}^k X_j = n-m} = \biggprob{\sum_{j=1}^{k-j} X_j = n-m} = \prob{S_{k-\ell}=n-m}\;,$(3.8)


du fait que les $ X_i$ sont identiquement distribués. $ \qedsymbol$

La propriété de Markov signifie que l'évolution du processus ne dépend que de son état présent, indépendamment de son passé. Elle permet d'écrire des relations du genre

\begin{multline} \qquad \prob{S_k=n,S_{k-1}=m,(S_1,\dots,S_{k-2})\in A} \\ = \p... ...n}{S_{k-1}=m} \prob{S_{k-1}=m,(S_1,\dots,S_{k-2})\in A}\;. \qquad \end{multline}







\begin{figure}{\small {\bf Figure 3.2. } Une r\'ealisation d'une marche al\'eatoire pour laquelle $\tau=12$.}\end{figure}

Voyons maintenant comment déduire de ces propriétés des informations non triviales sur les réalisations du processus. Une première quantité intéressante est le temps $ \tau$ du premier retour du processus en 0 (fig_marche2):


$\displaystyle \tau = \inf\setsuch{k\geqs 1}{S_k=0}\;.$(3.9)


Par exemple, dans l'expérience de jet de pièce de monnaie, $ \tau$ est le nombre de fois que l'on jette la pièce jusqu'à obtenir pour la première fois autant de Pile que de Face. Quelle est la loi de $ \tau$? Il est clair que $ \tau$ ne peut prendre que des valeurs paires. De plus, si $ \tau=k$ alors $ S_k=0$, donc $ \prob{\tau=k}\leqs\prob{S_k=0}$. En fait, il nous faut déterminer

$\displaystyle \prob{\tau=k} = \prob{S_1\neq0,S_2\neq0,\dots,S_{k-1}\neq0,S_k=0}\;.$(3.10)



\begin{theorem} La loi de $\tau$\ est donn\'ee par \begin{equation} \prob{\tau=... ...rob{S_{k-2}=0} & \text{pour $k$\ pair\;.} \end{cases}\end{equation}\end{theorem}




\begin{figure}{\small {\bf Figure 3.3. } Pour chaque r\'ealisation d'une marche... ...=-1$, obtenue par r\'eflexion par rapport \\lq a l'axe des abscisses.}\end{figure}



D´EMONSTRATION. Supposons que $ \tau=k$. Comme le processus ne peut pas changer de signe sans passer par 0, on a
$\displaystyle \prob{\tau=k} ={}$$\displaystyle \prob{S_1>0,S_2>0,\dots,S_{k-1}>0,S_k=0}$   
$\displaystyle {}+ \prob{S_1<0,S_2<0,\dots,S_{k-1}<0,S_k=0}$   
$\displaystyle ={}$$\displaystyle 2 \prob{S_1>0,S_2>0,\dots,S_{k-1}>0,S_k=0}$   
$\displaystyle ={}$$\displaystyle 2 \prob{S_1=1,S_2>0,\dots,S_{k-2}>0,S_{k-1}=1,S_k=0}$   
$\displaystyle ={}$$\displaystyle 2 \pcond{S_k=0}{S_{k-1}=1} \prob{S_1=1,S_2>0,\dots,S_{k-2}>0,S_{k-1}=1} \;,$(3.11)


où nous avons utilisé la propriété de Markov dans la dernière ligne. La propriété des incréments stationnaires implique

$\displaystyle \pcond{S_k=0}{S_{k-1}=1} = \prob{S_1=-1} = \frac12\;.$(3.12)


Il suit que
$\displaystyle \prob{\tau=k}$$\displaystyle = \prob{S_1=1,S_2>0,\dots,S_{k-2}>0,S_{k-1}=1}$(3.13)
$\displaystyle = \prob{S_1=S_{k-1}=1} - \prob{S_1=S_{k-1}=1,\, \exists\ell\in\set{2,\dots,k-2}:\,S_\ell=0}\;.$   


Nous utilisons maintenant un argument important, appelé le principe de réflexion: A tout chemin allant de $ (1,1)$ à $ (k-1,1)$ passant par 0, on peut faire correspondre un unique chemin de $ (-1,1)$ à $ (k-1,1)$, obtenu en réfléchissant par rapport à l'axe des abscisses la partie du chemin antérieure au premier passage en 0. On a donc

$\displaystyle \prob{S_1=S_{k-1}=1,\,\exists\ell\in\set{2,\dots,k-2}:\,S_\ell=0} = \prob{S_1=-1,S_{k-1}=1}\;.$(3.14)


Finalement, en appliquant de nouveau la propriété des incréments stationnaires, on voit que
$\displaystyle \prob{S_1=1,S_{k-1}=1}$$\displaystyle = \pcond{S_{k-1}=1}{S_1=1}\prob{S_1=1} = \prob{S_{k-2}=0}\cdot\frac12\;,$   
$\displaystyle \prob{S_1=-1,S_{k-1}=1}$$\displaystyle = \pcond{S_{k-1}=1}{S_1=-1}\prob{S_1=-1} = \prob{S_{k-2}=2}\cdot\frac12\;.$(3.15)


En remplaçant dans (3.1.19), il vient

$\displaystyle \prob{\tau=k} = \frac12 \bigbrak{\prob{S_{k-2}=0} - \prob{S_{k-2}=2}}\;.$(3.16)


Le reste de la preuve est un calcul direct. Comme

$\displaystyle \frac{\prob{S_{k-2}=2}}{\prob{S_{k-2}=0}} = \frac{\binom{k-2}{k/2... ...frac k2}!\bigpar{\frac k2-2}!} = \frac{\frac k2 - 1}{\frac k2} = 1 - \frac2k\;,$(3.17)


on obtient

$\displaystyle \prob{\tau=k} = \frac12 \prob{S_{k-2}=0}\biggbrak{1 - 1 + \frac2k} = \frac1k \prob{S_{k-2}=0}\;,$(3.18)


ce qui conclut la démonstration. $ \qedsymbol$

Le tableau suivant donne les premières valeurs de la loi de $ \tau$:
$ k$$ 2$$ 4$$ 6$$ 8$$ 10$$ 12$$ 14$
$ \prob{\tau=k}$$ \frac12$$ \frac18$$ \frac1{16}$$ \frac5{128}$$ \frac7{256}$$ \frac{21}{1024}$$ \frac{33}{2048}$
$ =0.5$$ =0.125$$ \cong0.063$$ \cong0.039$$ \cong0.027$$ \cong0.021$$ \cong0.016$
Il est donc assez probable de revenir rapidement en 0, puis la loi prend des valeurs plutôt faibles, tout en décroissant lentement. Il suit de (3.1.6) que pour des grands$ k$, $ \prob{\tau=k}$ décroît comme $ 1/k^{3/2}$. Ce fait a une conséquence surprenante:
\begin{cor} $\expec{\tau}=+\infty$. \end{cor}

D´EMONSTRATION. On a

$\displaystyle \expec{\tau} = \sum_{k\geqs 1}k\prob{\tau=k} = \sum_{\ell\geqs1} ... ...\prob{S_{2\ell-2}=0} \sim \sum_{\ell\geqs1} \frac1{\sqrt{\pi\ell}} = +\infty\;.$(3.19)


$ \qedsymbol$

En d'autres termes, la marche aléatoire finit toujours par revenir en 0, mais la loi de $ \tau$ décroît trop lentement pour que son espérance soit finie. Cela est lié au fait que si la marche aléatoire s'éloigne beaucoup de 0, il lui faut longtemps pour y revenir.
Considérons une autre application du principe de réflexion. Supposons qu'une machine à sous fonctionne avec une mise d'un euro, et que la machine rende soit deux euros, soit rien, avec la même probabilité. Combien de fois peut-on jouer, si l'on possède initialement $ 10$ euros? La somme que l'on possède après avoir joué $ k$ fois est égale à $ 10-S_k$, on peut donc jouer jusqu'à ce que $ S_k=10$. Il nous faut donc déterminer la loi de


$\displaystyle \tau_L = \inf\setsuch{k\geqs0}{S_k=L}$(3.20)


pour $ L=10$ dans notre exemple.
\begin{theorem} La loi de $\tau_L$\ est donn\'ee par \begin{equation} \prob{\ta... ...}+2, \dots}$\;,} \\ 0 & \text{sinon\;.} \end{cases}\end{equation}\end{theorem}

D´EMONSTRATION. Considérons le cas $ L>0$. On a
$\displaystyle \prob{\tau_L=k}$$\displaystyle = \prob{S_1<L,S_2<L,\dots,S_{k-1}=L-1,S_k=L}$   
$\displaystyle = \pcond{S_k=L}{S_{k-1}=L-1}\prob{S_1<L,S_2<L,\dots,S_{k-1}=L-1}$   
$\displaystyle = \frac12 \prob{S_1<L,S_2<L,\dots,S_{k-1}=L-1}$(3.21)
$\displaystyle = \frac12 \bigbrak{\prob{S_{k-1}=L-1} - \prob{S_{k-1}=L-1,\,\exists j\in\set{1,\dots,k-2}:\,S_j=L}}\;.$   


Invoquons alors à nouveau le principe de réflexion (fig_marche4). A chaque réalisation telle que $ S_{k-1}=L-1$, qui a déjà atteint le niveau $ L$ auparavant, on peut associer une réalisation telle que $ S_{k-1}=L+1$. Nous avons donc
$\displaystyle \prob{\tau_L=k}$$\displaystyle = \frac12 \bigbrak{\prob{S_{k-1}=L-1} - \prob{S_{k-1}=L+1}}$   
$\displaystyle = \frac12 \frac1{2^{k-1}} \biggbrak{\binom{k-1}{\frac{k+L}2 -1} - \binom{k-1}{\frac{k+L}2}}$   
$\displaystyle = \frac{(k-1)!}{2^k} \biggbrak{\frac1{\bigpar{\frac{k+L}2-1}!\bigpar{\frac{k-L}2}!} - \frac1{\bigpar{\frac{k+L}2}!\bigpar{\frac{k-L}2 - 1}!}}$   
$\displaystyle = \frac1{2^k} \frac{k!}{\bigpar{\frac{k+L}2}!\bigpar{\frac{k-L}2}!} \frac1k \biggbrak{\frac{k+L}2 - \frac{k-L}2}$   
$\displaystyle = \prob{S_k=L} \frac Lk\;.$(3.22)


Le cas $ L<0$ suit par symétrie. $ \qedsymbol$





\begin{figure}{\small {\bf Figure 3.4. } Pour chaque r\'ealisation d'une marche... ...btenue par r\'eflexion par rapport \\lq a la droite d'ordonn\'ee $L$.}\end{figure}

Pour des raisons similaires à celles du cas du retour en 0, la loi de $ \tau_L$ décroît en $ 1/k^{3/2}$, et son espérance est donc infinie. On est donc sûr de perdre tôt ou tard, tout en pouvant espérer jouer infiniment longtemps. Le tableau suivant donne les premières valeurs de la loi dans le cas $ L=2$, donc si on ne possède que deux euros au début.

IMPORTANT.


 On constate que si l'on ne perd pas lors des $ 6$ premiers coups, la probabilité de perdre en $ k$ coups change très peu d'un $ k$ au suivant.
$ k$$ 2$$ 4$$ 6$$ 8$$ 10$$ 12$$ 14$
$ \prob{\tau_2=k}$$ \frac14$$ \frac18$$ \frac5{64}$$ \frac7{128}$$ \frac{21}{512}$$ \frac{33}{1024}$$ \frac{429}{16384}$
$ =0.25$$ =0.125$$ \cong0.078$$ \cong0.054$$ \cong0.041$$ \cong0.032$$ \cong0.026$

next up previous contents






zajdenweber02-05-2012 - 11:27:24

mauvaise file

Parmi les explications mathématiques de la malédiction de la mauvaise file, il faut citer celle de William Feller, contenue dans son manuel "An Introduction to Probability Theory and its Applications, vol II, page 17, Wiley edit." W.Feller, la nomme: "Persistency of bad luck". Elle repose sur une propriété bien connue, mais paradoxale, du jeu de pile ou face : la longueur moyenne entre deux retours à l'origine est infinie. En effet, si on assimile deux files d'attente parallèles aux deux faces d'une pièce de monnaie "équitable", l'écart entre les deux files correspond à la fortune d'un joueur au détriment de l'autre. Pile, la file de gauche avance d'un cran, face, la file de droite avance d'un cran. Or, la loi de probabilité qui distribue la longueur des intervalles entre deux retours à l'origine (=à l'égalité des fortunes) est la distribution "stable" de Paul Lévy d'exposant caractéristique -1/2. Il y a bien une probabilité égale à 1 pour qu'une file soit toujours rattrapée, mais l'espérance du temps d'attente est infinie! Ainsi, un conducteur qui voit que l'autre file le dépasse, doit attendre parfois très longtemps avant de la rattraper. L'illusion de la malédiction provient d'un biais de perception. Les très nombreux petits intervalles ne sont ni perçus, ni mémorisés. En revanche, l'attention d'un conducteur est éveillée dès qu'il voit une file le dépasser. En conséquence, dès que vous êtes dépassé de façon perceptible, vous n'avez pas beaucoup de chance de rattraper l'autre file. De plus, il ne sert à rien de changer de file, puisque dans une partie de pile ou face, il n'y a pas de mémoire. Chaque date est le point de départ d'une nouvelle partie. En s'infiltrant dans la file qui avance en apparence plus vite, on risque de voir l'ancienne file dépasser la nouvelle avec une probabilité 1/2. Une malédiction au carré en quelque sorte


_________________________________________________

Savoir quand s'arrêter

Dans les jeux de hasard, les mathématiques indiquent parfois quel est le meilleur moment pour s'arrêter de jouer. Ces stratégies d'arrêt optimal s'appliquent aussi dans d'autres situations.
Theodore Hill

L'auteur

Theodore HILL est professeur émérite de mathématiques à l'Institut de technologie de Géorgie, aux États-Unis.

Nous remercions la revue American Scientist de nous avoir autorisés à reproduire cet article.

Pour en savoir plus

F. Boshuizen et T. P. Hill, Moment-based minimax stopping functions for sequences of random variables, Stochastic Processes and Applications, vol. 43, pp. 303-316, 1992.

F. T. Bruss, Sum the odds to one and stop, The Annals of Probability, vol. 28, pp. 1384-1391, 2000.

Y. Chow, H. Robbins, et D. Siegmund, Great Expectations : The Theory of Optimal Stopping, Dover Publications, 1991.

T. Cover, « Pick the largest number », dans Open Problems in Communication and Computation (édité par T. Cover et B. Gopinath), Springer-Verlag, 1987.

L. Dubins et L. Savage, Inequalities for Stochastic Processes : How to Gamble if You Must, Dover Publications, 1976.

T. Ferguson, Who solved the secretary problem ?, Statistical Science, vol. 4, pp. 282-296, 1989.

P. R. Freeman, The secretary problem and its extensions : a review, International Statistical Review, vol. 51, pp. 189-208, 1983.

T. P. Hill et U. Krengel, Minimax-optimal stop rules and distributions in secretary problems, The Annals of Probability, vol. 19 (1), pp. 342-353, 1991.

T. P. Hill et D. Kennedy, Sharp inequalities for optimal stopping with rewards based on ranks, Annals of Applied Probability, vol. 2, pp. 503-517, 1992.

S. Jacka et al., Optimal stopping with applications, Stochastics, vol. 79, pp. 1-4, 2007.

G. Peskir et A. Shiryaev, Optimal Stopping and Free Boundary Problems, Birkhaüser, 2006.

D. Samet, I. Samet et D. Schmeidler, One observation behind two-envelope problems, American Mathematical Monthly, vol. 111, pp. 347-351, 2004.

S. Shreve, Don’t blame the quants. Forbes.com. http://www.forbes.com/2008/10/07/securities-quants-models-oped-cx_ss_1008shreve.html

W. Stadje, The maximum average gain in a sequence of Bernoulli trials, American Mathematical Monthly, vol. 115, pp. 902-910, 2008.

Dans ce numéro

Pour la science N°381Pour la science N°381
juillet 2009



de 90, il est optimal d'acheter. En remontant jusqu'au lundi, puisque 100 est supérieur à l'espérance de prix s'il continue (à savoir (1/2)(105) + (1/2)(90) = 97,5), il est optimal de ne pas acheter le lundi. Ces éléments réunis constituent la stratégie optimale d'arrêt.

Dans le cas où l'information est complète, avec pour objectif de s'arrêter sur l'une des k plus grandes valeurs, on ignorait quelles étaient les meilleures probabilités possibles de gagner pour des séquences finies générales de variables aléatoires indépendantes. En utilisant à la fois la récurrence normale et celle à rebours, et une classe de distributions statistiques nommées pyramides de Bernoulli, Douglas Kennedy, de l'Université de Cambridge, et moi avons découvert ces probabilités optimales. Nous avons prouvé vers 1992 que pour toute séquence finie de variables aléatoires indépendantes, il y a toujours une règle d'arrêt qui tombe sur la valeur la plus élevée avec une probabilité au moins égale à 1/e, et une règle d'arrêt qui tombe sur l'une des deux valeurs les plus élevées avec une probabilité au moins égale à (1+ œ2) exp (-œ2), soit environ 0,59 - c'est le mieux que l'on puisse faire. Les probabilités de s'arrêter sur l'une des k valeurs les plus élevées ont des formules similaires.
Notons que les ordinateurs n'ont été d'aucune aide pour résoudre ce problème. En fait, tous les problèmes décrits dans cet article ont été résolus en utilisant des outils mathématiques classiques, en travaillant exemple après exemple avec du papier et un crayon ; en résolvant le cas avec deux, trois, puis quatre inconnues ; en cherchant des régularités ; en attendant que viennent des idées lumineuses ; enfin, en cherchant à démontrer formellement chaque étape.
Quand l'information n'est que partielle
Le cas où l'information n'est que partielle est le plus difficile. D'ordinaire, on ne sait pas d'avance combien de candidats il y aura à un emploi donné, ni les probabilités des valeurs futures des actions en Bourse. Dans ces situations, une méthode de résolution consiste à utiliser les outils de la théorie des jeux. Le problème de l'arrêt peut y être envisagé comme celui d'un décideur jouant contre un adversaire qui peut fixer les valeurs et les probabilités à sa guise.
Ulrich Krengel, de l'Université de Göttingen, et moi-même avons utilisé cette technique pour découvrir la stratégie optimale dans le problème dit du mariage, où seule une borne supérieure au nombre de candidats est connue.
À titre d'exemple concret, considérons le problème consistant à sélectionner le plus grand nombre dans un chapeau contenant au moins une, et au plus cinq, cartes numérotées (si vous ne vous arrêtez pas et qu'il ne reste aucune carte, vous avez perdu). Nous avons démontré que la stratégie optimale dans ce cas est de s'arrêter à la première carte avec la probabilité 26/75. Si vous ne vous arrêtez pas à la première carte, alors vous continuez jusqu'à la deuxième carte, s'il y en a une. Si le nombre de la deuxième carte est supérieur à celui de la première, arrêtez-vous avec la probabilité 26/49. Sinon, continuez, en vous arrêtant au premier record (ou lorsque vous avez épuisé vos cartes ou que vous êtes forcé de choisir le nombre de la cinquième carte). Cela garantit une probabilité de 26/75 de s'arrêter sur le nombre le plus élevé, quel que soit le nombre (entre un et cinq) de cartes déposées dans le chapeau.
Il n'existe pas de meilleure stratégie. Nous avons trouvé les formules exactes pour toutes les limites possibles sur le nombre maximum de cartes, et les probabilités de gagner sont étonnamment élevées. Par exemple, si vous savez seulement qu'il y a entre 1 et 100 cartes dans le chapeau, il est encore possible de gagner environ une fois sur cinq. On peut utiliser exactement la même méthode pour obtenir les règles d'arrêt optimal dans de nombreux problèmes de la vie courante, par exemple quand un employeur veut embaucher le meilleur vendeur sur le marché, connaît le nombre maximum de candidats au poste, mais ignore combien d'entre eux ont déjà accepté une autre offre.
Dans un autre type de problème d'arrêt impliquant une information partielle, l'observateur connaît exactement la longueur de la séquence (par exemple le nombre de cartes), mais il ne dispose que d'une information partielle sur les valeurs (aléatoires) écrites sur les cartes. Au lieu de n'avoir aucune information du tout, ou de connaître toutes les valeurs et probabilités possibles, il pourrait ne connaître que la valeur moyenne et l'écart type de chaque variable aléatoire. Dans le cas où les variables sont indépendantes, Frans Boshuizen, de l'Université libre d'Amsterdam, et moi-même avons réussi à déterminer les règles d'arrêt optimal, mais les techniques que nous avons utilisées, issues notamment de la théorie des jeux, échouent dans la plupart des autres problèmes d'arrêt à information partielle.
que de nombreux problèmes d'arrêt aient été résolus, il subsiste des problèmes très simples qui, de manière très frustrante, restent non résolus, même parmi ceux qui font intervenir une information complète. Mon préféré est le suivant. Vous tirez à pile ou face avec une pièce non truquée, en vous arrêtant quand vous voulez. La récompense est le nombre moyen de faces obtenues (nombre de faces divisé par le nombre de lancers) au moment où vous vous arrêtez (voir la figure 5).
Si votre premier lancer est une face et que vous vous arrêtez, votre récompense est ainsi de un Krugerrand. Puisque vous ne pourrez jamais avoir plus de 100 pour cent de faces, il est optimal de s'arrêter dans ce cas. Si, en revanche, le premier lancer tombe sur le côté pile, il est préférable de ne pas s'arrêter tout de suite, puisque votre récompense serait nulle. Supposez que le premier tirage soit pile, et le second face. Vous pouvez vous arrêter là et recevoir un demi-Krugerrand, ou bien continuer à tirer. Un peu de réflexion montre qu'il n'est jamais optimal de s'arrêter avec un demi-Krugerrand ou moins. En effet, en vertu de la loi des grands nombres, plus le nombre de lancers est grand, plus la proportion de faces s'approche de 50 pour cent, en oscillant aléatoirement au-dessus et au-dessous de cette valeur. S'arrêter à 50 pour cent n'est tout simplement pas assez ambitieux.
Avec un peu plus de difficulté, on montre que s'arrêter au troisième tirage après pile-face-face est optimal, et que s'arrêter la première fois qu'on observe plus de faces que de piles est optimal pendant un certain temps. Mais s'arrêter la première fois que vous avez davantage de faces que de piles ne reste pas éternellement optimal. Au bout d'un certain temps, on devrait s'arrêter seulement si l'on a deux faces de plus que de piles, puis après un deuxième temps critique, s'arrêter seulement si l'on a trois faces d'avance, et ainsi de suite.
La démonstration de ce fait n'est pas aisée, et la liste complète des temps critiques n'est pas connue. La récurrence à rebours ne fonctionne pas pour ce problème puisqu'il n'y a a priori pas de fin à la séquence et donc pas de temps futur à partir duquel on puisse raisonner à reculons. Malgré des avancées très récentes de Wolfgang Stadje, de l'Université d'Osnabrück, en Allemagne, la règle optimale exacte pour toutes les séquences de faces et de piles est inconnue.
Néanmoins, le domaine général de l'arrêt optimal, en particulier avec ses applications aux marchés financiers, continue à se développer à vive allure. En fait, certains spécialistes trouvent que ce rythme a été trop rapide et que les modèles informatiques de l'évaluation des options financières et des produits dérivés sont à l'origine de l'actuelle crise économique. Mais ce n'est pas la théorie qui est en cause. Comme Steven Shreve, de l'Université Carnegie Mellon, j'en attribue la responsabilité à la confiance aveugle des décideurs dans les prédictions des modèles. En fait, nous avons besoin de nouvelles idées et découvertes en matière d'arrêt optimal, y compris de meilleures estimations du risque que les modèles mathématiques soient erronés - non seulement comme guide pour savoir quand mettre fin aux subventions, par exemple, mais aussi pour faire face à de nombreux autres problèmes cruciaux (quand arrêter d'utiliser des combustibles fossiles, de stocker des armes nucléaires, etc.). ■


____________________________________________________________________




Savoir quand s'arrêter

Dans les jeux de hasard, les mathématiques indiquent parfois quel est le meilleur moment pour s'arrêter de jouer. Ces stratégies d'arrêt optimal s'appliquent aussi dans d'autres situations.
Theodore Hill

L'auteur

Theodore HILL est professeur émérite de mathématiques à l'Institut de technologie de Géorgie, aux États-Unis.

Nous remercions la revue American Scientist de nous avoir autorisés à reproduire cet article.

Pour en savoir plus

F. Boshuizen et T. P. Hill, Moment-based minimax stopping functions for sequences of random variables, Stochastic Processes and Applications, vol. 43, pp. 303-316, 1992.

F. T. Bruss, Sum the odds to one and stop, The Annals of Probability, vol. 28, pp. 1384-1391, 2000.

Y. Chow, H. Robbins, et D. Siegmund, Great Expectations : The Theory of Optimal Stopping, Dover Publications, 1991.

T. Cover, « Pick the largest number », dans Open Problems in Communication and Computation (édité par T. Cover et B. Gopinath), Springer-Verlag, 1987.

L. Dubins et L. Savage, Inequalities for Stochastic Processes : How to Gamble if You Must, Dover Publications, 1976.

T. Ferguson, Who solved the secretary problem ?, Statistical Science, vol. 4, pp. 282-296, 1989.

P. R. Freeman, The secretary problem and its extensions : a review, International Statistical Review, vol. 51, pp. 189-208, 1983.

T. P. Hill et U. Krengel, Minimax-optimal stop rules and distributions in secretary problems, The Annals of Probability, vol. 19 (1), pp. 342-353, 1991.

T. P. Hill et D. Kennedy, Sharp inequalities for optimal stopping with rewards based on ranks, Annals of Applied Probability, vol. 2, pp. 503-517, 1992.

S. Jacka et al., Optimal stopping with applications, Stochastics, vol. 79, pp. 1-4, 2007.

G. Peskir et A. Shiryaev, Optimal Stopping and Free Boundary Problems, Birkhaüser, 2006.

D. Samet, I. Samet et D. Schmeidler, One observation behind two-envelope problems, American Mathematical Monthly, vol. 111, pp. 347-351, 2004.

S. Shreve, Don’t blame the quants. Forbes.com. http://www.forbes.com/2008/10/07/securities-quants-models-oped-cx_ss_1008shreve.html

W. Stadje, The maximum average gain in a sequence of Bernoulli trials, American Mathematical Monthly, vol. 115, pp. 902-910, 2008.

Dans ce numéro

Pour la science N°381Pour la science N°381
juillet 2009



inscrit est supérieur au nombre caché sous l'autre carte. L'étonnant résultat, avancé à l'origine par David Blackwell, de l'Université de Californie à Berkeley, est que l'on peut gagner à ce jeu plus d'une fois sur deux (voir la figure 4).

À l'évidence, on peut gagner exactement une fois sur deux en s'arrêtant systématiquement sur le premier nombre, ou systématiquement sur le second, sans même les regarder. Mais pour gagner dans plus de la moitié des cas, on doit trouver un moyen d'utiliser l'information liée au premier nombre pour décider s'il convient de s'arrêter ou pas. (Que le lecteur se rassure : quand nous autres mathématiciens avons entendu cette affirmation, nous avons été nombreux à ne pas y croire.)
Une règle d'arrêt qui le permet est la suivante. Tout d'abord, générez un nombre aléatoire R selon une loi gaussienne centrée réduite (loi statistique classique, dont la courbe représentative - en abscisse les nombres, en ordonnée leurs fréquences de tirage - a une forme de cloche) à l'aide d'un ordinateur ou d'un autre dispositif. Retournez alors l'une des cartes et lisez le nombre écrit dessus. Si R est supérieur au nombre observé, continuez et retournez la seconde carte. Si R est inférieur, restez-en au nombre indiqué sur la première carte.
Comment une stratégie aussi simple garantit-elle de gagner dans plus de la moitié des cas ? Notons N1 et N2 les deux nombres inscrits, avec N1 < N2. Soit p la probabilité (inconnue a priori) de choisir, selon la loi gaussienne, un nombre R inférieur à N1, et q la probabilité de choisir un R supérieur à N2 (voir la figure 4).
Supposons R inférieur à N1 ; dans cette hypothèse, vraie avec la probabilité p, vous gagnez une fois sur deux, donc avec une probabilité p/2. Si R est supérieur à N2, situation de probabilité q, vous gagnez encore une fois sur deux, donc avec la probabilité q/2. Mais si R tombe entre les deux nombres inscrits (N1 < R < N2), situation qui se produit avec une probabilité strictement positive égale à 1 - p - q (la distribution gaussienne attribue une probabilité positive à tout intervalle), alors vous gagnez à chaque fois, c'est-à-dire avec la probabilité 1 - p - q.
Au total, en prenant en compte les trois situations possibles pour le nombre R choisi, vous gagnez avec la probabilité p/2 + q/2 + 1 - p - q. Or cette probabilité, qui s'écrit aussi 1/2 + (1 - p - q)/2, est supérieure à 1/2, puisque 1 - p - q est positif. Par exemple, si les deux nombres cachés sont 1 et π, la loi gaussienne donne p égal à environ 0,8413 et q égal à environ 0,0008 ; il s'ensuit qu'avec la stratégie indiquée, la probabilité de sélectionner le plus grand des deux nombres est supérieure à 57 pour cent.
Bien sûr, si la personne qui écrit les nombres sait que vous utilisez la stratégie gaussienne, elle peut, en choisissant des nombres N1 et N2 très proches, ramener votre probabilité de gagner au plus près de 1/2. Si elle n'est pas complètement libre de choisir n'importe quels nombres, mais est obligée par exemple de prendre des entiers compris entre 1 et 100, alors il lui sera impossible de rendre votre probabilité de gagner arbitrairement proche de 1/2.
Récurrence à rebours
Au lieu de ne disposer, comme précédemment, d'aucune information préalable sur les valeurs impliquées, on peut avoir une information complète sur les probabilités et les valeurs exactes de toutes les observations potentielles futures. Considérons un jeu consistant à lancer au maximum cinq fois un dé à six faces. Vous pouvez vous arrêter quand vous voulez et recevoir alors comme récompense autant de Krugerrands (pièces d'or sud-africaines) que de points affichés par le dé au moment où vous vous arrêtez.
Contrairement aux problèmes de mariage sans information, ici tout est connu. Les résultats possibles de chaque lancer sont 1, 2, 3, 4, 5 et 6, et la probabilité de chacun à chaque lancer est d'un sixième. Il s'agit de trouver la règle d'arrêt qui maximise le nombre de Krugerrands que l'on peut espérer gagner en moyenne.
Si vous vous arrêtez toujours au premier lancer, par exemple, le gain sera simplement l'espérance mathématique d'une variable aléatoire qui prend les valeurs 1, 2, 3, 4, 5 ou 6 avec une probabilité 1/6 pour chacune. En d'autres termes, une fois sur six vous gagnerez un Krugerrand, une fois sur six vous en gagnerez deux, etc., ce qui donne l'espérance mathématique : 1(1/6) + 2(1/6) + 3(1/6) + 4(1/6) + 5(1/6) + 6(1/6) = 7/2.
Ainsi, si vous vous arrêtez toujours au premier lancer, vous gagnerez 3,5 Krugerrands en moyenne. Bien sûr, il n'est pas optimal de s'arrêter au premier lancer s'il donne un 1, et il est toujours optimal de s'arrêter s'il donne un 6. Mais faut-il s'arrêter si l'on a obtenu un 5 au premier lancer ? Une méthode générale puissante pour résoudre ce type de problème est la « récurrence à rebours ».
Il est évidemment optimal de s'arrêter au premier lancer si la valeur affichée par le dé est supérieure à celle attendue dans le cas où vous continuez à lancer le dé après avoir rejeté le premier lancer. Cela vous placerait dans un nouveau jeu où vous n'avez droit qu'à quatre lancers, dont l'espérance mathématique est également inconnue au départ. La stratégie optimale dans un problème à quatre lancers, à son tour, est de s'arrêter au premier lancer si la valeur obtenue est supérieure au gain espéré en continuant avec un problème à trois lancers, et ainsi de suite. On aboutit au problème à un lancer, pour lequel il n'y a qu'une stratégie, à savoir s'arrêter, et la récompense attendue est l'espérance mathématique d'un unique lancer de dé, dont nous avons vu qu'elle vaut 3,5 (voir la figure 6).
Cette information nous donne à son tour la stratégie optimale d'un problème à deux lancers : s'arrêter au premier lancer si la valeur est supérieure à ce que vous espérez gagner en continuant, c'est-à-dire supérieure à 3,5. Nous connaissons donc maintenant la stratégie optimale pour un problème à deux lancers (s'arrêter au premier lancer si c'est un 4, un 5 ou un 6, continuer sinon) et cela permet de calculer la récompense espérée.
Dans un problème à deux lancers, on gagne 4, 5 ou 6 au premier lancer avec une probabilité de 1/6 chacun, et l'on s'arrête. Sinon (quand le premier lancer est un 1, un 2 ou un 3, situation qui se produit une fois sur deux), on continue, auquel cas on s'attend à gagner 3,5 en moyenne. Ainsi, la récompense attendue pour le problème à deux lancers est : 4(1/6) + 5(1/6) + 6(1/6) + (1/2)(3,5) = 4,25.
Stratégie optimale
Cela fournit maintenant la stratégie optimale pour un problème à trois lancers, à savoir s'arrêter si le premier lancer est un 5 ou un 6 (c'est-à-dire supérieur à 4,25), et sinon continuer et ne s'arrêter que si le second lancer est un 4, 5 ou 6, et dans le cas contraire poursuivre avec un troisième et dernier lancer. La connaissance de cette récompense attendue pour trois lancers donne à son tour la stratégie optimale pour un problème à quatre lancers : ne s'arrêter au premier lancer que s'il donne un 5 ou un 6, s'arrêter au second lancer si c'est un 5 ou un 6, au troisième si c'est un 5 ou un 6, au quatrième si c'est un 4, un 5 ou un 6, et sinon aller jusqu'au lancer final. Cette stratégie garantit que vous gagnerez environ 5,12 Krugerrands en moyenne, et aucune stratégie n'est meilleure.
La méthode de la récurrence à rebours est polyvalente, et fonctionne aussi bien lorsque les valeurs du processus ne sont pas indépendantes (comme elles sont supposées l'être lorsqu'on lance plusieurs fois le dé), ou s'il s'agit de minimiser une espérance mathématique telle que le coût.
Supposons qu'une entreprise doive acheter son approvisionnement hebdomadaire en énergie le lundi, mardi ou mercredi précédent et que la probabilité des prix à venir puisse être estimée sur la base de statistiques passées. Par exemple, si le lundi l'acheteur a l'occasion de payer l'énergie pour la semaine suivante à un prix de 100, il peut savoir d'expérience qu'il y a une probabilité 1/2 pour que le prix du mardi soit 110, et 90 sinon. De plus, il sait que si le prix est égal à 110 le mardi, alors le prix sera de 115 le mercredi avec une probabilité égale à 1/3, et de 100 autrement ; et que s'il vaut 90 le mardi, il a autant de chances de valoir 100 que 85 le mercredi.
Par récurrence à rebours, on voit que la règle optimale pour le mardi est de ne pas acheter si le prix est de 110, puisque 110 est supérieur à l'espérance mathématique du prix s'il attend mercredi pour acheter, espérance égale à : (1/3)(115) + (2/3)(100) = 105.
De la même façon, si le prix mardi est

Article intégral


Téléchargez cet article au format pdf


  • Imprimante




Vos réactions (7)




Alain Gottcheiner04-08-2009 - 14:11:28
A propos de probabilités
Il me semble avoir repéré deux erreurs dans l'article de T. Hill sur les procédures de décision.
1. La probabilité de trouver le plus grand nombre parmi 100, avec la procédure simple "regarder les 50 premiers nombres, ensuite s'arrêter sur un nombre-record" n'est pas de 1/4 mais bien de 50/99. En effet, la probabilité conditionnelle pour que le second plus grand nombre soit dans la prmeière moitié, ssachant que le plus grand est dans la seconde moitié, n'est pas de 1/2 mais bien de 50/99 (comptons les "places disponibles").
2. La probabilité de trouver le plus grand de deux nombres avec l'aide d'un tirage suivant une loi normale ne peut être déterminée en connaissant seulement les deux nombres. En effet, elle dépend de la loi normale choisie. Pour reprendre l'exemple de l'article, si les deux nombres cachés étaient 1 et Pi, si j'ai choisi une normale de moyenne 1000 et d'écart-type 100, ma probabillité de réussite est extrêmement proche de 50%, car le nombre engendré ne se situera pour ainsi dire jamais entre 1 et Pi. Par contre, si j'ai choisi une normale de moyenne 2 et d'écart-type 1, mes chances de réussites sont grandes.
Déterminer des valeurs de p et q, et donc une probabilité précise de gain, sans savoir quelle normale l'interlocuteur a choisie, est impossible, et la valeur de 57% avancée par l'auteur ne veut rien dire. Peut-on vérifier tout cela ? Merci.
Alain Gottcheiner, Laboratoire de Mathématiques et Sciences Humaines, ULB.

Theodore Hill 11-09-2009 - 12:04:30
Réponse à Alain Gottcheiner
Je remercie M. Alain Gottcheiner pour ses commentaires. Comme mon article l'affirmait, la stratégie consistant à regarder les 50 premiers nombres et de s'arrêter ensuite sur le premier nombre record sélectionne le meilleur "dans plus d'un quart des cas". Il est clair que cette stratégie ne sélectionne pas le meilleur nombre avec une probabilité 50/99, puisqu'avec la probabilité 50/100, ce meilleur se trouve dans la première cinquantaine de nombres et n'est donc pas sélectionné. Mon article aurait dû aussi affirmer "dans plus d'un quart des cas (25/99, pour être précis)". (En fait, la stratégie "Regarder les 50 premiers nombres, puis s'arrêter sur un nombre record" est gagnante avec une probabilité notablement supérieure à 1/4, puisque, par exemple, elle est aussi gagnante si le troisième record est dans la première cinquantaine, avec le meilleur et le deuxième meilleur se trouvant tous deux dans la seconde cinquantaine, le deuxième meilleur arrivant après le meilleur.)
Concernant le second point, la version française imprimée (publiée à mon insu), par Pour la Science, de mon article original dans American Scientist a omis la traduction du mot clef "standard" dans "standard Gaussian", termes qui signifient "une loi gaussienne centrée réduite". En utilisant cette loi, l'estimation de la probabilité de 57% citée est juste pour des valeurs de cartes entre 1 et π Toute stratégie randomisée de ce type sélectionnera le plus grand nombre avec une probabilité strictement comprise entre 1/2 et 1, quels que soient la gaussienne particulière utilisée et les nombres inscrits sur les cartes. Comme le suggère l'exemple de A. Gottcheiner, la probabilité résultante de gagner peut en effet être arbitrairement proche de 1/2 ou de 1, en fonction de la gaussienne et des nombres choisis.

La rédaction de Pour la Science11-09-2009 - 12:04:58
Note de la rédaction
Nous tenons à rappeler à nos lecteurs que tous nos articles sont validés par leurs auteurs quand ces derniers sont francophones ou par des scientifiques francophones spécialistes du sujet traité quand les auteurs ne lisent pas le français.

Michel Emery11-09-2009 - 12:05:33
Contradiction ?
Cet article est aussi provocant qu'intéressant, tant certains résultats vont à l'encontre de l'intuition. Toutefois, cet article me semble receler une contradiction : j'y apprends page 26 que Gilbert et Mosteller ont établi l'optimalité de la stratégie consistant à observer un certain nombre de cartes puis à s'arrêter au record suivant. Cela entraîne en particulier que pour un total de N = 2 cartes, la stratégie optimale consiste à choisir systématiquement la première (ou la seconde). Mais un peu plus loin, l'argument de Blackwell établit, de façon tout à fait convaincante, que, pour N = 2, on peut faire mieux. Cela signifie donc que Gilbert et Mosteller n'ont pas envisagé les stratégies à la Blackwell, qui, puisqu'elles permettent de gagner plus d'une fois sur deux lorsque N = 2, devraient aussi permettre de faire mieux pour N = 100. En d'autres termes, les deux affirmations de Theodore Hill, "la stratégie consistant à observer 37 cartes puis à s'arrêter au premier record est la meilleure" et "pour N = 2, on peut gagner plus d'une fois sur deux" ne sont, me semble-t-il, compatibles qu'à condition de changer d'un paragraphe à l'autre le sens de l'expression "stratégie la meilleure"...
Merci à Pour La Science de nous proposer des articles de cette qualité, et continuez, pour notre plus grand plaisir !

Theodore Hill 11-09-2009 - 12:06:16
Réponse à Michel Émery
M. Michel Émery soulève un excellent point sur l'optimalité des stratégies, dont l'essence est une intéressante subtilité mathématique que je n'ai pas traitée dans mon article - à savoir, y a-t-il une différence entre le cas où l'observateur voit les valeurs numériques concrètes des candidats (cartes) et celui où il ne voit que les rangs relatifs des candidats (par exemple, que la première secrétaire est meilleure que la troisième, mais pas aussi bonne que la deuxième, etc.) ?
La stratégie de Gilbert et Mosteller est optimale pour tout N quand l'observateur ne voit que les rangs relatifs, et la découverte de Blackwell a montré que quand N = 2, il peut faire mieux s'il voit les valeurs numériques concrètes. L'existence de meilleures stratégies pour N > 2 quand l'observateur voit les valeurs était un problème non résolu et bien connu jusqu'en 1994, année où Alexander Gnedin a montré (Annals of Probability, 22, pp. 1588-1595) que pour tout N > 2, il n'existe pas de meilleures stratégies que celles de Gilbert et Mosteller. Le cas N = 2 est ainsi unique et, en particulier, dans le cas de 100 candidats, la stratégie de Gilbert-Mosteller "consistant à observer 37 cartes puis à s'arrêter au premier record" est optimale même quand l'observateur peut voir les valeurs concrètes.
Je remercie M. Emery pour sa très pertinente question, et je voudrais aussi remercier mon ami et collègue le Professeur Christian Houdré de m'avoir aidé à réviser la version française mise en ligne (ci-dessus et en PDF) de mon article original publié dans American Scientist, et pour son aide dans ces réponses.

Pascal Minini02-10-2009 - 23:42:24
Quand s'arrêter? Difficile à dire
Cet article est effectivement passionnant pour un féru de probabilités. Merci encore pour la qualité de cet article, et des autres. Je m'interroge sur l'exemple des tirages à pile ou face avec gain égal à la moyenne (en fait la proportion) de faces, problème qui ne semble pas complètement résolu malgré son apparente simplicité. On peut remarquer par exemple que sauf après avoir obtenu face après le premier lancer, on a toujours une probabilité strictement supérieure à 1/2 d'améliorer la moyenne en continuant à lancer la pièce, et ce quelle que soit la moyenne après n lancers. Une limite à ce problème semble être liée à l'absence de fin. Il est difficilement concevable de lancer éternellement la pièce jusqu'à la fin des temps en espérant améliorer sa moyenne ("l'éternité, c'est long, surtout vers la fin"). Je suppose que si l'on imposait un coût à chaque lancer supplémentaire (par exemple 0.01 Krugerrand), le problème serait plus facilement résolu.

Frederic Solbes04-12-2012 - 21:54:11
générer un nombre selon une loi gaussienne ?
Il y a selon moi un gros problème dans l'article, dans ce passage : "Tout d'abord, générez un nombre aléatoire R selon une loi gaussienne centrée réduite à l'aide d'un ordinateur ou d'un autre dispositif." Cela n'a aucun sens ! Vous savez bien qu'un ordinateur ou n'importe quel autre procédé ne peut générer qu'un nombre parmi un nombre fini de possibilités. Du coup, tout ce qui en découle n'est que du vent.
 
 
  1.  ______________Jeu semblable à pile ou face - Proba
  2. Bonsoir à tous
    Voilà je vous pose ce problème :

    Prenons un jeu semblable à celui des pièces: je lance une pièce de monnaie, si ça fait pile je gagne, si ça fait face je perd et je relance, et comme cela indéfiniment jusqu'à ce que ça fasse pile.
    Je dis bien semblable, car la proba à chaque nouveau lancer est de 1/2 de gagner (de faire pile) or dans mon cas de figure la proba à chaque nouveau "lancer" est différent. C'est-à-dire qu'au lieu d'avoir, proba de A: 1/2, proba de B: 1/2, proba de C: 1/2 etc.. on à proba de A: 1/2, proba de B: 1/4, proba de C: 1/6, de D: 1/8 etc...
    C'est comme si au lieu de lancer une pièce de monnaie à deux faces, on lançait au départ une pièce de monnaie à deux faces, puis un dé à 4 faces puis un dé à 6 faces puis un dé à 8 faces puis à 10 faces etc.. avec toujours pour objectif qu'une face précise tombe pour gagner.
    (l'univers concerné est bien infini)

    Dans ce cas, la probabilité de gagner avec A est 1/2, et il y a aussi 1/2 comme proba de ne pas avoir gagné. la probabilité de gagner avec B est alors 1/2 fois 1/4, soit 1/8. Et il reste 3/8 comme probabilité de ne pas avoir encore gagné après 2 coups (donc 5/8 comme proba d'avoir gagné après 2 coups). D'où la probabilité de gagner avec C : 3/8 fois 1/6, et ainsi de suite...

    Le cadre maintenant posé, voici ma question:
    _ Dans le jeu classique de pile ou face, on gagne en moyenne un coups sur 2. Mais ici qu'en est-il? J'ai une petite idée sur la question mais plein de doutes! Je ne dirai rien pour vous laisser toute votre créativité

    _Il me semble que la plus longue série d'une même couleur à une roulette réelle (et non en ligne car je crois que c'est truqué) est été de 27 noirs consécutifs (pour simplifier, on dira qu'il y a 2 couleurs à la roulette: rouge et noir et donc que la proba de tomber sur le noir est 1/2 à chaque coup), il me semble qu'il faut attendre en moyenne 134 217 728 coups pour tomber sur une série aussi longue!
    PS: il faut attendre en moyenne 256 coups pour voir une série de + de 8 couleurs consécutives.

    Mais, en jouant à mon jeu (où les événements sont de + en + incertains) et seulement 200 coups (< à 256), à quelle sorte de mauvaise série puis-je m'attendre à votre avis?
    Honnêtement, je ne sais pas le traduire mathématiquement, ni même ne sais si il est possible de le faire, mais plus de 100 coups à jouer sans gagner ne me semble pas envisageable. Serte tout peut arriver, mais sur toute l'histoire de la roulette 27 noirs consécutifs à été la plus longue série! Et jeter un coup d'œil au PS (serte dans les 2 cas les événements n'ont pas la même proba mais quand même)!

    Essaie-je de "jouer" sur les nombres? peut-être bien, quand on est désespéré lol
    Mais toutes réponses constructives m'intéressent,

    Merci d'avance, Cordialement


 

  • ____________________________________________________________
  1. Bonjour,

    La probabilité de ne pas avoir gagné au tour n est de qui tend vers 0 quand n tend vers l'infini. Donc faire plus de 100 coups sans gagner représente environ une chance sur 1031. Cela "ne vous semble peut-être pas envisageable" mais cela peut arriver. A comparer à la chance sur 10 000 000 d'avoir les 6 bons numéros au loto bien sûr.
    1. "Quand les gens sont de mon avis, il me semble que je dois avoir tort."O.Wilde
  1. 09/03/2011 - 19h19
    Melissa-11









    Date d'inscription
    mars 2011








    Messages
    13

    Exclamation Re : Jeu semblable à pile ou face - Proba

    Bonsoir et merci bcp pour vos réponses!
    En effet, mon jeu peut être traduit par ça:

    On dispose d'une urne avec une boule rouge et une boule noir,

    premier cas: la première boule tirée est rouge et on a donc gagné, dans ce cas on remet la boule rouge dans l'urne et on recommence.

    deuxième cas: la boule tirée est noir, on a perdu, on remet la boule noir dans l'urne et on rajoute 2 autres boules noirs (ainsi il y a 4 boules en tout dans l'urne: 3 noirs et 1 rouge). la deuxième boule tirée est à nouveau noir, on a encore perdu, on remet donc la boule noir dans l'urne et on rajoute encore 2 autres boules noirs (il y a maintenant 6 boules en tout dans l'urne: 5 noirs et 1 rouge ) et on continue à rajouter 2 noirs tant qu'on à pas trouver de rouge.


    Dans ce jeu, si on ne trouve pas la boule rouge assez vite, on se retrouvera avec bcp de boules noirs et donc de + en + difficile de gagner.

    S'il vous plait, connaissez-vous un topic qui a abordé exactement le même sujet, si oui pouvez-vous me fournir le lien?
    Si non, pouvez vous m'exprimer ce jeu mathématiquement, pour que j'essaie d'avoir des éléments de réponses pour savoir si oui ou non ce jeu est profitable au joueur.
    Enfaite ce que je voudrai absolument, c'est savoir si mathématiquement, le joueur est gagnant.

    PS: NicoEnac comme je l'ai dis "Serte tout peut arriver", je sais qu'il y a une probabilité pour qu'au pile ou face, une des faces tombe 100 fois de suite mais comme tu l'as montré cette probabilité est de 10^31 donc plus qu' infime! C'est tellement infime, qui si on va prendre au srx des proba si faible, ça ne vaut pas le coup de jouer, me comprends-tu?
    C'est comme avant même de jouer au poker, on va se dire, "oui mais si l'autre a 5 quinte flush de suite c'est sur que je vais perdre donc vaut mieux ne pas jouer", vois-tu?

    Ce que je veux dire, c'est qu'il est possible que même après 1000 coups je perde toujours je suis d'accord mais, ce que je voudrai savoir, c'est par exemple dans mon jeu (pas pile ou face mais celui de l'urne), dois-je m'attendre à une série de 100 coups sans gagner?

    Merci d'avance, Cordialement.
  1. 09/03/2011 - 19h43
    invite986312212
    Invité

    Re : Jeu semblable à pile ou face - Proba

    avec le jeu que tu as décrit dans le premier post, la probabilité de gagner en 100 coups est d'environ 0.9436515.
  1. 09/03/2011 - 21h25
    Melissa-11









    Date d'inscription
    mars 2011








    Messages
    13

    Smile Re : Jeu semblable à pile ou face - Proba

    Bonsoir,
    Merci bcp Ambrosio de ta réponse,

    lorsque tu dis "avec le jeu que tu as décrit dans le premier post" est-ce que tu veux dire par la que mon premier post ne décrit pas le même jeu que dans le second. Car le deuxième post avec le jeu des urnes, c'est normalement la même chose que le premier poste.
    Enfaite lorsque je disais "on lançait au départ une pièce de monnaie à deux faces, puis un dé à 4 faces puis un dé à 6 faces puis un dé à 8 faces puis à 10 faces etc.. avec toujours pour objectif qu'une face précise tombe pour gagner. " cela devait équivaloir à
    "On dispose d'une urne avec une boule rouge et une boule noir,

    premier cas: la première boule tirée est rouge et on a donc gagné, dans ce cas on remet la boule rouge dans l'urne et on recommence.

    deuxième cas: la boule tirée est noir, on a perdu, on remet la boule noir dans l'urne et on rajoute 2 autres boules noirs (ainsi il y a 4 boules en tout dans l'urne: 3 noirs et 1 rouge). la deuxième boule tirée est à nouveau noir, on a encore perdu, on remet donc la boule noir dans l'urne et on rajoute encore 2 autres boules noirs (il y a maintenant 6 boules en tout dans l'urne: 5 noirs et 1 rouge ) et on continue à rajouter 2 noirs tant qu'on à pas trouver de rouge."

    Ensuite lorsque tu dis "la probabilité de gagner en 100 coups est d'environ 0.9436515.", tu veux bien dire par là que avec mon jeu (et non pile ou face) j'ai quasi 95% de chance de gagner une fois en 100 coups? Comment as tu eu ce résultat, peux-tu m'expliquer ta démarche?

    Merci d'avance, Cordialement
  1. 09/03/2011 - 22h05
    SchliesseB









    Date d'inscription
    novembre 2009








    Messages
    663

    Re : Jeu semblable à pile ou face - Proba

    la probabilité de tirer une noire au premier tour est 1/2
    Alors, la probabilité de tirer une noire au second tour est 3/4
    Alors, la probabilité de tirer une noire au troisième tour est 5/6
    ....
    Alors, la probabilité de tirer une noire au n-ième tour est 1-1/2n

    Ainsi, la probabilité de n'avoir tiré QUE des boules noires sur n tours est:



    La probabilité d'avoir tiré au moins une rouge est donc

    Sauf erreur,
    ça fait:


    soit pour n=100: 94,37% en accord avec Ambrosio.
  1. 10/03/2011 - 00h04
    Melissa-11









    Date d'inscription
    mars 2011








    Messages
    13

    Red face Re : Jeu semblable à pile ou face - Proba

    Bonsoir, merci bcp pour votre réponse SchliesseB!
    Je ne comprend pas les deux points d'exclamations dans votre dernier calcul. Quand j'essaie de taper ce calcul sur ma calculette, le résultat affiché est 1 lol
    Pouvez vous s'il vous plaît faire le calcul pour n=1000 et me dire le résultat?
    Il me semble que le nombre de coups pour être certain de gagner est infini... néanmoins 94,37% de chance de gagner une fois pour 100 coups c'est énorme!

    Enfin, j'aimerai bien prendre également en compte ce jeu:
    On dispose d'une urne avec deux boules rouges et une boule noir,

    premier cas: la première boule tirée est rouge et on a donc gagné, dans ce cas on remet la boule rouge dans l'urne et on recommence.

    deuxième cas: la boule tirée est noir, on a perdu, on remet la boule noir dans l'urne et on rajoute 3 autres boules noirs (ainsi il y a 6 boules en tout dans l'urne: 4 noirs et 2 rouges). la deuxième boule tirée est à nouveau noir, on a encore perdu, on remet donc la boule noir dans l'urne et on rajoute encore 3 autres boules noirs (il y a maintenant 9 boules en tout dans l'urne: 7 noirs et 2 rouges ) et on continue de rajouter 3 noirs tant qu'on à pas trouver de rouge."

    Ainsi au lieu d'avoir "proba de A: 1/2, proba de B: 1/4, proba de C: 1/6, de D: 1/8 etc..." on a proba de A: 2/3, proba de B: 2/6, proba de C: 2/9, proba de D: 2/12 etc....

    Enfaite au lieu d'avoir: 1/2 puis 1/4 puis 1/6 etc.. on a 1/1,5 puis 1/3 puis 1/4,5 puis 1/6 .... voyez.
    Dans ce second jeu, la proba de tirer un rouge en 100 coups est de cb? elle doit être supérieur à celle du premier jeu. A mon avis, proche de 99%

    Merci d'avance pour vos réponses, Cordialement
    PS: je crois qu'je vous embêterez plus après ça ^^ encore merci
  1. 10/03/2011 - 00h38
    SchliesseB









    Date d'inscription
    novembre 2009








    Messages
    663

    Re : Jeu semblable à pile ou face - Proba

    est le symbole factorielle.
    http://fr.wikipedia.org/wiki/Factorielle



    par exemple:


    pour n=1000, on trouve que la probabilité de gagner au premier jeu est de 98,21%.
    Et oui, "Il me semble que le nombre de coups pour être certain de gagner est infini... néanmoins 94,37% de chance de gagner une fois pour 100 coups c'est énorme! " est juste.

    pour le second jeu, on fait le même raisonnement:
    la probabilité de tirer une noire au premier tour est 1/3 (1 noire/2 rouges)
    Alors, la probabilité de tirer une noire au second tour est 4/6 (4 noires/2rouges)
    Alors, la probabilité de tirer une noire au troisième tour est 7/9 (7 noires/2rouges)
    ....
    Alors, la probabilité de tirer une noire au n-ième tour est 1-2/3n (2 rouges pour 3n boules)

    la probabilité cherchée est donc:


    on peut sûrement l'écrire avec des factorielles comme pour l'autre...
    Cliquez pour afficher


    pour n=100: 98.26%

    pour n=1000: 99.62%
  1. 10/03/2011 - 01h01
    Melissa-11









    Date d'inscription
    mars 2011








    Messages
    13

    Smile Re : Jeu semblable à pile ou face - Proba

    Géniaal!
    Merci bcp SchliesseB c'est exactement ce que je voulais

    Et crois-tu qu'il est possible de faire une sorte de "moyenne" des proba? Par exemple pour les 5 premiers coups on a les probas suivantes: 1/2 puis 1/4 puis 1/6 puis 1/8 puis 1/10, crois-tu qu'il est possible de faire une moyenne de ces proba afin d'avoir 5 évènements équiprobables qui soient dans leur ensemble "identique" à ces 5 coups ci ?

    Par exemple au lieu d'avoir 1/2 puis 1/4 puis 1/6 puis 1/8 puis 1/10 on aurait 1/X puis 1/X puis 1/X puis 1/X puis 1/X.

    Ca m'aiderait à comparer ce jeu à celui du pile ou face ^^

    Merci d'avance, Cordialement
  1. 10/03/2011 - 01h07
    Melissa-11









    Date d'inscription
    mars 2011








    Messages
    13

    Smile Re : Jeu semblable à pile ou face - Proba

    PS: n'est-ce pas plutôt "2^n*n²" et non pas "2^2n*n²" dans ta pré-précédente réponse (le dernier calcul encore)? ^^
    dsl du double post
    Merci
  1. 10/03/2011 - 09h02
    SchliesseB









    Date d'inscription
    novembre 2009








    Messages
    663

    Re : Jeu semblable à pile ou face - Proba

    Citation Envoyé par Melissa-11 Voir le message

    Par exemple au lieu d'avoir 1/2 puis 1/4 puis 1/6 puis 1/8 puis 1/10 on aurait 1/X puis 1/X puis 1/X puis 1/X puis 1/X.

    Ca m'aiderait à comparer ce jeu à celui du pile ou face ^^

    Merci d'avance, Cordialement
    Si j'ai bien compris:
    tu cherches tel que (premier cas)



    Je ne vois pas ce que tu peux en dire de plus (passer au log?). Tu n'arriveras pas à mon avis à trouver simplement X. Tu pourras au mieux trouver un équivalent de en l'infini.


    Sinon je ne vois pas d'erreur. Mais je me suis peut-être trompé
  1. 10/03/2011 - 10h09
    NicoEnac









    Date d'inscription
    juin 2008








    Âge
    27








    Messages
    1 394

    Re : Jeu semblable à pile ou face - Proba

    Citation Envoyé par NicoEnac Voir le message
    Bonjour,

    La probabilité de ne pas avoir gagné au tour n est de qui tend vers 0 quand n tend vers l'infini. Donc faire plus de 100 coups sans gagner représente environ une chance sur 1031. Cela "ne vous semble peut-être pas envisageable" mais cela peut arriver. A comparer à la chance sur 10 000 000 d'avoir les 6 bons numéros au loto bien sûr.
    Désolé
________________________________________________________________________________
Marche al´eatoire
De la marche au hasard de l’ivrogne “mod`ele” qui oublie `a chaque instant d’ou` il vient et ou` il veut aller, au mouvement brownien d’une particule collo¨ıdale en suspension dans un fluide mol´eculaire, en passant par l’´evolution d’actifs financiers, une marche al´eatoire est d´ecrite par un processus stochastique en termes de probabilit´e. La mod´elisation et la compr´ehension d’un tel processus s’inscrivent pleinement dans le cadre de la physique mais sont ´egalement `a la base de la mod´elisation financi`ere depuis les travaux pr´ecurseurs de Louis Bachelier en 1900, cinq ans avant l’´etude du mouvement brownien par Albert Einstein. En effet, quel que soit l’actif financier (action, obligations, mati`erepremi`ere...) on observe la mˆeme forme d’´evolution erratique dans le temps. Cette r´egularit´e, qui r´esulte pourtant des actions innombrables d’individus dont les motivations propres ne sont pas forc´ement rationnelles, sugg`ere une possible mod´elisation. En partant d’un mod`ele simple sur r´eseau, comme le jeu de pile ou face, nous pr´esenterons des r´esultats non triviaux et contraires `a l’intuition qui nous permettrons, `a la limite continue, d’aborder les ph´enom`enes de diffusion en termes d’´equations stochastiques. Enfin, nous introduirons le mod`ele de BlackScholes, pierre angulaire de la mod´elisation financi`ere. Mais pour commencer, int´eressons-nous `a un mod`ele ph´enom´enologique historique : l’´equation de Langevin.


____________Loi de l’arcsinus
Au jeu de pile ou face, l’intuition sugg`ere que le gain d’un joueur (partant de 0) oscille fr´equemment autour de 0. Ainsi, si on interrompt une longue partie, la probabilit´e que le dernier passage `a l’origine soit ancien devrait ˆetre faible. Comme nous allons le voir, ce n’est pas le cas. En particulier, nous verrons que la probabilit´e qu’il n’y ait pas eu de retour `a l’origine durant la seconde moiti´e du jeu, et ce quelle que soit sa dur´ee, est ´egale `a 50%!
_______________________________________________________________

2.5. CHAˆINE DE MARKOV 61
2.5 Chaˆıne de Markov
Reprenons la marche al´eatoire ´etudi´ee `a la section 2.2.1. Les sauts successifs Xn sont des variables al´eatoires ind´ependantes, en revanche, les positions successives de la particule (la fortune du joueur) ne sont pas ind´ependantes : la position Sn au temps n d´epend de la position Sn−1 au temps n−1 par la relation (2.4). Le point important est que la position `a un instant donn´e n ne d´epend que de la position `a l’instant ant´erieur n−1 et non pas de toute l’histoire de la particule aux temps 0,1,2,... : Le futur ne d´epend du pass´e que par l’interm´ediaire du pr´esent. Cette marche al´eatoire est appel´ee une chaˆıne de Markov.22 Les chaˆınes de Markov,qui jouent un roˆle fondamental en finance, repr´esentent une forme de causalit´einterm´ediaireentre les processus compl`etement ind´ependants et les processus avec histoire compl`ete (la r´ealisation `a l’instant n d´epend de celles `a tous les instants ant´erieurs 0,1,2,...).

_____________________________________________________________________________

On a en particulier
P{τ0 = +∞} = 0 si p = 1/2, > 0 si p 6= 1/2. Ce résultat signi e que pour une marche équilibrée (p = 1/2), le marcheur repassera presque sûrement (i.e. avec probabilité 1) par sa position initiale : on parle de marche récurrente, alors que dans le cas d'une marche désiquilibrée (p 6= 1/2), il y a une dérive vers +∞ si p > 1/2, vers −∞ si p < 1/2 et le retour à l'origine pourrait se produire, mais ce avec une probabilité inférieure à 1. Dans ce cas il y a une probabilité non nulle de ne jamais retourner à l'origine : on parle de marche transitoire ou transiente.

_____________________________________________________________________________
A.1 Loi de Bernoulli et loi binomiale Une variable aléatoire X prenant les deux valeurs 0 et 1 avec les probabilités respectives 1−pet p suit la loi de Bernoulli de paramètre p. Soient X1,...,Xn des variables aléatoires indépendantes de Bernoulli de paramètre commun p. La variable aléatoire S = X1 +···+ Xn, représente le nombre de 1 obtenus parmi les X1,...,Xn ; elle suit la loi binomiale de paramètres (n,p). Cette loi de probabilité est donnée par P{S = k} = n k pkqn−k, k ∈{0,1,...,n}.


Publié par à

Aucun commentaire:

Enregistrer un commentaire

Inscription à : Publier les commentaires (Atom)