Jet de dé

Combien de fois faut-il jeter un dé à 6 faces pour espérer obtenir les 6 chiffres au moins une fois ?
Il faut le jeter 14 fois. Par contre avec 6 jets on ne peut espérer obtenir que 4 chiffres différents.

Combien d'échantillons aléatoires d'une dizaine de pages sont nécessaires pour espérer récupérer le contenu d'un livre de 300 pages ?
Il faut 192 échantillons (1 916 pages). Par contre avec 30 échantillons (300 pages) on ne peut espérer obtenir que 190 pages.

Explication

Pour un nombre (N) de chiffres (c.), on calcule l'espérance (E_n) pour chaque tirage (n), soit la probabilité d'avoir un chiffre différent que l'on ajoute à l'espérance précédente, plus la probabilité d'avoir un chiffre déjà obtenu qui implique la conservation l'espérance précédente.

Espérance en fonction de l'espérance précédente

• E₁ = 1 c.
• E₂ = (2 c.).(N-1)/N + (1 c.).1/N
  ⇒ E₂ = (2N-1)/N
• E₃ = (E₂ + 1 c.).(N - E₂)/N + (E₂ c.).E₂/N
  ⇒ E₃ = (E₂.N + N - E₂² - E₂ + E₂²) / N
  ⇒ E₃ = [E₂(N-1) + N] / N ⇒ E₃ = E₂(N-1)/N + 1
• E_n = E_n-1(N-1)/N + 1
  E_n = (1 - 1/N)E_n-1 + 1

Espérance en fonction du numéro de tirage

• On pose a = 1 - 1/N
  ⇒ E_n = aE_n-1 + 1
  ⇒ E_n = a(aE_n-2 + 1) + 1
  ⇒ E_n = a²E_n-2 + 1 + a
  ⇒ E_n = a²(a_n-3 + 1) + 1 + a + a²
  ⇒ E_n = a³_n-3 + 1 + a + a² + a³
  ⇒ E_n = a^n-1E1 + 1 + a + a² + a³ + ... + a^n-2
• Sachant E1 = 1
  ⇒ E_n = 1 + a + a² + a³ + ... + a^n-2 + a^n-1
  ⇒ E_n = (1-aⁿ)/(1-a)
  
• Hors 1-a = 1/N
  ⇒ E_n = N[1 - (1 - 1/N)ⁿ]

Tirage en fonction de l'espérance

• ⇒ (1 - 1/N)ⁿ = 1 - E_n/N
  ⇒ n = Ln(1 - E_n/N) / Ln(1 - 1/N)

Exemples

• Pour un dé à 6 faces : E(6) = 4 et E(14) ≈ 6
• Pour un livre de 300 pages : E(300) = 190 et E(1916) ≈ 300

---

Michel Corne. Tirage de nombres uniques, 1/2019.