[Maths] Marathon de problèmes

On va commencer par reformuler le problème (la partie chiante à rédiger). Déjà, on peut supposer que $0$ n’est pas dans $P$. À un tel ensemble $P ⊆ ℂ^*$ non vide, on associe

$m(P) := \max_{S ⊆ P \text{ non vide}} \frac{\left|∑_{x ∈ S} x\right|}{∑_{x ∈ P} |x|} \text{.}$

Soit $𝕌 ⊆ ℂ$ le cercle unité. On voit qu’en fait,

$m(P) = \frac{1}{∑_{x ∈ P} |x|} \max_{v \in 𝕌} \left[∑_{x ∈ P} \max(0,\langle x,v \rangle)\right] \text{.}$

En effet, soit $S ⊆ P$ maximisant la somme voulue et soit $v := \frac{∑_{x ∈ S} x}{\left|∑_{x ∈ S} x\right|}$. Alors $∑_{x ∈ P} \max(0,\langle x,v \rangle) ≥ ∑_{x ∈ S} \left|x\right|$. Et pour l’autre sens, on prend $S' := \{x ∈ P \,|\, \langle x,v \rangle > 0\}$.

On peut remplacer $P$ par $\left\{ x/\left[∑_{x ∈ P} |x|\right] \,|\, x ∈ P\right\}$, de sorte que l’on peut supposer que $∑_{x ∈ P} |x| = 1$. On associe à $P$ la loi de probabilité $L_P$ sur $𝕌$ définie comme la somme des $|x| \delta_{x/|x|}$ pour $x ∈ P$. Soit $X$ une variable aléatoire suivant $L_P$. Alors $m(L_P) := m(P) = \sup_{v ∈ 𝕌} 𝔼[\max(0,\langle v,X \rangle)]$.

La quantité recherchée est $\inf_{P ⊆ ℂ^* \text{ non vide}} m(P)$. Je n’ai pas de source mais les mesures de probabilité de la forme $L_P$ sont denses dans l’ensemble des mesures de probabilités sur $𝕌$ selon la convergence faible, ce qui ramène le problème à chercher l’infimum sur toutes les lois de probabilité sur le cercle.

Soit $U$ la loi uniforme sur le cercle. Alors $m(U) = \frac{1}{2\pi} ∫_{-\pi/2}^{\pi/2} \cos(x) \mathrm{d}x = \frac{1}{\pi}$ (on peut approcher $U$ par des lois de la forme $L_P$ en prenant des points uniformément répartis sur le cercle). Il faut ensuite montrer que $m(L) ≥ 1/\pi$ pour toute loi de probabilité $L$ sur le cercle. Pour cela, on emploie la « méthode probabiliste » (c’est la partie intéressante) : on tire $v$ selon $U$ et $X$ selon $L$ et on obtient (on se sert implicitement de Fubini ici) $𝔼[\max(0,\langle v,X \rangle)] = ∫_X ∫_v \max(0,\langle v,X \rangle) = ∫_X 1/\pi = 1/\pi \text{.}$ On en déduit qu’il existe au moins un $v ∈ 𝕌$ tel que $𝔼[\max(0,\langle v,X \rangle)] ≥ 1/\pi$.

On prend donc $C=1/\pi$.

Nécessairement, la probabilité que $A_b=1$Ab​=1 est de $1/2$1/2. En utilisant que $P(A_b=1\text{ et }{B}_a=1)=P(A_b=1)P(B_a=1\mid A_b=1)=\frac{1}{2}P(B_a=1\mid A_b=1)$P(Ab​=1 et Ba​=1)=P(Ab​=1)P(Ba​=1∣Ab​=1)=21​P(Ba​=1∣Ab​=1), la question revient à maximiser $P(B_a=1\mid A_b=1)$P(Ba​=1∣Ab​=1).

Je ne sais pas pourquoi mais la première stratégie que j’ai testée est : le mathématicien A choisit la position du deuxième 1 de sa suite et le mathématicien B choisit la position du premier 1 de sa suite. On trouve une probabilité de gagner de $5/18=\mathrm{0.2777...}$5/18=0.2777... C’est déjà mieux que 1/4, mais ce n’est pas 1/3. Puis ensuite j’ai essayé : les deux mathématiciens choisissent les positions du deuxième 1, ça donne $8/27=0.\overline{2962}$8/27=0.2962.

Mais en fait si on fait choisir aux deux mathématiciens les positions du premier 1 de leur suite, on trouve 1/3. Il faut calculer la probabilité que les deux suites aient leurs premiers 1 qui coïncide. Les lois de ces premiers $1$1 sont $(1/2,1/4,1/8,\dots )$(1/2,1/4,1/8,…), donc la probabilité qu’ils soient égaux est ${\sum }_{n=1}^{\infty }1/2^n\times 1/2^n=\frac{1/4}{1-1/4}=1/3$∑n=1∞​1/2n×1/2n=1−1/41/4​=1/3.

Si on fixe la stratégie de A, alors on peut trouver la stratégie optimale pour B comme suit : choisir $b$b de sorte à maximiser la probabilité que $B_a=1$Ba​=1 sachant que $A_b=1$Ab​=1. (Ce $b$b n’est pas forcément bien défini, c’est informel.) Ça définit une fonction associant à une stratégie $S_1$S1​ une stratégie $S_2$S2​, de sorte que si $A$A adopte $S_1$S1​, alors la stratégie optimale pour $B$B est $S_2$S2​. Alors la stratégie de donner la position du premier 1 de la suite est un point fixe de cette fonction… (Si $A$A adopte cette stratégie, alors la meilleure chose pour $B$B est de faire pareil.)

Pour la 2), tu peux t’intéresser aux nombres $a^{\prime }$a′ et $b^{\prime }$b′ que $A$A et $B$B auraient choisi s’ils avaient observé les suites complémentaires à celles qu’ils avaient obtenues en premier lieu (i.e. en transformant les $1$1 en $0$0 et réciproquement) et écrire la probabilité qu’on cherche à borner sous forme d’espérance.