{ "cells": [ { "cell_type": "markdown", "metadata": { "id": "rzsspKn6HWxu" }, "source": [ "# **
Décision dans l'incertain
**\n", "\n", "\n", "##
Un exemple simple de problème de décision
\n", "$\\newcommand\\indi[1]{{\\mathbf 1}_{\\displaystyle #1}}$\n", "$\\newcommand\\inde[1]{{\\mathbf 1}_{\\displaystyle\\left\\{ #1 \\right\\}}}$\n", "$\\newcommand{\\ind}{\\inde}$\n", "$\\newcommand\\E{{\\mathbf E}}$\n", "$\\newcommand\\Cov{{\\mathrm Cov}}$\n", "$\\newcommand\\Var{{\\mathrm Var}}$\n" ] }, { "cell_type": "markdown", "metadata": { "id": "WzCEFt4WxrUr" }, "source": [ "# 1. La question à résoudre" ] }, { "cell_type": "markdown", "metadata": { "id": "2P3YE_XcxrUr" }, "source": [ " On place deux oeufs \"au hasard\" dans une matrice $p\\times q$. On\n", " considère deux joueurs ($A$ et $B$). Le joueur $A$ parcours la\n", " matrice en colonne, le joueur $B$ en ligne. Le gagnant est celui qui\n", " atteint le premier l'un des deux oeufs. La question est de savoir si\n", " ce jeu est équitable (i.e. les deux joueurs ont ils la même\n", " probabilité de gagner ?) et de déterminer, si ce n'est pas le cas,\n", " lequel a un avantage.\n", "\n", "\n", "
\n", "\n", "On trouvera la réponse à cette question lorsque $p=3$ et $q=4$ sur le\n", "site de la NSA. Nous verrons que l'on peut répondre très simplement\n", "à ces questions à l'aide d'un programme de quelques lignes pour une valeur\n", "arbitraire de $p$ et $q$. \n", "\n", "\n", "Les réponses dépendent des\n", "valeurs de $p$ et $q$ de façon surprenante: elles sont différentes\n", "pour $(p=3,q=4)$, $(p=4,q=4)$ et $(p=4,q=5)$!\n", "\n", "---\n", "\n", "Remarque:\n", "
\n", "Lorsque vous aurez terminé la partie informatique, les parties en bleu pourront\n", "vous servir d'exercices (de révision du cours du premier semestre).\n", "\n", "\n", "---" ] }, { "cell_type": "markdown", "metadata": { "id": "UQnnlFQ6xrUs" }, "source": [ "# 2. Étude de la question posée par une méthode de Monte-Carlo" ] }, { "cell_type": "markdown", "metadata": { "id": "1vv0cMmIxrUs" }, "source": [ "On commence par traiter la question par simulation.\n", "\n", "On suppose (ce qui est implicite dans la formulation du problème) que\n", "les $2$ oeufs sont placés, indépendamment, uniformément sur les\n", "$p\\times q$ cases de la matrice. Il peut donc arriver que les $2$\n", "oeufs soient au même endroit (à vrai dire le problème ne précise pas\n", "ce détail), mais cela n'a pas d'importance pour la\n", "réponse à la question posée.\n", "\n", "On doit tirer une ligne au hasard uniformement entre $1$ et\n", "$p$ et une colonne au hasard entre $1$ et $q$. Pour cela il faut\n", "savoir tirer au hazard une variable aléatoire selon une loi discrête\n", "donnée. C'est l'objet de la question 1.\n", "\n", "Dans la question 2, on tire au hazard les 2 oeufs et on en déduit les\n", "temps d'atteinte par A et B du premier oeuf (notés respectivement $T_A$ et $T_B$).\n", "\n", "Dans la question 3, on répond à la question \"qui gagne le plus souvent?\" en simulant un grand nombre de parties (une méthode de Monte-Carlo)." ] }, { "cell_type": "markdown", "metadata": { "id": "50mnYcLWxrUs" }, "source": [ "### Simulation d'une loi discrète" ] }, { "cell_type": "markdown", "metadata": { "id": "e5azPbMoXSI5" }, "source": [ "**Rappel:**\n", "\n", "Il est possible de simuler une variable aléatoire qui prend les valeurs $(x_i)_{i\\in \\mathbb{N}^*}$ avec probabilités respectives $(p_i)_{i \\in \\mathbb{N}^*}$ (avec les $p_i \\geq 0$ et $\\sum\\limits_{i \\in \\mathbb{N}^*} p_i = 1$) à l'aide d'une seule variable aléatoire $U \\sim \\mathcal{U}([0, 1])$ en posant:\n", "\n", "$$\n", "X = x_1 \\mathbb{1}_{ \\{U \\leq p_1 \\} } + x_2 \\mathbb{1}_{ \\{p_1 \\leq U \\leq p_1 + p_2 \\}} + \\dots + x_i \\mathbb{1}_{ \\{p_1 + \\dots + p_{i-1} \\leq U \\leq p_1 + \\dots + p_i \\}} + \\dots\n", "$$\n" ] }, { "cell_type": "markdown", "metadata": { "id": "yQRy-2TZxrUs" }, "source": [ "On cherche à réaliser un tirage selon la loi d'une variable aléatoire $N$ qui prend ses valeurs \n", "dans $\\{1,\\ldots,n\\}$ dont la loi donnée par le vecteur $(P[k-1],1\\leq k \\leq n)$.\n", "\n", "---\n", "Exercice 1:\n", "
\n", "Lorsque la loi est uniforme sur $\\{1,\\ldots,n\\}$, on peut\n", "vérifier (exercice) que $\\E(N)=\\frac{n+1}{2}$ et $\\Var(N)=\\frac{(n+1)(n-1)}{12}$.\n", "\n", "\n", "---\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "id": "0G3xCWCwxrUt" }, "outputs": [], "source": [ "import random\n", "import numpy as np\n", "import math\n", "\n", "def rand_disc(P):\n", "# P est une loi discrète qui charge les entiers 1,...,p\n", "# le vecteur P[i-1],pour i=1,...,p donne la probabilité d'obtenir i .\n", "# Il est décalé de 1 pour tenir compte de la convention \"Python\"\n", "# de vecteurs qui débutent en 0.\n", "\n", "# Version itérative.\n", " U=np.random.rand(1) # On tire selon une loi uniforme entre 0 et 1\n", " # \"On inverse la fonction de répartition\" : voir cours du premier semestre.\n", "\n", " ###### A vous de jouer .....\n", " " ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "LCFPvgKglo02", "outputId": "5a42c9b5-465d-4b89-d175-d4d4601efaf2" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "moyenne empirique: 6.606 - moyenne attendue 6.5\n", "variance: 11.632764 - variance attendue 11.916666666666666\n" ] } ], "source": [ "n=12\n", "P=np.ones(n)/n\n", "X=np.zeros(1000,dtype=int) # dtype=int pour indiquer que le tableau est constitué d'entiers\n", "for i in range(1000):\n", " X[i]=rand_disc(P)\n", "print(\"moyenne empirique:\",np.mean(X),\" - moyenne attendue \",(n+1)/2) # np.mean calcule moyenne des tirages\n", "print(\"variance:\",np.var(X),\" - variance attendue \",(n+1)*(n-1)/12) # np.var la variance des tirages" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "qJqCddHZxrUu", "outputId": "c10f90b1-981d-44cd-b334-fb57b1600906" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2 2 2 3 3 1 2 3 3 3 " ] } ], "source": [ "def test_0():\n", "# Un exemple de tirages uniformes sur |$\\{1,2,3\\}$|\n", " p=3;\n", " P=np.ones(p)/p;# loi uniforme sur |$\\{1,2,3\\}$|\n", "\n", " N=10;\n", " X=np.zeros(N,dtype=int)\n", " for i in range(N): # N tirages uniformes sur |$\\{1,2,3\\}$|\n", " X[i] = rand_disc(P)\n", " print(X[i], end=' ')\n", " \n", "test_0()" ] }, { "cell_type": "markdown", "metadata": { "id": "hhNP_U55xrUu" }, "source": [ "### Simulation des temps d'atteinte" ] }, { "cell_type": "markdown", "metadata": { "id": "lWuzduO0xrUv" }, "source": [ "On tire le premier oeuf en $(U_1,V_1)$, $U_1$ (l'indice de ligne)\n", "et $V_1$ (l'indice de colonne) étant indépendantes, de loi uniforme\n", "respectivement sur $\\{1,\\ldots,p\\}$ et $\\{1,\\ldots,q\\}$. Si le premier\n", "oeuf se trouve en $(U_1,V_1)$, le temps d'atteinte de cet oeuf\n", "par $A$ (parcours en colonne) est donné par\n", "$$\n", " t_1^A=(V_1-1) p+U_1,\n", "$$\n", "\n", "
\n", "\n", "et, pour $B$ (parcours en ligne), par\n", "$$\n", "t_1^B=(U_1-1) q+V_1,\n", "$$\n", "
\n", "avec des formules identiques pour le deuxième oeuf:\n", "$$\n", "t_2^A=(V_2-1) p+U_2,\\quad t_2^B=(U_2-1) q+V_2,\n", "$$ \n", "$U_2$ et $V_2$ étant indépendantes, toujours de lois uniformes,\n", "indépendantes du couple $(U_1,V_1)$.\n", "\n", "---\n", "Exercice 2:\n", "
\n", " Noter que l'on peut calculer la loi (commune) de $t_1^A$, $t_1^B$,\n", "$t_2^A$, $t_2^B$ (loi uniforme sur $\\{1,\\ldots,p\\times q\\}$) et\n", "montrer que $t_1^A$ s'obtient comme une permutation déterministe $\\sigma$ de\n", "$t_1^B$.\n", "\n", "\n", "---\n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "id": "hotE62_COYIm" }, "source": [ "Avec ces éléments, il est facile d'écrire une fonction qui réalise le tirage\n", "des deux oeufs dans la matrice et d'en déduire les temps que mettent $A$\n", "et $B$ pour trouver le premier oeuf (au sens chronologique).\n", "\n", "En d'autres termes:\n", "\n", "$$\n", "T_A = \\min(t_1^A, t_2^A), \\quad T_B = \\min(t_1^B, t_2^B)\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "id": "PG7O10UcL-zv" }, "source": [ "\n", "---\n", "Exercice 3:\n", "
\n", "Montrer que $T_A$ et $T_B$ ont la même loi et que si $\\sigma^2 = id$ alors les couples $(T_A, T_B)$ et $(T_B, T_A)$ ont la même loi (c'est le cas lorsque $p=q$).\n", "\n", "\n", "---\n" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "id": "MdU7jQw6xrUv" }, "outputs": [], "source": [ "def random_times(p,q):\n", "# On simule selon des lois uniformes sur 1:p et 1:q\n", "# On en déduit les tirages de T_A et T_B\n", "\n", " P=np.ones(p)/p;# Loi uniforme sur 1:p\n", " Q=np.ones(q)/q;# Loi uniforme sur 1:q\n", "\n", " # Calcul de T_A et T_B en fonction de (i_1,j_1) (i_2,j_2)\n", " \n", " \n", " ###### A vous de jouer .....\n", " \n", " \n", " return [T_A,T_B]" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "afsx0dnPxrUv", "outputId": "31cce1cd-98a1-453f-ac13-e1a683810759" }, "outputs": [ { "data": { "text/plain": [ "[1, 1]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random_times(2,3)" ] }, { "cell_type": "markdown", "metadata": { "id": "T6FZSWJMxrUw" }, "source": [ "Il ne reste plus qu'à faire suffisamment de tirages \n", "pour répondre (en partie) à la question posée." ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "_ixIbTkuxrUw", "outputId": "f64046e6-7440-4049-8797-36489170aa4d" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "**********************************************************************\n", "Pour p = 2, q = 3:\n", "pA = 0.279 +- 0.010, pB = 0.330 +- 0.010\n", "Il est très probable que B gagne en moyenne.\n", "**********************************************************************\n", "Pour p = 3, q = 4:\n", "pA = 0.394 +- 0.010, pB = 0.413 +- 0.010\n", "On ne peut pas conclure (il faut augmenter le nombre de tirages)\n", "**********************************************************************\n", "Pour p = 4, q = 5:\n", "pA = 0.438 +- 0.010, pB = 0.440 +- 0.010\n", "On ne peut pas conclure (il faut augmenter le nombre de tirages)\n", "**********************************************************************\n", "Pour p = 4, q = 4:\n", "pA = 0.365 +- 0.010, pB = 0.364 +- 0.010\n", "On ne peut pas conclure (il faut augmenter le nombre de tirages)\n" ] } ], "source": [ "def qui_gagne_MC(p,q,N):\n", " print(\"*\"*70)\n", " print(\"Pour p = {}, q = {}:\".format(p, q))\n", " statA = 0 \n", " statB = 0\n", " # Nombre de fois où chaque joueur gagne\n", " \n", " ###### A vous de jouer .....\n", " for i in range(N):\n", " [T_A,T_B] = random_times(p,q);\n", "\n", " ### Comment estimer par simulation pA=P(A gagne) et pB=P(B gagne) ?\n", " \n", "\n", " erreur=1/math.sqrt(N) # erreur maximum probable\n", " \n", " print(\"pA = {:.3f} +- {:.3f}, pB = {:.3f} +- {:.3f}\".format(pA, erreur, pB, erreur))\n", "\n", " if (pA+erreur < pB-erreur):\n", " print(\"Il est très probable que B gagne en moyenne.\")\n", "\n", " elif (pA-erreur > pB+erreur):\n", " print(\"Il est très probable que A gagne en moyenne.\")\n", "\n", " else:\n", " print(\"On ne peut pas conclure (il faut augmenter le nombre de tirages)\")\n", "\n", "\n", "def test_1():\n", " N=10000;\n", " qui_gagne_MC(2,3,N)\n", " qui_gagne_MC(3,4,N)\n", " qui_gagne_MC(4,5,N)\n", " qui_gagne_MC(4,4,N)\n", "\n", "test_1()" ] }, { "cell_type": "markdown", "metadata": { "id": "F2QNZoixxrUw" }, "source": [ "---\n", "Exercice 4:\n", "
\n", "Noter que le théorème de la limite centrale permet (exercice!) de\n", "montrer que l'erreur \"probable maximale\" est de l'ordre de\n", "$1/\\sqrt{n}$ (C'est le même résultat qui permet d'évaluer\n", "approximativement l'erreur d'un sondage d'opinion).\n", "\n", "\n", "---\n", "\n", "Dans le cas $p=2$, $q=3$ on arrive assez facilement ($N=10000$ suffit\n", "largement) à se convaincre que $B$ gagne en moyenne. C'est plus\n", "difficile pour $(p=3,q=4)$ ($N=100000$ convient). Ça devient délicat\n", "pour $(p=4,q=5)$ (il faut prendre $N\\approx 1000000$ pour conclure que\n", "c'est $A$ qui gagne). Dans les cas où $p=q$ (où l'on peut prouver\n", "qu'il y a égalité des probabilités), une méthode de simulation ne sera\n", "__jamais__ concluante.\n", " \n", "Il nous faut une méthode exacte de calcul de ces probabilités. C'est\n", "ce que nous allons faire maintenant." ] }, { "cell_type": "markdown", "metadata": { "id": "8hFnW8eOxrUx" }, "source": [ "# 3. Un calcul exact par énumération exhaustive" ] }, { "cell_type": "markdown", "metadata": { "id": "hRxmTJ3ZxrUx" }, "source": [ "L'espace de probabilité $\\Omega$ étant fini, il suffit d'énumérer\n", "$\\Omega$ pour calculer la probabilité: on génère toutes les valeurs\n", "possibles pour les positions des oeufs $(i_1,j_1)$ et $(i_2,j_2)$\n", "(tous ces couples (de couples!) sont supposés équiprobables), on calcule $T_A$\n", "et $T_B$ et l'on fait des stats sur celui qui gagne.\n", "\n", "\n", "
\n", "On en profite pour calculer la loi du couple $(T_A,T_B)$ et pour vérifier que les\n", "lois de $T_A$ et $T_B$ sont identiques (exercice, pour une correction voir la \n", "version `scilab` du sujet).\n", "\n", "On vérifie aussi que la loi de $(T_A,T_B)$ n'est pas identique à celle de $(T_B,T_A)$ (sauf si $p=q$).\n", "On peut aussi montrer (exercice) que $T_A$ n'est jamais indépendante de $T_B$.\n", "" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "cDK7dR3hxrUx", "outputId": "72af43c8-e9dc-4412-9627-308502a78e53" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "p = 40 , q = 45 : c'est A qui gagne\n", "H_AB est bien de somme 1\n", "Les lois de T_A et T_B sont bien égales.\n", "La loi du couple (T_A,T_B) n'est pas symétrique (c'est normal si p!=q) !\n", "\n" ] } ], "source": [ "def qui_gagne_elem(p,q):\n", "# On énumère toutes les positions possibles\n", "# et on en déduit lequel des joueurs gagne en moyenne\n", "\n", " Ascore=0;Bscore=0;nbre_cas_egalite=0\n", " \n", " # On génère toutes les positions pour les 2 oeufs\n", " # Attention en Python: range(1,p+1) = {1,2, ...,p}, c'est bien ce que l'on veut\n", " \n", " ###### A vous de jouer .....\n", " \n", " if T_A > T_B :\n", " Bscore=Bscore+1\n", " elif T_A < T_B:\n", " Ascore=Ascore+1\n", " else: # T_A == T_B\n", " nbre_cas_egalite=nbre_cas_egalite+1\n", "\n", " print('p = ',p,', q = ',q, ': ',end='') # end='' pour eviter le passage à la ligne\n", " if (Bscore>Ascore): \n", " print(\"c'est B qui gagne\")\n", " elif (Ascore>Bscore): \n", " print(\"c'est A qui gagne\")\n", " else: \n", " print(\"cas d'égalité\")\n", "\n", "def histo(p,q):\n", "# Calcule la loi du couple (T_A,T_B) par énumération exhaustive des cas\n", "\n", " nbre=p*q;# valeur maximale de T_A ou T_B\n", " \n", " # Les tableaux Python sont indicés à partir de 0 -> on rajoute 1\n", " H_AB=np.zeros([nbre+1,nbre+1]);\n", " \n", " # On génère toutes les positions pour les 2 oeufs \n", " \n", " ###### A vous de jouer .....\n", " \n", " \n", " # met à jour le nbre de tirages valant (k,l)\n", " H_AB[T_A,T_B] = H_AB[T_A,T_B] + 1\n", " H_AB = H_AB/(nbre*nbre) \n", " return H_AB\n", "\n", "p=40;q=45\n", "qui_gagne_elem(p,q)\n", "\n", "# On calcule la loi du couple (T_A,T_B)\n", "H_AB=histo(p,q)\n", "\n", "# On vérifie que H_AB est bien la loi d'un couple\n", "if np.abs(np.sum(H_AB)-1) <= 1.e-7 :\n", " print('H_AB est bien de somme 1')\n", "\n", "# Verification que les lois marginales sont identiques.\n", "\n", "###### A vous de jouer .....\n", "\n", "# Vous pourrez utiliser np.linalg.norm(matrice)\n", "# qui calcule la norme quadratique d'une matrice.\n", "\n", "# np.sum(matrice,axis=0) fait la somme des lignes d'une matrice\n", "# np.sum(matrice,axis=1) fait la somme des colonnes d'une matrice\n", "\n", "#H_A=...\n", "#H_B=...\n", "\n", "# H_A = la loi de T_A est forcément égal à H_B = la loi de T_B : on va vérifier\n", "\n", " ###### A vous de jouer .....\n", "\n", " #if ... : # H_A ?=? H_B à epsilon près ...\n", " # print(\"Warning: les lois de T_A et T_B doivent être égales.\\n\")\n", " #else:\n", " # print('Les lois de T_A et T_B sont bien égales.');\n", "\n", "# Par contre (T_A,T_B) n'a pas la même loi que (T_B,T_A) lorsque p != q.\n", "# La loi n'est pas symétrique (en particulier T_A et T_B ne peuvent être indépendantes)\n", "\n", "# On va vérifier ce point.\n", "\n", " ###### A vous de jouer .....\n", "\n", " # La loi (T_B,T_A) est donnée par la transposée de la loi de (T_A,T_B)\n", " # Il faut donc comparer la matrice H_AB et sa transposée.\n", " # En python pour transposer une matrice : np.transpose(matrice)\n", "\n", " # if np.linalg.norm(...) >= 1.e-7 :\n", " print(\"La loi du couple (T_A,T_B) n'est pas symétrique (c'est normal si p!=q) !\\n\")\n", "else:\n", " print('La loi du couple (T_A,T_B) est symétrique: p et q sont probablement égaux.');\n", "\n", "if p*q <=10:\n", " print(H_AB[1:p*q+1,1:p*q+1])" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "xh7p1YYmxrUz", "outputId": "69b82858-4d0c-4d9f-8ddf-db8e3b7437d1" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "p = 3 , q = 4 : c'est B qui gagne\n", "p = 4 , q = 4 : cas d'égalité\n", "p = 4 , q = 5 : c'est A qui gagne\n" ] } ], "source": [ "def test_2():\n", " qui_gagne_elem(3,4);\n", " qui_gagne_elem(4,4);\n", " qui_gagne_elem(4,5);\n", " \n", " #for p in range(2,5): qui_gagne_elem(p,p+1)\n", " #for p in range(2,9): qui_gagne_elem(p,p+2)\n", " #for p in range(2,7): qui_gagne_elem(p,p+3)\n", "\n", "test_2()" ] }, { "cell_type": "markdown", "metadata": { "id": "QUy2ZA5pxrU0" }, "source": [ "On retrouve le résultat, un peu surprennant, annoncé au début." ] }, { "cell_type": "markdown", "metadata": { "id": "MtpusKb0Nsvp" }, "source": [ "# Références\n", "\n", "[Cours probabilités et statistique pour l'ingénieur - Benjamin Jourdain](http://cermics.enpc.fr/~jourdain/probastat/poly.pdf)" ] }, { "cell_type": "markdown", "metadata": { "id": "N6-F580m4DkM" }, "source": [ "## Corrigés des exercices" ] }, { "cell_type": "markdown", "metadata": { "id": "rfOrIFgS4MOk" }, "source": [ "---\n", "Exercice 1:\n", "\n", "
\n", "Lorsque la loi est uniforme sur $\\{1,\\ldots,n\\}$, on peut\n", "vérifier (exercice) que $\\E(N)=\\frac{n+1}{2}$ et $\\Var(N)=\\frac{(n+1)(n-1)}{12}$.\n", " \n", "\n", "---\n", "\n", "**Solution:**\n", "\n", "\n", "Soit $N \\sim \\mathcal{U}(\\{1, \\dots, n\\})$ \n", "\n", "On a:\n", "$$ \n", "\\begin{align}\n", " \\mathbb{E}[N] &= \\sum\\limits_{k=1}^{n} k \\underbrace{\\mathbb{P}(N = k)}_{=\\frac{1}{n}} \\\\\n", " &= \\frac{1}{n} \\sum\\limits_{k=1}^{n} k \\\\\n", " &= \\frac{1}{n} \\frac{n(n+1)}{2} \\\\\n", " &= \\frac{n+1}{2}\n", "\\end{align}\n", "$$\n", " \n", "$$\n", "\\begin{align}\n", " \\mathbb{E}[N^2] &= \\sum\\limits_{k=1}^{n} k^2 \\underbrace{\\mathbb{P}(N = k)}_{=\\frac{1}{n}} \\\\\n", " &= \\frac{1}{n} \\sum\\limits_{k=1}^{n} k^2 \\\\\n", " &= \\frac{1}{n} \\frac{n(n+1)(2n+1)}{6} \\\\\n", " &= \\frac{(n+1)(2n+1)}{6}\n", "\\end{align}\n", "$$\n", "\n", "On en déduit que:\n", "$$\n", "\\begin{align}\n", " \\mathbb{V}\\text{ar}[N] &= \\mathbb{E}[N^2] - \\mathbb{E}[N]^2 \\\\\n", " &= \\frac{(n+1)(2n+1)}{6} - \\left( \\frac{n+1}{2} \\right)^2 \\\\\n", " &= \\frac{(n+1)(n-1)}{12}\n", "\\end{align}\n", "$$\n", "\n", "---" ] }, { "cell_type": "markdown", "metadata": { "id": "1KQ9PyNZ4OQc" }, "source": [ "---\n", "Exercice 2:\n", "\n", "
\n", " Noter que l'on peut calculer la loi (commune) de $t_1^A$, $t_1^B$,\n", "$t_2^A$, $t_2^B$ (loi uniforme sur $\\{1,\\ldots,p\\times q\\}$) et\n", "montrer que $t_1^A$ s'obtient comme une permutation déterministe $\\sigma$ de\n", "$t_1^B$.\n", " \n", "\n", "---\n", "**Solution:**\n", "\n", "Les temps aléatoires $t_1^A$ et $t_1^B$ suivent tous les deux une\n", "loi uniforme sur $\\{1,\\ldots,p\\times q\\}$. \n", "\n", "En effet, si $k$ est un nombre entier compris entre $0$ et $p\\times q-1$, il s'écrit de façon unique sous la forme $k=i_1\\times p + j_1$ avec $i_1\\in\\{0,1,\\ldots,q-1\\}$ et $j_1\\in\\{0,1,\\ldots,p-1\\}$. \n", "\n", "On a donc:\n", "\n", "$$\n", "\\mathbb{P}(t_1^A=k+1) = \\mathbb{P}(V_1=i_1+1,U_1=j_1+1) = \\mathbb{P}(V_1=i_1+1)\\mathbb{P}(U_1=j_1+1) = 1/(p\\times q).\n", "$$ \n", "\n", "Ces temps ne sont pas indépendants. En fait, $t_1^B$ s'obtient par une\n", "permutation déterministe à partir de $t_1^A$: il existe une permutation\n", "$\\sigma$ de $\\{1,\\ldots,p\\;q\\}$ telle que $t_1^B=\\sigma(t_1^A).$ \n", "\n", "Il est facile de s'en convaincre, puisque à chaque case $(i,j)$\n", "correspond un temps d'atteinte différent pour chacun des joueurs:\n", "pour construite la permutation, il suffit donc de mettre en relation\n", "le temps mis par $A$ pour atteindre $(i,j)$ avec le temps mis par\n", "$B$ pour atteindre la même case. \n", "\n", "On peut aussi voir que, lorsque l'on considère le jeu avec un seul\n", "oeuf, on a toujours un problème équitable (i.e. on a $\\mathbb{P}(t_1^A < t_1^B) =\\mathbb{P}(t_1^B < t_1^A)$). \n", "\n", "Pour s'en convaincre, on écrit:\n", "\n", "$$\n", "\\mathbb{P}(t_1^A V'_1 (q-1) )\\\\\n", " &= \\mathbb{P}(t_1^B\n", "
\n", "Montrer que $T_A$ et $T_B$ ont la même loi et que si $\\sigma^2 = id$ alors les couples $(T_A, T_B)$ et $(T_B, T_A)$ ont la même loi.\n", " \n", "\n", "---\n", "**Solution:**\n", "\n", "Pour montrer que $T_A$ et $T_B$ suivent la même loi, on commence par remarquer\n", "qu'il existe une permutation $\\sigma$ de $\\{1,\\ldots,p\\times q\\}$ telle que\n", "$t^1_B=\\sigma(t^1_A)$ et $t^2_B=\\sigma(t^2_A)$ (elle est calculée\n", "plus tard, mais c'est facile de s'en convaincre). \n", "\n", "Comme $t^1_A$ et $t^2_A$ suivent des lois uniformes sur $\\{1,\\ldots,p \\times q\\}$, c'est aussi le cas de $t^1_B$ et $t^2_B$ (exercice). \n", "\n", "$t^1_B$ et $t^2_B$ sont indépendantes, puisque fonctions de variables aléatoires\n", "indépendantes. \n", "\n", "Les couples $(t^1_A,t^2_A)$ et $(t^1_B,t^2_B)$ suivent donc la même loi et l'on conclut que $T_A$ et $T_B$ ont même loi puisque:\n", "\n", "$$\n", "T_A=\\min(t^1_A,t^2_A),\\quad T_B=\\min(t^1_B,t^2_B).\n", "$$\n", "\n", "Il convient de noter que les temps aléatoires $T_A$ et $T_B$ ne sont pas indépendants. C'est d'ailleurs ce qui fait l'intérêt de\n", "la question posée (Que se passerait-il si $T_A$ et $T_B$ étaient\n", "indépendants?).\n", "\n", "\n", "On peut montrer que si $\\sigma^2=Id$, alors la loi du couple $(T_A,T_B)$ est identique à celle du couple $(T_B,T_A)$. En effet on a:\n", "\n", "$$\n", "T_A=\\min(t^1_A,t^2_A),\\quad T_B=\\min(\\sigma(t^1_A),\\sigma(t^2_A))\n", "$$\n", "\n", "Donc, en utilisant le fait que la loi de $(t^1_A,t^2_A)$ est identique à celle de $(\\sigma(t^1_A),\\sigma(t^2_A))$, on obtient:\n", "\n", "$$\n", "\\begin{align*}\n", " \\mathbb{P}\\left(T_A=k,T_B=l\\right) & = \\mathbb{P}\\left(\\min(t^1_A,t^2_A)=k,\\min(\\sigma(t^1_A),\\sigma(t^2_A))=l\\right)\\\\\n", "& = \\mathbb{P} \\left(\\min(\\sigma(t^1_A),\\sigma(t^2_A))=k, \\min(\\sigma^2(t^1_A),\\sigma^2(t^2_A))=l\\right).\n", "\\end{align*}\n", "$$\n", "\n", "Et lorsque $\\sigma^2=Id$, on en déduit $\\mathbb{P} \\left(T_A=k,T_B=l\\right) = \\mathbb{P}(T_B=k,T_A=l)$.\n", "\n", "\n", "Ceci permet d'en déduire (exercice simple mais instructif) que\n", "$$\n", "\\mathbb{P}(T_A