[Maths] Marathon de problèmes

a marqué ce sujet comme résolu.
Banni

@elegance

Intuitivement, si la probabilité p est supérieure à 0.5, il faut faire ’tapis’. On a une probabilité supérieure à 50% de faire le score maximum, et donc de gagner (ou match nul si l’adversaire choisit la même stratégie et gagne le maximum de jetons).

À peu près oui, mais il faut faire attention au fait que l’autre stratégie peut aussi gagner tous les points (il y a en fait trois issues possibles : gagner, perdre ou partie nulle). Il est possible de trouver une valeur de $p$ (qui est strictement supérieure à 1/2) à partir de laquelle aucune stratégie ne bat cette consistant à tout miser.

Je joue un seul jeton., uis encore un seul jeton et encore un seul jeton … A priori, mon adversaire joue come moi, parce que lui aussi à réfléchi. Si à un moment, je considère que j’ai eu très peu de chance (par exemple au bout de 20 jetons, je n’ai eu aucun coup gagnant, alors que la probabilité théorique est de 40% de gain à chaque lancer), alors je pense que j’ai un retard significatif, je n’ai plus de chance de gagner avec cette stratégie, et je dois donc faire tapis.

Déjà, quand on dit « gagner », ça dépend contre quelle autre stratégie, et en plus on veut maximiser ses chances de gagner, bref c’est un peu complexe. En faisant ce que tu dis, on va être battu par une stratégie qui continue à miser un par un jusqu’à la fin (si $p<1/2$), pour la même raison que l’on a plus intérêt à miser un par un au début.

Et même, si on a beaucoup de jetons au départ, la stratégie parfaite est probablement de jouer 1 jeton à la fois au début, puis 2 jetons à la fois si on a un retard significatif, puis 3 à la fois…

Il est possible a priori qu’il n’y ait pas de stratégie parfaite. C’est pour ça que je parlais de phénomènes non transitifs. Je ne suis pas convaincu par ce que tu dis car une stratégie battant la stratégie « tout miser » pour $p$ compris entre 0 et une valeur critique fait un peu le contraire…

Si on a 1000 jetons au départ, si p vaut 40%, et si au bout de 100 jetons joués, j’ai gagné seulement 25 points, je suis 15 points en retard par rapport à l’espérance normale. En jouant 1 pion par 1 pion, je joue la stratégie qui donne une très faible variance, je me donne peu de chances de faire plus de 40% sur les 900 pions restants. En jouant les pions 5 par 5 ou 10 par 10, l’espérance est la même, mais la variance est plus élevée, j’augmente donc mes chances de rattraper mon retard.

Mais tu augmentes aussi tes chances de creuser ton retard. Bref c’est pas clair. De toute manière il faudra bien faire des calculs quelque part si on veut dire quelque chose.

Déjà, chaque stratégie (pour un nombre de jetons $n$ fixé) peut être représentée sous forme d’arbre binaire entier étiqueté par des entiers positifs et tel que la somme sur chaque chemin menant de la racine à une feuille soit $n$.

J’ai fait un code Python pour tester les stratégies.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from random import random

class Checker:
  def __init__(self,n,p):
    self.n = n
    self.p = p
    self.nonplayed = n
    self.played = 0
    self.score = 0
  
  def play(self,m):
    if m > self.nonplayed:
      m = self.nonplayed
    self.score += int(random() < self.p) * m
    self.played += m
    self.nonplayed -= m

def play_game(strat,n,p):
  ch = Checker(n,p)
  strat(ch)
  return ch.score

def prob_win(stratA, stratB, n, p, *, nb_tries=10**5):
  nb_gt = 0
  nb_eq = 0
  nb_lt = 0
  for _ in range(nb_tries):
    sa = play_game(stratA,n,p)
    sb = play_game(stratB,n,p)
    if sa > sb:
      nb_gt += 1
    elif sa == sb:
      nb_eq += 1
    elif sa < sb:
      nb_lt += 1
  return (nb_gt/nb_tries, nb_eq/nb_tries, nb_lt/nb_tries)

def stratA(checker):
  checker.play(checker.n)

def stratB(checker):
  for i in range(checker.n):
    checker.play(1)

print(prob_win(stratA, stratB, 100, 0.3))
+0 -0

Appelons les deux joueurs Bob et Alice. On cherche à étudier la meilleur stratégie (entre les stratégies $A$ et $B$) que doit adopter Bob suivant le paramètre $p$. Pour cela on $4$ cas de figure : - Bob adopte la stratégie $A$ et Alice la stratégie $B$ - Bob adopte la stratégie $B$ et Alice la stratégie $A$ - Bob et Alice adoptent la stratégie $A$ - Bob et Alice adoptent la stratégie $B$

Pour l’étude de chacun de ces cas de figure on est obligé de se placer sur des espaces probabilisables différents (j’ai du mal à voir comme on pourrait définir une probabilité qui convienne pour chacun des espaces). Dans la suite nous allons représenter une partie par des $n-$uplets à valeurs dans $\{0, 1\} \times \{0, 1\}$. $0$ correspondant à la perte d’un pion sans gain de point et $1$ au gain d’un point.

Pour le premier cas de figure nous allons prendre comme ensemble des réalisations $\Omega = \{\{0\} \times \{0, 1\} \}^n \bigcup \{\{1\} \times \{0, 1\} \}^n $, pour tribu des événements $\mathcal{P}(\Omega)$. Maintenant l’idée c’est d’essayer de définir une probabilité $P_1$ sur notre espace $(\Omega, \mathcal{A})$. En notant $A$ l’événement : "Bob à $0$ points et Alice en gagne $k$". Alors on peut définir naturellement  :

$$P_1(A) = (1-p) \cdot p^k \cdot (1-p)^{n-k} = p^k \cdot (1-p)^{n-k+1} $$

De la même manière en notant $B$ l’événement : "Bob gagne $n$ points et Alice en gagne $k$". Alors :

$$P_1(B) = p \cdot p^k \cdot (1-p)^{n-k} = p^{k+1} \cdot (1-p)$$

Sur $(\Omega, \mathcal{A}, P_1)$, la probabilité que Bob gagne (gagne veut dire qu’il n’y a pas match nul) est alors de :

$$P_1(\text{gain de Bob}) = p \cdot \sum_{i = 0}^{n-1} \binom{n}{ i} p^i \cdot (1-p)^{n-i} = p \cdot (1-p^n) = p-p^{n+1}$$ De manière similaire on trouve (on se place plutôt sur un ensemble $(\Omega_2, \mathcal{P}(\Omega_2))$ ou $\Omega_2 = \{\{0,1\} \times \{0\} \}^n \bigcup \{\{0,1\} \times \{1\} \}^n$ pour $P_2$, puis sur $(\Omega_3, \mathcal{P}(\Omega_3))$ avec $\Omega_3 = \{\{0\} \times \{0\} \}^n \bigcup \{\{1\} \times \{0\} \}^n \bigcup \{\{1\} \times \{0\} \}^n \bigcup \{\{1\} \times \{01\} \}^n$ pour $P_3$...) : $$P_2(\text{gain de Bob}) = 1-P_2(\text{Alice gagne } 0 \text{ points}) = 1-P_1(\text{gain de Bob}) = 1-(p-p^{n+1}) = 1-p + p^{n+1}$$
$$P_3(\text{gain de Bob}) = P_3(\text{Alice gagne } 0 \text{ points}) \cdot P_3(\text{Bob gagne } n \text{ points}) = p \cdot (1-p)$$ $$P_4(\text{gain de Bob}) = \sum_{i = 1}^n P_4(\text{Bob gagne } i \text{ points}) \sum_{j = 0}^{i-1} P_4(\text{Alice gagne } j \text{ points}) = \sum_{i = 1}^n \binom{n}{i}p^i(1-p)^{n-i} \sum_{j = 1}^{i-1} \binom{n}{j}p^j(1-p)^{n-j}$$

On en conclu que la probabilité que Bob gagne en employant la stratégie $A$ est de :

$$\mathcal{G}(p) = P_1(\text{gain de Bob}) + P_3(\text{gain de Bob}) = p-p^{n+1}+p-p^2 = 2p-p^2-p^{n+1}$$

La probabilité que Bob gagne avec la stratégie $B$ est donc de :

$$\mathcal{K}(p) = P_2(\text{gain de Bob})+P_4(\text{gain de Bob}) = 1-p+p^{n+1} + \sum_{i = 1}^n \left (\binom{n}{i}p^i(1-p)^{n-i} \sum_{j = 1}^{i-1} \binom{n}{j}p^j(1-p)^{n-j} \right)$$

On a donc considérer que l’adversaire choisi une stratégie avec la probabilité uniforme donc ici puisqu’il y a que deux stratégies cela correspond à une probabilité de $1/2$. $\mathcal{G}(p)$ est plus commode à étudier néanmoins à moins d’avoir mal compris quelque chose il me semble difficile d’avoir des valeurs exactes de $p$ pour lesquelles la stratégie $A$ gagne par rapport à celle de $B$. On peut par contre faire comme élégance et conjecturer des résultats par rapport aux valeurs obtenues.

+0 -0
Banni

La question est : quand on fait jouer la stratégie A contre la B, est-ce qu’il y a plus de chances que ce soit la A ou la B qui gagne ? C’est ça que j’entendais par « quelle stratégie l’emporte sur l’autre ? ».

Si tu fais jouer une stratégie contre elle-même, par symétrie elle va gagner avec la même probabilité qu’elle perd (mais on peut calculer la probabilité de partie nulle…).

Je pense qu’on ne gagne vraiment rien à parler de tribus comme tu fais. Pour formaliser, on peut par exemple dire qu’on a deux variables aléatoires $A$ et $B$ indépendantes qui représentent les scores des deux stratégies, et parler de $ℙ(A>B)$, $ℙ(A=B)$, … (Et les lois de ces variables aléatoires dépendent implicitement de $p$.)

Ça mis à part, ton calcul de $P_1(\text{Bob gagne})$ est correct mais pas celui de $P_2(\text{Bob gagne})$, je pense que tu as oublié de réfléchir au cas « partie nulle ».

+1 -0

La question est : quand on fait jouer la stratégie A contre la B, est-ce qu’il y a plus de chances que ce soit la A ou la B qui gagne ? C’est ça que j’entendais par « quelle stratégie l’emporte sur l’autre ? ».

Ok, ok mb.

Si tu fais jouer une stratégie contre elle-même, par symétrie elle va gagner avec la même probabilité qu’elle perd (mais on peut calculer la probabilité de partie nulle…).

Oui effectivement pour le cas de stratégies fixes c’est le cas ("fixe" dans le sens ou le coup ne dépend pas du coup du joueur).

Je pense qu’on ne gagne vraiment rien à parler de tribus comme tu fais. Pour formaliser, on peut par exemple dire qu’on a deux variables aléatoires $A$ et $B$ indépendantes qui représentent les scores des deux stratégies, et parler de $ℙ(A>B)$, $ℙ(A=B)$, … (Et les lois de ces variables aléatoires dépendent implicitement de $p$.)

En fait je suis complètement d’accord avec toi, et je trouve que ça complique juste le truc pour rien.J’ai fais ça, parce-que je ne sais pas si on enlève complètement la rigueur au truc si on parle pas d’espaces probabilisables. ’Fin je veux dire est ce que je peux parler de probabilités sans parler d’espaces probabilisables ? Pour moi les variables aléatoires ça revient au même (juste ça permet plus de clarté) dans le sens ou on est obligé de parler d’ensemble de départ et d’arrivée qui sont des espaces probabilisables.

Au lycée, je ne faisais pas du tout ça, mais après avoir vu ces notions, dans toutes les corrections d’exos on rappelle souvent sur quel espace sont définies les probas… Donc bêtement je fais pareil de peur de perdre de la rigueur mais je suis d’accord que je ne sais pas du coup ce que ça rajoute, peut-être quand on passe au cas continu on peut avoir des ambiguïtés et il est alors préférable de rappeler ce sur quoi on fais des calculs.

Ça mis à part, ton calcul de $P_1(\text{Bob gagne})$ est correct mais pas celui de $P_2(\text{Bob gagne})$, je pense que tu as oublié de réfléchir au cas « partie nulle ».

blo yhg

Oui en fait j’ai explicitement précisé que je n’avais pas traité le cas partie nulle. Par contre dans ce cas $P_1(\text{Bob gagne})$ répond aussi à la question : gain sans partie nulle.

Bref, en traitant ces cas là on obtient :

$$P(\text{Bob gagne avec la stratégie A sans match nul}) = G_{A, BOB} = p-p^{n+1}$$
$$P(\text{Bob gagne avec la stratégie B sans match nul}) = G_{B, BOB} = 1-P_{A, BOB} = 1-p+p^{n+1}$$
$$P(\text{Bob fait un match nul avec la stratégie A}) = N_{A,BOB} = p \cdot p^n = p^{n+1}$$

On a : $G'_{A, BOB} = 1-(n+1)\cdot p^n $. Or $1-(n+1)p^n \geq 0 \Leftrightarrow p \leq (\frac{1}{n+1})^{1/n}$. Ainsi la probabilité de gain est maximal pour Bob lorsque : $p = (\frac{1}{n+1})^{1/n}$.

Si on regarde à l’inverse la probabilité de gain ou de match nul on a :$N_{A,BOB} + G_{A, BOB} = p$. Donc dans ce cas, c’est clair que Bob doit jouer si et seulement si $p > 1/2$, puisque $p$ donne directement sa probabilité de gain (ou de match nul).

+0 -0
Banni

Pour la partie modélisation, il est sûrement possible de faire plus formel (ce qui peut être intéressant mais pas si c’est juste pour faire un truc plus formel). Pour ce que je demandais, c’est suffisamment rigoureux de dire $ℙ(A>B) = ℙ(A=n \text{ et } B<n) = ℙ(A=n) × ℙ(B≠n) = \text{etc.}$

J’ai pas compris dans ton résultat ce qu’est $1-p+p^{n+1}$. Tu ne veux pas exprimer ton truc avec les variables que j’ai appelées $A$ et $B$ ? Pour moi ton évènement « Bob gagne avec la stratégie $B$ sans match nul » se traduit par « $B>A$ » mais tu calcules $ℙ(B≥A) = 1-ℙ(A>B)$. Et la probabilité que $A=B$ (ta troisième équation) n’est pas $p × p^n$.

+0 -0

Pour la partie modélisation, il est sûrement possible de faire plus formel (ce qui peut être intéressant mais pas si c’est juste pour faire un truc plus formel). Pour ce que je demandais, c’est suffisamment rigoureux de dire $ℙ(A>B) = ℙ(A=n \text{ et } B<n) = ℙ(A=n) × ℙ(B≠n) = \text{etc.}$

Pour moi on doit avoir un espace probabilisable pour parler de probabilités. En utilisant tes notations néanmoins on a :

$$P(A > B) = p-p^{n+1}$$ $$P(A = B) = p^{n+1}+(1-p)^{n+1}$$ $$P(A \geq B) = P(A > B) + P(A = B) = p-p^{n+1}+p^{n+1}+(1-p)^{n+1} = p-(1-p)^{n+1} = 1-q-q^{n+1}$$

avec $q = 1-p$.

+0 -0
Banni

Pour moi on doit avoir un espace probabilisable pour parler de probabilités.

Oui mais souvent il est implicite, on ne le définit pas très précisément car il y a une infinité de manières de faire et que ce n’est pas ça qui est important. Ce qui est important est quelles sont les lois des variables aléatoires considérées, et quelles sont leurs lois jointes (sont-elles indépendantes ? etc.). Dans notre cas on a deux lois sur $ℝ$ : la loi de $A$ et la loi de $B$, que je vais noter $L(A)$ et $L(B)$. Ça donne la loi $L(A) ⊗ L(B)$ sur $ℝ×ℝ$ (produit indépendant de lois). Si on veut, on peut appeler $A$ et $B$ les deux projections $ℝ×ℝ→ℝ$.

Sinon peut-être que tu as résolu le problème mais tu n’as pas écrit ça assez explicitement pour que je comprenne. On a $ℙ(A<B) = q(1-q^n)$, avec $q=1-p$, comme tu as dit. Et la question est donc de comparer $p(1-p^n)$ et $q(1-q^n)$. Je ne sais pas comment le voir de manière évidente.

+1 -0

Notons $f_n$ la fonction définie par :

$$ f_n: [0,1] \to [0,1] : p \mapsto p-p^{n+1}, \forall n> 2$$

Sur $[0,\frac{1}{2}]$ on a :

$$(1-p)^{n+1} \geq p^{n+1} \text { et } 2p \leq 1 \Rightarrow f_n(p) \leq f_n \circ (1-p) $$

Ensuite pour passer de la courbe représentative de $f_n$ à celle de $f_n \circ (1-p)$ il suffit d’effectuer une symétrie par rapport à l’axe des ordonnés puis une translation de $1$ "vers la droite". Puisqu’on est sur $[0,1]$, cela correspond donc à faire une symétrie par rapport à la droite $y = \frac{1}{2}$.

Ainsi par symétrie on en déduit :

$$ \forall x \in \left[ \frac{1}{2}, 1 \right ], f_n(p) \geq f_n \circ (1-p) $$

Ainsi Bob doit effectuer la stratégie $A$ lorsque $p \geq \frac{1}{2}$.

Lorsque $n \leq 2$, les deux quantités sont égales, la stratégie importe alors peu.

+0 -0

Yep, excuse je voulais dire $n+1 \leq 2$, soit $n\leq 1$.

La suite provient du fait que :

$$a^n-1 = (a-1)(a^{n-1}+...+1)$$

En faisant ça de chaque côté de l’inégalité sur $1-(1-x)^n$ et $1-x^n$, ça revient à prouver l’inégalité :

$$(1-p)^n \geq p^n$$

Qui est vraie sur $[0,0.5]$.

Si c’est pas clair je peux developer le truc si tu veux.

+0 -0
Banni

Ah d’accord, maintenant je valide. Mais c’était quand même selon moi l’argument principal (l’inégalité se réécrit $pq(1+p+⋯+p^n) ≥ pq(1+q+⋯+q^n)$), non ?

Remarque : on peut aussi voir le truc avec la convexité de $p ↦ p^n$. L’inégalité se réécrit $\frac{1-p^n}{1-p} ≥ \frac{1-q^n}{1-q}$ et la fonction $p ↦ \frac{1-p^n}{1-p}$ est croissante sur $[0,1]$ par convexité de $p↦p^n$ sur cet intervalle.

+1 -0

Ah d’accord, maintenant je valide. Mais c’était quand même selon moi l’argument principal (l’inégalité se réécrit $pq(1+p+⋯+p^n) ≥ pq(1+q+⋯+q^n)$), non ?

Oui je suis d’accord que ce que j’ai dis n’étais pas très explicite :)

Remarque : on peut aussi voir le truc avec la convexité de $p ↦ p^n$. L’inégalité se réécrit $\frac{1-p^n}{1-p} ≥ \frac{1-q^n}{1-q}$ et la fonction $p ↦ \frac{1-p^n}{1-p}$ est croissante sur $[0,1]$ par convexité de $p↦p^n$ sur cet intervalle.

blo yhg

Yep, j’y ai aussi pensé. On pouvait faire un truc encore plus hard, en disant que si pour un $z$ dans $[0, 0.5]$, on a $f_n(z)> f_n\circ(1-z)$, alors il existe un intervalle $[a,b]$, sur lequel $f_n(x) > f_n \circ (1-x)$, et ensuite il faut montrer que sur tout compact on a : $\int_{x_1}^{x_2} f_n(x)-f_n \circ (1-x) \mathrm{d}x < 0$ qui est une contradiction. (Bon par contre c’est possible qu’il y est beaucoup de calculs rendant la preuve pas ouf, ouf).

+0 -0

Un paysan possède $2n + 1$ vaches. Lorsqu’il isole n’importe laquelle d’entre elles, il peut séparer l’ensemble des $2n$ autres en deux groupes de $n$ vaches dont la somme des masses est égale. Montrer que toutes les vaches ont la même masse. Les masses sont supposées réelles quelconques.

+0 -0
Banni

T’es sûr que ça fonctionne ta deuxième idée ? On ne se retrouve pas avec quelque chose d’au moins aussi dur qu’au départ ?

On peut aussi montrer que la stratégie « tout miser » est optimale si $p(1-p^2) ≥ q(1-q^n)$ (ce qui est vrai quel que soit $n$ si $p≥\frac{\sqrt{5}-1}{2}$ en majorant $q(1-q^n)$ par $q$). En effet, une stratégie est meilleure que la stratégie « tout miser » si, en notant $u$ et $v$ les probabilités respectives de gagner $n$ points et $0$, on a $p(1-u) < q(1-v)$. Il faut donc maximiser $u$ et minimiser $v$, et c’est faisable de manière jointe en prenant une stratégie qui commence par miser un seul pion. Si on remporte cette première mise, on mise tout ce qu’il reste. Ça donne $u = p^2$. Si on perd la mise, on mise les pions un par un, ça donne $v=q^n$.

Pour ton autre énigme, je la connais déjà. :(

+0 -0

T’es sûr que ça fonctionne ta deuxième idée ? On ne se retrouve pas avec quelque chose d’au moins aussi dur qu’au départ ?

Ouai, je sais pas trop. Mais effectivement c’est possible que comme on réintègre des polynömes on se retrouve avec des trucs de la même forme. J’ai un peu la flemme de tester là. :)

On peut aussi montrer que la stratégie « tout miser » est optimale si $p(1-p^2) ≥ q(1-q^n)$ (ce qui est vrai quel que soit $n$ si $p≥\frac{\sqrt{5}-1}{2}$ en majorant $q(1-q^n)$ par $q$). En effet, une stratégie est meilleure que la stratégie « tout miser » si, en notant $u$ et $v$ les probabilités respectives de gagner $n$ points et $0$, on a $p(1-u) < q(1-v)$. Il faut donc maximiser $u$ et minimiser $v$, et c’est faisable de manière jointe en prenant une stratégie qui commence par miser un seul pion. Si on remporte cette première mise, on mise tout ce qu’il reste. Ça donne $u = p^2$. Si on perd la mise, on mise les pions un par un, ça donne $v=q^n$.

Oui, ok. En fait c’est assez intuitif (voir message d’elegance). Jolie invention sinon :D

Pour ton autre énigme, je la connais déjà. :(

blo yhg

Oui c’est assez connue, désolé :) Bon je ne l’enlève pas et je laisse les personnes actives chercher.

+0 -0
Banni

On a le droit de s’assister d’un ordinateur ?

J’ai trouvé n=1578270389554680057141787800241971645032008710129107338825798n=1578270389554680057141787800241971645032008710129107338825798 avec sage mathematics. On commence par calculer le résultant des deux polynômes, il s’agit de p:=5299875888670549565548724808121659894902032916925752559262837p:=5299875888670549565548724808121659894902032916925752559262837. Sage me dit que c’est un nombre premier (je ne sais pas quel algorithme est employé…). Donc le seul facteur commun possible est pp. On passe modulo pp et on calcule le gcd des deux polynômes, cela donne leur racine commune, et le résultat que j’ai donné.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte