Simulations – de paradoxes probabilistes – Qu'est-ce que le hasard ?

View Github Repository Open presentation in a new window

HackingMondays

See all presentation from HackingMondays

Simulations – de paradoxes probabilistes – Qu'est-ce que le hasard ?

0 0

pres-simulation-de-paradoxes-probabilistes

Présentation: Résolution de paradoxes probabilistes par la simulation

On Github HackingMondays / pres-simulation-de-paradoxes-probabilistes

Simulations

de paradoxes probabilistes

Ou comment résoudre des problemes complexes sans maths

Rodrigo Reyes / Hacking Mondays

Paradoxes probabilistes

Définition générique: Proposition contraire à l’opinion commune ou à la vraisemblance.

Les paradoxes probabilistes sont des problèmes de probabilités dont la solution est contre-intuitive

Qu'est-ce que le hasard ?

XKCD.com/221

Fonctions Random

  • Javascript: Math.random() renvoie un nombre entre 0 et 1
  • Java: Math.random() renvoie un nombre entre 0 et 1
  • C/C++: rand() renvoie un nombre entier entre 0 et RAND_MAX

Deux sortes de générateurs

  • Les générateurs de type "pseudo-random"
  • Les générateurs de type "pseudo-random"

Les premiers sont basés sur une formule mathématique, les seconds utilisent un pool d'entropie (bruit collecté au niveau du système d'exploitation)

Evaluation

Evaluation BSI

  • K1: les séquences de nombre ne se répètent pas (ou peu)
  • K2: propriétés statistiques identiques à celles d'un RNG idéal
  • K3: Impossible de deviner les valeurs suivantes ou antérieures à partir d'une sous-séquence
  • k4: Impossible de deviner les valeurs suivantes ou antérieures même en connaissant l'état interne du RNG

Le paradoxe des anniversaires

Combien de personnes doit-on réunir pour qu'il y ait une chance sur deux qu'il y ait deux personnes ayant le même jour d'anniversaire ?

Solution

Exercice

Trouver la solution (approximation) en écrivant un simulateur

Algorithme

  • Prendre un groupe de taille quelconque
  • Établir un jour anniversaire au hasard pour chaque membre (/365)
  • Vérifier s'il y a des jours identiques
  • Compter et itérer

Solution

Solution en Javascript

http://jsbin.com/zupuda/edit?js,console

Solution

n p(n) 1 0.0% 5 2.7% 10 11.7% 20 41.1% 23 50.7% 30 70.6% 40 89.1% 50 97.0% 60 99.4% 70 99.9% 100 99.99997%

Paradoxe de Monty Hall

Le joueur est placé devant 3 portes fermés, Derrière l'une d'elle se trouve un prix, les deux autres n'ont rien du tout.

Le joueur doit choisir une porte.

Ensuite l'animateur, qui sait où se trouve le prix, ouvre l'une des deux portes restantes et montre que le prix ne s'y trouve pas. Le joueur peut alors choisir de garder son choix initial, ou changer de porte.

Question

Le joueur doit-il garder sa porte, changer, ou bien est-ce que les probabilités restent identiques ?

Résumé

  • 3 portes, le joueur en choisit une
  • L'animateur en ouvre une
  • Le joueur peut alors changer de porte.

Quelle est la probabilité de succès s'il garde son premier choix ? S'il change de porte ?

Solution

Solution (contre-intuitive)

  • Quand au début du jeu il choisit une porte: 1/3
  • L'animateur ouvre une porte = il élimine une porte
  • La porte initiale: 1/3 La porte restante: 2/3

Écrivons un simulateur du jeu

Pour chaque tirage:

  • Le programme choisit la porte avec le prix
  • Le programme fait choisir une porte au joueur
  • Cas sans changement: le joueur gagne s'il avait choisit la bonne porte
  • Cas avec changement: le joueur gagne s'il avait choisit la mauvaise porte

Au moins 1000 tirages

Pour chaque tirage:

  • Trois portes
  • Le programme choisit la porte avec le prix
  • Le programme fait choisir une porte au joueur
  • Cas sans changement: le joueur gagne s'il avait choisit la bonne porte
  • Cas avec changement: le joueur gagne s'il avait choisit la mauvaise porte

Implémentation javascript

jsbin.com/sikitu/edit?js,console

Simulations de paradoxes probabilistes Ou comment résoudre des problemes complexes sans maths Rodrigo Reyes / Hacking Mondays