Exercice 1 : Probabilités et suites : transmission d'une donnée binaire et simulation en Python
5 points Arbres pondérés et probabilités totalesSuites et récurrencePython et méthodes numériques
Dans tout l'exercice, les probabilités seront, si nécessaire, arrondies à près.
Une donnée binaire est une donnée qui ne peut prendre que deux valeurs : 0 ou 1.
Une donnée de ce type est transmise successivement d'une machine à une autre.
Chaque machine transmet la donnée reçue soit de manière fidèle, c'est-à-dire en transmettant l'information telle qu'elle l'a reçue (1 devient 1 et 0 devient 0), soit de façon contraire (1 devient 0 et 0 devient 1).
La transmission est fidèle dans des cas, et donc contraire dans des cas.
Dans tout l'exercice, la première machine reçoit toujours la valeur 1.
- Partie A
- Pour tout entier naturel , on note :
• l'évènement : « la -ième machine détient la valeur 1 » ;
• l'évènement : « la -ième machine détient la valeur 0 ».
- 1.a. Recopier et compléter l'arbre de probabilité ci-dessous.
- 1.b. Démontrer que et interpréter ce résultat dans le contexte de l'exercice.
- 1.c. Sachant que la troisième machine a reçu la valeur 1, calculer la probabilité que la deuxième machine ait aussi reçu la valeur 1.
- 2. Pour tout entier naturel , on note .
- La première machine a reçu la valeur 1, on a donc .
- 2.a. Démontrer que pour tout entier naturel : .
- 2.b. Démontrer par récurrence que pour tout entier naturel , .
- 2.c. Calculer la limite de lorsque tend vers l'infini. Interpréter ce résultat dans le contexte de l'exercice.
- Partie B
- Pour modéliser en langage Python la transmission de la donnée binaire décrite en début d'exercice, on considère la fonction simulation qui prend en paramètre un entier naturel qui représente le nombre de transmissions réalisées d'une machine à une autre, et qui renvoie la liste des valeurs successives de la donnée binaire.
- On donne ci-dessous le script incomplet de cette fonction.
- On rappelle que l'instruction rand() renvoie un nombre aléatoire de l'intervalle .
- Par exemple, simulation(3) peut renvoyer [1, 0, 0, 1]. Cette liste traduit :
• qu'une donnée binaire a été successivement transmise trois fois entre quatre machines ;
• la première machine qui détient la valeur 1 a transmis de façon contraire cette donnée à la deuxième machine ;
• la deuxième machine a transmis la donnée qu'elle détient de façon fidèle à la troisième ;
• la troisième machine a transmis de façon contraire la donnée qu'elle détient à la quatrième. - B.1. Déterminer le rôle des instructions des lignes 5 et 6 de l'algorithme ci-dessus.
- B.2. Calculer la probabilité que simulation(4) renvoie la liste [1, 1, 1, 1, 1] et la probabilité que simulation(6) renvoie la liste [1, 0, 1, 0, 0, 1, 1].
Voir la correction
Réponses
- 1.a , ; , ; ,
- 1.b : la troisième machine détient la valeur 1 dans des cas
- 1.c
- 2.a Probabilités totales avec la partition :
- 2.b Initialisation , hérédité par : pour tout
- 2.c : après un grand nombre de transmissions, la valeur 1 n'est plus détenue qu'une fois sur deux, l'information initiale est perdue
- B.1 Avec une probabilité de , la donnée est remplacée par son contraire (transmission contraire) ; sinon elle est recopiée telle quelle (transmission fidèle)
- B.2 ; , soit arrondi à
A.1.a. Méthode : sur chaque branche issue d'un nœud, on porte la probabilité conditionnelle de l'évènement d'arrivée sachant l'évènement de départ, et les branches issues d'un même nœud ont des probabilités de somme .
Premier niveau : la première machine détient la valeur 1. Elle la transmet fidèlement avec la probabilité , donc et .
Second niveau, depuis : la deuxième machine détient 1 ; la troisième reçoit 1 si la transmission est fidèle, donc et .
Second niveau, depuis : la deuxième machine détient 0 ; la troisième reçoit 1 seulement si la transmission est CONTRAIRE, donc et . L'arbre complété figure en fin de corrigé.
Erreur fréquente : recopier vers sur les deux sous-arbres. La probabilité est celle d'une transmission fidèle, pas celle d'obtenir la valeur 1 : depuis , la transmission fidèle mène à .
A.1.b. Méthode : formule des probabilités totales, avec la partition de l'univers. On additionne les probabilités des deux chemins qui mènent à :
.
Interprétation : la troisième machine détient la valeur 1, la bonne valeur, avec une probabilité de ; autrement dit, après deux transmissions successives, la donnée initiale est intacte dans des cas. Elle l'était dans des cas après une seule transmission : chaque transmission dégrade la fiabilité.
Vérification : la donnée arrive juste après deux transmissions si les deux sont fidèles () ou si les deux sont contraires, deux inversions se compensant (). Le second chemin est celui qu'on oublie.
A.1.c. Méthode : on cherche une probabilité conditionnelle « à rebours », , l'arbre donnant les conditionnements dans l'autre sens. Par définition :
.
Sachant que la troisième machine a reçu la valeur 1, la probabilité que la deuxième l'ait aussi reçue est d'environ . Cohérence : elle dépasse , car savoir que la donnée est juste à l'arrivée rend plus probable qu'elle l'ait été en chemin.
Piège : répondre , qui est , la probabilité de l'arrivée sachant l'étape intermédiaire, et non l'inverse demandé.
A.2.a. Méthode : formule des probabilités totales au rang , avec la partition , en transposant le raisonnement de la question 1.b à deux machines consécutives quelconques.
Soit . La machine détient 1 si la machine détient 1 et transmet fidèlement, ou si la machine détient 0 et transmet de façon contraire. Donc et , et :
.
Vérification : avec , on retrouve et , la valeur de la question 1.b. Piège : écrire au lieu de ; n'est la probabilité de détenir 0 qu'à la deuxième machine.
Pour être rigoureux, il faut et pour parler des probabilités conditionnelles ; au rang , et l'égalité se lit simplement , qui vaut bien .
A.2.b. On démontre par récurrence la propriété : « », pour tout entier .
Initialisation : pour , . est vraie.
Hérédité : soit un entier tel que est vraie, c'est-à-dire . Montrons . Par la question 2.a, . est vraie.
Conclusion : la propriété est vraie au rang et héréditaire ; par le principe de récurrence, pour tout entier .
Vérification : donne . Pièges : initialiser au rang , alors que n'existe pas (la suite commence à ) ; et écrire l'exposant final sous la forme sans faire voir qu'il s'agit de , ce qui est précisément ce qu'il fallait obtenir.
A.2.c. Méthode : limite d'une suite géométrique. Comme , , donc par produit et somme, .
Interprétation : après un très grand nombre de transmissions, la machine détient la valeur 1 avec une probabilité proche de , autant que la valeur 0. La donnée reçue ne renseigne alors presque plus sur la donnée de départ : l'information est perdue, même si chaque transmission, prise seule, est fiable à .
Vérification : est le point fixe de la relation de 2.a, puisque . La convergence est rapide : , et dès , .
B.1. Ligne 5 : l'instruction rand() renvoie un réel aléatoire de , et la condition rand() < 0.1 est réalisée avec une probabilité égale à , la longueur de l'intervalle . Elle simule donc l'évènement « la transmission est contraire ».
Ligne 6 : dans ce cas, donnee prend la valeur 1 - donnee, c'est-à-dire 0 si elle valait 1 et 1 si elle valait 0 : la donnée est inversée. Dans l'autre cas, avec une probabilité de , la ligne 6 n'est pas exécutée et la donnée est recopiée telle quelle, ce qui simule une transmission fidèle. La ligne 7 ajoute ensuite la valeur transmise à la liste.
Le script tel qu'il est imprimé dans le sujet présente deux coquilles sans conséquence sur la question : il manque les deux-points à la fin de la ligne 5, sans lesquels Python refuse le programme, et la numérotation passe de 7 à 9. Le programme corrigé, avec l'import de rand, figure en fin de corrigé.
Erreur fréquente : affirmer que la ligne 6 « met la donnée à 0 ». L'expression 1 - donnee échange les deux valeurs, elle ne fixe rien : appliquée à une donnée qui vaut 0, elle donne 1.
B.2. Méthode : les transmissions successives sont simulées par des appels indépendants de rand() ; la probabilité d'une liste donnée est donc le produit des probabilités de chaque transmission, pour une transmission fidèle (valeur répétée) et pour une transmission contraire (valeur changée). C'est le principe multiplicatif le long d'un chemin de l'arbre.
simulation(4) effectue quatre transmissions. La liste [1, 1, 1, 1, 1] correspond à quatre transmissions fidèles : probabilité .
simulation(6) effectue six transmissions. Dans la liste [1, 0, 1, 0, 0, 1, 1], on compare chaque valeur à la suivante : contraire, contraire, contraire, fidèle, contraire, fidèle. Quatre transmissions contraires et deux fidèles : probabilité .
Arrondie à , cette probabilité vaut : il vaut mieux donner la valeur exacte , l'arrondi demandé « si nécessaire » faisant disparaître toute l'information.
Pièges : compter les valeurs de la liste au lieu des transmissions (une liste de valeurs ne compte que transmissions, d'où et non ) ; et confondre la valeur reçue avec le type de transmission : un 0 dans la liste n'est pas une transmission contraire, seul un CHANGEMENT de valeur l'est.
from random import random as rand
def simulation(n):
donnee = 1
liste = [donnee]
for k in range(n):
if rand() < 0.1:
donnee = 1 - donnee
liste.append(donnee)
return listeCoche ici les exercices faits ou à revoir : un compte gratuit, sans mot de passe, retient tes coches et tes réponses justes d'une visite à l'autre, te dit quel chapitre attaquer ensuite et te permet de demander l'exercice qui te manque. Crée ton espace, un courriel suffit.