Plus le temps passe, plus j’ai l’impression d’être un dinosaure…. Lorsque j’étais jeune, j’écoutais de la musique sur des cassettes1. Je me souviens même avoir été enchanté par l’arrivée du premier walkman réversible: on n’était alors plus obligé de tourner la cassette au bout de 20 minutes. Quand soudain, à la fin des années 80 est arrivé le compact disc, et les lecteurs avec leur fonction Random ou Shuffle..
J’aurais du me douter que je tournerais mal parce que je me souviens avoir joué avec la platine de mes parents, en essayant de voir si la première chanson pouvait passer en premier avec une lecture aléatoire, mais aussi la seconde pouvait passer juste après. Bon, avec le recul, je me rends compte que j’ai du beaucoup user la platine parce qu’avec un disque de 10 titres, il faut 90 (ou 100) essais (en moyenne) pour qu’une lecture aléatoire commence effectivement par 1 et 2. C’est d’ailleurs à ce moment que j’ai aussi découvert les tirages avec et sans remises: avec certaines platines, on ne pouvait pas obtenir deux fois le même titre, alors que d’autres oui.
Puis sont arrivés les lecteurs mp3, où on n’avait plus 10 titres tirés au hasard, mais 200 voire 1000. Et l’autre jour en courant, je me suis posé les mêmes questions que lorsque j’étais tout petit (oui, je suis un dinosaure, mais j’étais jeune à cette époque): si le lecteur propose une fonction random avec remise, combien de chansons dois-je attendre, en moyenne, avant de réentendre une chanson que j’avais déjà entendu ?
- De la probabilité d’entendre deux fois une chanson ?
Pour faire un peu formel, supposons que mon lecteur contienne chansons.
La probabilité de n’avoir aucune répétition sur lectures (on suppose ) est
qui correspond aussi au nombre d’arrangements de éléments parmi , divisé par , soit
Si le ratio est faible (ou n est grand), on peut utiliser l’approximation et donc la probabilité s’approche par
soit tout simplement – toujours en cherchant une approximation – une probabilité de n’avoir aucune répétition de
Si on se donne une probabilité de n’avoir aucune répétition de , alors
Avec =200 chansons sur mon lecteur mp3, en jouant 17 titres, j’ai environ 1 chance sur 2 d’avoir au moins un titre joué deux fois. Et 17 chansons, ça correspond à ce que j’écoute en faisant mon jogging…. Bref, le temps de faire mon jogging, j’ai 1 chance sur 2 d’entendre un titre deux fois.
Mais que se passerait-il si je tenais le raisonnement inverse ?
- Problème dual et jogging interminable….
Autrement dit, combien de temps vais-je courir si je décide de m’arrêter lorsque j’entends (pour la première fois) un titre pour la seconde fois ? En fait, Donald Knuth en parle un peu dans son livre the art of computer programming: on peut montrer que l’espérance du nombre de titres qu’il faudra jouer pour avoir une première répétition parmi n titres est de la forme
qui admet un développement asymptotique
soit, toujours avec 200 titres dans mon lecteur, une vingtaine de titres à jouer, en moyenne. Ce qui rallongera un peu mon jogging, finalement…
Formellement, le premier correspond à une médiane, alors que le second à une espérance. Ce qui explique la différence.
Notons que si mon jogging classique dure la durée de 17 titres, la probabilité d’avoir un jogging deux fois plus long est quand même d’une chance sur 10,
autrement dit, j’ai une chance sur 100 (ce qui devrait donc arriver une fois dans l’année, en moyenne) de courir pendant 43 chansons… qui vont me paraître très très longues….