Les séries de victoires
Salut,
Je m'interrogeais un peu sur un jeu vidéo auquel je joue, parce que j'ai l'impression de régulièrement enchaîner les victoires et les défaites, et je me demande parfois si le matchmaking est totalement aléatoire. Sans parler du jeu en lui-même, qui n'est pas vraiment le sujet ici, j'aimerais comprendre un peu les probas qui gouvernent les séries de victoire.
Imaginons que je lance une pièce, elle a une probabilité p de tomber sur pile (victoire), et 1-p de tomber sur face.
J'aimerais calculer la probabilité, après n lancers, d'avoir obtenu une série maximum de k victoires, que j’appellerai P(n,k,p).
Une des idées à laquelle j'ai pensé, pour faire ça, sont les chaînes de Markov. On pose les \(N^2\) états \(E_{i,j}\), avec i et j variant de 1 à n.
i correspond à la valeur de la winstreak en cours, j correspond à la valeur de la winstreak maximale déjà effectuée.
On en déduit alors la probabilité de passage d'un état à un autre assez facilement. Par exemple, si on est à l'état \(E_i,j\) , alors on passe à l'état \(E_ {i+1,j}\) en cas de victoire (proba p), ou \(E_{0,j}\) en cas de défaite (proba 1-p). (ou \(E_{i+1, i+1}\) si on gagne et que i = j).
On peut alors facilement déterminer la matrice de transition, les probabilités finale d'arriver à tel ou tel état, et en déduire les probabilités de winstreak de chaque joueur. L'inconvénient majeur, bien sûr, c'est que ça nécessite de faire des calculs matriciels sur des matrices (\(N^2\), \(N^2\)), avec des temps d'éxécution en \(N^6\).
Rien que mon ordi ne puisse pas faire, somme toute, mais j'aimerais savoir s'il existe des solutions plus élégantes que la première qui m'est venue en tête.
Merci et bonne soirée.
Je m'interrogeais un peu sur un jeu vidéo auquel je joue, parce que j'ai l'impression de régulièrement enchaîner les victoires et les défaites, et je me demande parfois si le matchmaking est totalement aléatoire. Sans parler du jeu en lui-même, qui n'est pas vraiment le sujet ici, j'aimerais comprendre un peu les probas qui gouvernent les séries de victoire.
Imaginons que je lance une pièce, elle a une probabilité p de tomber sur pile (victoire), et 1-p de tomber sur face.
J'aimerais calculer la probabilité, après n lancers, d'avoir obtenu une série maximum de k victoires, que j’appellerai P(n,k,p).
Une des idées à laquelle j'ai pensé, pour faire ça, sont les chaînes de Markov. On pose les \(N^2\) états \(E_{i,j}\), avec i et j variant de 1 à n.
i correspond à la valeur de la winstreak en cours, j correspond à la valeur de la winstreak maximale déjà effectuée.
On en déduit alors la probabilité de passage d'un état à un autre assez facilement. Par exemple, si on est à l'état \(E_i,j\) , alors on passe à l'état \(E_ {i+1,j}\) en cas de victoire (proba p), ou \(E_{0,j}\) en cas de défaite (proba 1-p). (ou \(E_{i+1, i+1}\) si on gagne et que i = j).
On peut alors facilement déterminer la matrice de transition, les probabilités finale d'arriver à tel ou tel état, et en déduire les probabilités de winstreak de chaque joueur. L'inconvénient majeur, bien sûr, c'est que ça nécessite de faire des calculs matriciels sur des matrices (\(N^2\), \(N^2\)), avec des temps d'éxécution en \(N^6\).
Rien que mon ordi ne puisse pas faire, somme toute, mais j'aimerais savoir s'il existe des solutions plus élégantes que la première qui m'est venue en tête.
Merci et bonne soirée.
Réponses
-
C'est probablement la solution la plus élégante que tu as trouvée ! Tu peux aussi considérer une chaine de Markov plus simple qui aurait comme état uniquement le record "en cours" dans $\{0,1,2,...,k\}$, avec comme état absorbant $\{k\}$, il y a eu une discussion ces derniers mois sur le forum avec bizarrement le titre "écart max". Ça ne te fait que $k+1$ états.
Il y a aussi une approche par série génératrice qui est faite dans le livre de Flajolet-Sedgewick sous le nom de " longest run". C'est peut-être plus efficace algorithmiquement si tu cherches des formules exactes en $p$.
Amuse-toi bien! -
En effet, c'est peut-être plus malin de ne considérer que k états, comme tu me l'as conseillé, ce qui donnera plutôt la probabilité que la série obtenue soit supérieure à k après n lancers (mais on en déduit la probabilité que la série soit exactement k assez facilement par soustraction ensuite). Je vais essayer avec ce que tu m'as dit, les calculs devraient être plus raisonnables.
Bon après il faut calculer cette proba pour tous les k. Mais ça reste quand même une complexité bien meilleure que ce je proposais.
Je suis également allé voir le thread écart-max, c'est vrai qu'il y a pas mal d'infos intéressantes, mais bon faut faire le tri parce que l'intervenant n'avait pas l'air de comprendre ce qui se passait, et ses interventions pour rien dire polluent vraiment la discussion. :-D
Pour l'article mathématique ça m'avait l'air complexe, pas sûr que j'ai le courage de le lire :-) Mais bon sait-on jamais ?
En tout cas merci pour ta réponse, et bonne journée ! -
Bonsoir,
Ce qui suit donne une relation de récurrence simple qui permet de calculer la probabilité cherchée.
Je fixe la probabilité $p$ d'obtenir $"\text{Pile}",\:$ je note $q=1-p,\:$ et pour tous $ \: k,n$ dans $\N^*,\:$ je désigne par $\: P_k(n) $ la probabilité d'obtenir, au cours d'une série de $n$ lancers de pièce consécutifs, une séquence d'au moins $k$ $\:"\text{Pile}"$ consécutifs.
Alors: $ \:\:\:\forall n \in [\![1;k-1]\!], \:\: P_k(n) =0, \:\:P_k(k) =p^k,\:\: \:\:P_k(k+1) =p^k(2-p) ,$
$$\boxed{\forall n>k \quad P_k(n+1) = P_k(n)-qp^k P_k(n-k) +qp^k.}$$ -
J'essaie de comprendre ce que je peux, mais j'avoue que ce n'est pas facile (:P)
Pour la première ligne que tu écris : $ \ \forall n \in [\![1;k-1]\!], \ P_k(n) =0, \ P_k(k) =p^k,\ P_k(k+1) =p^k(2-p) .$
Pas de soucis.
Pour la deuxième ligne, j'avoue ne pas comprendre d'où ça sort. J'imagine que c'est sûrement en lien avec ta réponse dans le précédent sujet, sur la manière de dénombrer le nombre de manière d'obtenir des séries de d'au moins k 0 dans \([0,1]^{n}\), que je n'avais déjà pas compris. -
Bonjour,
@gasasaaa Voici quelques explications:
Notons $\:U_k (n) := 1 -P_k(n),\: $ et $\:\: \forall i \in \N^*,\:\: E_i $ l'événement : $\:\: \text {le i-ème lancer donne "pile"}$.
$U_k(n)$ est donc la probabilité de n'obtenir aucune sequence de $k \:\text{"pile"}$ au cours des $n$ lancers.
Alors: $\forall n>k, \:\:\: U_k(n) = \Pr ( \overline {E_1})\times U_k(n-1) + \Pr ( E_1\cap \overline {E_2})\times U_k(n-2) +\dots \Pr (E_1 \cap \dots E_{k-1} \cap \overline {E_k}) \times U_k(n-k).\quad$ Ainsi : $$\:\:U_k(n) = \displaystyle \sum _{i=1} ^k qp^{i-1} U_k(n-i). \quad (1)$$
En appliquant $(1)$ à $U_k(n)$ et à $U_k(n+1)$, on obtient: $\quad U_k(n+1) -p U_k(n) = qU_k(n)-qp^k U_k(n-k)$
$U_k(n+1) = U_k (n) - qp^k U_k(n-k), \qquad \boxed{P_k(n+1) = P_k(n) - qp^k P_k(n-k) + qp^k.}$
Bien entendu, le polynôme caractéristique de la récurrence linéaire vérifiée par la suite $(U_k(n))_n$ est étroitement lié à celui de la matrice de transition décrivant la chaîne de Markov à $k+1$ états précédemment évoquée. En effet, ces deux polynômes sont égaux, au facteur $(X-1)$ près. -
Ok c'est très clair merci !
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 9
+7 Invités