Retournement de pièces

Ben314159

Bonjour,
Je viens de retomber sur un vieux case-tête dont la solution m'avait un peu surpris :

Sur une table, $n$ pièces de monnaie sont posées avec leur coté "pile" visible. On choisi au hasard (et avec équiprobabilité) une pièce et on la retourne. On recommence l'opération tant qu'il reste au moins une pièce avec son coté "pile" visible.

Q1) Combien faut-il, en moyenne, d'étapes pour aboutir ?
Q2) Quelle est la probabilité qu'on aboutisse sans jamais être repassé par l'état initial ?
Q3) Cette probabilité admet-elle un maximum ? un minimum ?

On pourra éventuellement chercher un comportement asymptotique lorsque $n\to\infty$ pour les questions 1 et 2.

LOU16

Bonjour
Pour la première question, en notant $T$ le nombre de tirages nécessaires à la disparition des faces visibles PILE, $ \mathbb E(T)$  peut être obtenu avec "l'analyse du premier pas" et le système linéaire qui en découle et qui met en jeu les matrices suivantes :

$A=(a_{ij})_{1\leqslant i, j \leqslant n}\in \mathcal M_n(\R) $ définie par:$ \begin{cases} a_{ij} =0 \:\text { si }\: |i-j|\neq 1,\\  \forall i \in [\![1;n-1]\!],\:\:a_{i,i+1} =n+1-i, \quad a_{i+1,i} =i.\end{cases}\:$ et $\:\quad M =\mathrm I_n-\dfrac 1nA, \:\: M^{-1} =(m_{ij})_{1\leqslant i,j\leqslant n}$

$$\text{Alors }\quad\mathbb  E(T) =\displaystyle \sum_{j =1}^n m_{1 j}.$$

Bien que la matrice $M$ possède beaucoup de coefficients nuls, je n'ai pas trouvé d'expression simple des $m_{1j} $ en fonction de $n.$

Ben314159

Il y a deux expressions de l'espérance sous forme de somme (de 1 à n) de choses simples (dont une particulièrement simple et c'est l'égalité entre les deux expressions qui m'avait surpris dans le temps).
Perso, j'avais plutôt procédé en disant que l'espérance cherchée, c'est la somme des espérances des temps pour passer de k pièces O.K. à k+1, mais avec des processus stochastiques, tu devrais tomber sur les mêmes équations.

GaBuZoMeu

Bonjour
Je trouve, plutôt expérimentalement : $$2^{n-1} \sum_{i=0}^{n-1} \frac1{\binom{n-1}{i}}\;.$$
Pour 5 pièces par exemple, $42\frac23$.
Pour l'asymptotique, c'est équivalent à $2^n$.

cailloux

Bonjour,
... qu'on peut aussi écrire :  $$n\sum_{k=1}^n\dfrac{2^{k-1}}{k}$$

GaBuZoMeu

Pour Q3, je dirais minimum 3/8 et maximum 1/2 (mais là encore , c'est plutôt expérimental !).

Ben314159

Concernant les deux formules, c'est bien ça (et ça m'avais un peu surpris qu'on puisse simplifier la somme des inverses des coefficients binomiaux).
Et, effectivement, l'autre truc éventuellement contre intuitif (en tout cas pour moi), c'est que là où on a le moins de chances d'arriver au but sans être repassé par la situation initiale, c'est lorsqu'il y a 4 ou 5 pièces (avec p=3/8) : On pourrait penser que, quand les pièces augmentent, ça va être de moins en moins probable de finir sans repasser par la case départ.  Sauf que, quand les pièces augmentent, on a de moins en moins de chance de perdre dés le deuxième coup en re-retournant la première pièce retournée . . .

EDIT : et pour le max., c'est bien 1/2, modulo de lire correctement l'énoncé où, exceptionnellement, je n'ai pas fait de faute d'orthographe et où j'ai mis un "s" à pièces (donc $n\geqslant2$)

Georges Abitbol

Mon idée intuitive est que pour $n$ grand, on se perd en très peu de temps dans le « milieu » du groupe $\mathbb{Z}/2\mathbb{Z}^n$, à savoir la partie dont les éléments ont presque autant de $0$ que de $1$. Or les deux configurations en question sont opposées (symétriques) par rapport à ce milieu, et donc une fois qu’on est au milieu, autant de chance d’arriver à l’une qu’à l’autre.

Lucas

Bonjour,
Pour ceux et celles qui sont intrigués par ces formules, il y a des choses très jolies racontées à-dessus dans l'article :
N.Pippenger. The Hypercube of Resistors, Asymptotic Expansions, and Preferential Arrangements.
Mathematics Magazine, Vol. 83, No. 5 (December 2010)
L'équation (4) dans cette référence est une reformulation de la remarque de @cailloux . En effet, il y a un lien entre les temps d'atteinte de la marche aléatoire sur un graphe (ici, l'hypercube), et le calcul de certaines résistances équivalentes.

jandri

Merci pour cet article très intéressant. On peut le lire ici : The Hypercube of Resistors

PetitLutinMalicieux

Bonjour

Avec n pièces, je considère n+1 populations qui vont de (n,0) à (0,n). Et ceci me donne le graphe suivant pour chaque retournement :

Et avec n=7 et mon tableur préféré, on arrive à la matrice de transition suivante :

Puis un produit matriciel répété nous montre que la situation se stabilise autour de 2 états stables alternés :

1,000	0,000	0,000	0,000	0,000	0,000	0,000	0,000
(...)
0,000	0,109	0,000	0,547	0,000	0,328	0,000	0,016
0,016	0,000	0,328	0,000	0,547	0,000	0,109	0,000
0,000	0,109	0,000	0,547	0,000	0,328	0,000	0,016
0,016	0,000	0,328	0,000	0,547	0,000	0,109	0,000

Notez la symétrie entre les deux lignes.

Ces nombres veulent dire qu'une fois sur deux, 1,6% des cas arrivent à l'objectif et 1,6% reviennent au point de départ (pas dans le même retournement, bien sûr). De la même manière, une fois sur deux, ces évènement sont impossibles. Mais cela tient à la parité de la quantité de population, donc l'imparité du nombre de pièces. Avec un nombre pair de pièces, on peut parier que 1 cas sur 2, on obtient rien (ni retour à zéro, ni l'objectif), et 1 cas sur 2 les 2 évènements recherchés sont possibles.

Idées en vrac.

Titi le curieux

Bonjour, 
 Je n'y arrive pas, je suis aussi passé par une matrice de Markov (avec je précise $a_{n,n}=1$ et $a_{n,n-1}=0$ pour le cas de la question 1 et en ajoutant encore des conditions similaires pour l'état 0 après le tour 1 dans la question 2). Pour diviser en gros le nombre d'états par 2 je fais par pas de deux lancers (ça implique quand même d'ajouter un état pour la question 2 dans les cas où $n$ est impair). 
Et après je cherche les valeurs propres des matrices et sachant que la probabilité d'avoir fini est nulle avant le tour $n$ je résous un petit système d'équation pour avoir mes constantes dans ma probabilité d'avoir fini au $k$ ième essaie (pour la question 1 c'est 1 moins une somme de termes géomètriques, chacun ayant pour pas une des autres valeurs propres de la matrice). 

C'est pas top, un peu compliqué et en supposant que je sois capable de trouver les racines d'un polynôme de degré 4, je suis au mieux capable de trouver la solution formelle jusqu'au cas $n=9$ pour la question 1 et $n=10$ pour la question 2.

Bref, je suis super intéressé pour connaître la méthode d'une des trois personnes qui as trouvé (Ben314, GaBuZoMeu et cailloux), parce que je sèche complètement (s'il vous plaît). 
Merci d'avance

Ben314159

La façon dont j'avais procédé (en essayant de rester le plus rudimentaire possible)

Titi le curieux

Super, merci! 

Lucas

Au fait, personne n'a jamais mentionné le nom dans le fil mais il s'agit de l'urne d'Ehrenfest. J'en profite pour donner une autre référence qui considère des temps d'atteinte pour Ehrenfest :
Another Look at the Ehrenfest Urn via Electric Networks
José Luis Palacios.Advances in Applied Probability, Vol. 26, No. 3 (Sep., 1994)

cailloux

Bonsoir
@Titi_le_curieux
Tu peux m'effacer de tes tablettes. Je n'ai pas touché aux probabilités dans ce fil.
Je me suis limité à rappeler une égalité (plus ou moins connue sous une forme ou une autre) :
$$2^{n-1} \sum_{i=0}^{n-1} \frac1{\binom{n-1}{i}}=n\sum_{k=1}^n\dfrac{2^{k-1}}{k}$$
Clairement : je n'ai rien "trouvé" du tout.

jandri

Merci à @Ben314159  pour son étude détaillée.

On peut donner une démonstration plus courte du développement asymptotique de $\sigma_{n-1}$ en partant de $\sigma_{n-1} = 1 +\dfrac{n}{2(n-1)} \sigma_{n-2}$ :

\begin{align*}2\displaystyle\sum_{k=0}^p\dfrac{a_k}{n^k}&=1+n\sum_{k=0}^p\dfrac{a_k}{(n-1)^{k+1}}+o(1/n^p)\\&=1+\sum_{k=0}^p\dfrac{a_k}{n^k}\sum_{j\ge k}\dfrac{\binom{j}{k}}{n^{j-k}}+o(1/n^p)\end{align*}

D'où l'on déduit $a_0=1$ et $2a_p=\displaystyle\sum_{k=0}^p\binom{p}{k}a_k$ qui est la définition de la suite des nombres de Fubini.