La risposta è $ n = 17 $ , con $ P (N_ {30} \ ge180) = 0,976388 $ .
L'approccio che ho adottato per calcolare la probabilità dopo 30 pareggi è stato quello di determinare la probabilità di pareggi visti rispetto a nomi non visti ad ogni round.
Quando si disegnano nomi $ n $ da $ p = 200 $ dopo aver visto $ s $ di loro, chiamiamo $ U_s $ il numero di nomi tra questi $ n $ precedentemente non visti.
Quindi abbiamo:
$$ P (U_s = u) = \ frac {\ text {P} (200-s, u) \ text {P} (s, nu) \ text { C} (n, u)} {\ text {P} (200, n)} $$
Il primo termine sono le permutazioni di u
nomi precedentemente non visti, le seconde permutazioni di nomi visti in precedenza. L'ultimo termine $ \ text {C (n, u)} $ rappresenta $ u $ non visto nomi che vengono in posizioni diverse dal $ n $ disegnato. Il denominatore tiene conto di tutte le possibili estrazioni di nomi $ n $ .
Dopo averlo calcolato, possiamo esaminare i successivi sorteggi di nomi. Chiamiamo $ N_d $ il numero totale di nomi dopo il disegno $ d $ .
Prima della prima estrazione, non ci saranno nessun nomi visti in precedenza, quindi nella prima estrazione verranno visualizzati tutti i nomi $ n $ per la prima volta.
$$ P (N_1 = n) = 1 $$
Possiamo quindi calcolare la probabilità di disegnare un certo numero di nomi durante il disegno $ N_ {d + 1} $ osservando le possibilità di disegnare dopo $ N_d $ e con un numero specifico di nomi mai visti prima. Con cui possiamo calcolare:
$$ P (N_ {d + 1} = x) = \ sum_ {i = 0} ^ {n} {P (N_d = xi) P (U_ {xi } = i)} $$
Ad esempio, se disegniamo $ n = 16 $ ogni volta, è possibile disegnare esattamente 180 nomi in totale in un disegno specifico disegnando 164 nomi nell'estrazione precedente e quindi disegnare esattamente 16 nomi non visti (per un totale di 180), o aver visto in precedenza 165 nomi e disegnare 15 nomi non visti e uno visto in precedenza, e così via ... Fino alla possibilità di aver visto 180 nomi nel iterazione precedente e disegnare tutti i 16 nomi visti in precedenza.
A questo punto possiamo usare l'iterazione per calcolare $ P (N_ {30} \ ge 180) $ per diversi valori di $ n $ .
Iterazione in Python:
Questo codice utilizza Python 3 e come scritto richiede Python 3.8 per math.comb ()
e math.perm ()
dalla libreria standard (se si utilizza una versione precedente di Python, puoi usare un'implementazione diversa di queste funzioni.)
Cominciamo con $ P (U_s = u) $ :
da functools importa lru_cache
dal pettine di importazione matematica, perm
@lru_cache
def prob_unseen (n, p, s, u):
# Restituisce la probabilità di disegnare
# esattamente $ u $ nomi invisibili quando
# disegno di nomi di $ n $ su un totale di $ p $ ,
# avendone già visti $ s $ .
ritorno (perm (p-s, u) *
perm (s, n-u) *
pettine (n, u) /
perm (p, n))
Abbastanza semplice. Ora per $ P (N_d = x) $ usiamo un elenco di 201 elementi (gli indici vanno da 0 a 200) per tenere traccia delle probabilità per ogni $ x $ :
def names_in_draw (prev_draw, n):
# Calcola le probabilità di trovare
# nomi esattamente $ x $ in questa estrazione,
# per ogni $ x $ , preso in considerazione
# le probabilità di aver disegnato specifiche
# numeri di nomi nell'estrazione precedente.
p = len (prev_draw) - 1
this_draw = [0.0] * (p + 1)
per x nell'intervallo (n, p + 1):
this_draw [x] = sum (
prev_draw [x-u] * prob_unseen (n, p, x-u, u)
per u nell'intervallo (n + 1))
restituisci this_draw
Infine, calcoliamo la probabilità per il numero di nomi dopo le estrazioni di $ d $ .
def total_names (n, p, d):
# Calcola le probabilità di trovare
# nomi esattamente $ x $ dopo i disegni $ d $ .
disegnare = [0,0] * (p + 1)
disegnare [n] = 1.0 # prima estrazione
per _ nell'intervallo (d):
draw = names_in_draw (draw, n)
pareggio di ritorno
Partiamo dalla prima estrazione, dove sappiamo per certo che disegneremo $ n $ nomi univoci. Quindi calcoliamo ripetutamente le probabilità $ d-1 $ volte.
Infine, possiamo calcolare la probabilità di disegnare almeno $ x $ nomi, disegnando $ n $ span > su $ p $ alla volta, eseguendo $ d $ disegni:
def prob_names (n, p, d, x):
# Restituisce la probabilità di vedere
# almeno $ x $ nomi dopo $ d $ disegni,
# ognuno dei quali disegna $ n $ da $ p $ nomi.
somma restituita (total_names (n, p, d) [x:])
Infine, possiamo eseguirlo per alcuni valori di $ n $ per trovare le probabilità:
>>> per i nell'intervallo (13, 20):
... print (i, prob_names (i, 200, 30, 180))
13 0,058384795418431244
14 0.28649904267865317
15 0.6384959089930037
16 0,8849450106842117
17 0.976388046862824
18 0.9966940083338005
19 0.9996649977705089
Quindi $ n = 17 $ è la risposta, con probabilità del 97,6388% di vedere almeno il 90% dei nomi. $ n = 16 $ si avvicina, con l'88,4945%.
(Dato che avevo il codice, ho anche guardato quanti disegni di un singolo nome sono necessari per vedere il 90% dei nomi, con il 90% di probabilità. Si scopre che sono 503 disegni,o 454 disegni per vedere il 90% dei nomi con il 50% di probabilità. Risultato piuttosto interessante!)