Calcolo della probabilità di estrazioni ripetute
Buongiorno,
Avrei necessità di un aiuto per capire come effettuare il seguente calcolo di probabilità.
Ho un urna contenente 8 palline, numerate da 1 a 8.
Eseguo 12 estrazioni con reinserzione generando una sequenza di 12 numeri corrispondente alla sequenza delle 12 palline estratte.
Mi chiedo quale è la probabilità che nella sequenza generata compaiano 5 qualunque delle 8 palline contenute nell'urna, e le altre 3 non vi compaiano.
Per esempio sarebbero favorevoli le seguenti sequenze:
1,2,3,4,5,1,1,1,1,1,1,1, in cui compaiono le 5 palline 1,2,3,4,5 e in cui le 3 palline 6,7,8 non compaiono
1,2,1,1,6,1,1,5,1,8,2,8, in cui compaiono le 5 palline 1,2,6,5,8 e in cui le 3 palline 3,4,7 non compaiono
2,1,1,1,1,6,5,1,7,1,7,2, in cui compaiono le 5 palline 2,1,6,5,7 e in cui le 3 palline 3,4,8 non compaiono
7,3,3,8,3,6,3,6,4,8,8,4, in cui compaiono le 5 palline 7,3,8,6,4 e in cui le 3 palline 1,2,5 non compaiono
Sarebbero invece sfavorevoli le seguenti:
1,2,3,4,2,1,1,1,1,1,1,1, perché contiene solo le seguenti 4 palline: 1,2,3,4
1,2,1,1,6,1,1,5,1,3,2,8, perché contiene più di 5 palline: 1,2,6,5,3,8
Per facilitare le notazioni userei le seguenti lettere:
N = 8 (palline nell'urna)
k = 12 (estrazioni)
h = 5
A me sembrava che la probabilità cercata potesse essere qualcosa del tipo:
$ P(h; k, N) = ( (k), (h) ) * N_h * h^(k-h) $
ma non funziona.
C'è certamente almeno un errore di concetto nel coefficiente binomiale $ ( (k), (h) ) $.
Per numeri bassi la formula senza il coefficiente binomiale sembra funzionare.
Vi ringrazio,
Paolo
Avrei necessità di un aiuto per capire come effettuare il seguente calcolo di probabilità.
Ho un urna contenente 8 palline, numerate da 1 a 8.
Eseguo 12 estrazioni con reinserzione generando una sequenza di 12 numeri corrispondente alla sequenza delle 12 palline estratte.
Mi chiedo quale è la probabilità che nella sequenza generata compaiano 5 qualunque delle 8 palline contenute nell'urna, e le altre 3 non vi compaiano.
Per esempio sarebbero favorevoli le seguenti sequenze:
1,2,3,4,5,1,1,1,1,1,1,1, in cui compaiono le 5 palline 1,2,3,4,5 e in cui le 3 palline 6,7,8 non compaiono
1,2,1,1,6,1,1,5,1,8,2,8, in cui compaiono le 5 palline 1,2,6,5,8 e in cui le 3 palline 3,4,7 non compaiono
2,1,1,1,1,6,5,1,7,1,7,2, in cui compaiono le 5 palline 2,1,6,5,7 e in cui le 3 palline 3,4,8 non compaiono
7,3,3,8,3,6,3,6,4,8,8,4, in cui compaiono le 5 palline 7,3,8,6,4 e in cui le 3 palline 1,2,5 non compaiono
Sarebbero invece sfavorevoli le seguenti:
1,2,3,4,2,1,1,1,1,1,1,1, perché contiene solo le seguenti 4 palline: 1,2,3,4
1,2,1,1,6,1,1,5,1,3,2,8, perché contiene più di 5 palline: 1,2,6,5,3,8
Per facilitare le notazioni userei le seguenti lettere:
N = 8 (palline nell'urna)
k = 12 (estrazioni)
h = 5
A me sembrava che la probabilità cercata potesse essere qualcosa del tipo:
$ P(h; k, N) = ( (k), (h) ) * N_h * h^(k-h) $
ma non funziona.
C'è certamente almeno un errore di concetto nel coefficiente binomiale $ ( (k), (h) ) $.
Per numeri bassi la formula senza il coefficiente binomiale sembra funzionare.
Vi ringrazio,
Paolo
Risposte
Allora, si potrebbe ragionare in questo modo.
Si potrebbe iniziare stabilendo in modo fisso il gruppo di 5 palline che vogliamo che siano estratte.
Ad esempio fisso il gruppo $1,2,3,4,5$ oppure il gruppo $4,5,6,7,8$.
Quindi mi chiedo qual e' la probabilità' di fare 12 estrazioni con re-inserzione di una delle palline del gruppo che ho fissato.
E' facile, la probabilita' e' $(5/8)^{12}$.
Pero' siccome il problema che hai proposta prevede che il gruppo di palline "prescelte" non sia fissato, ma sia libero, una combinazione qualunque, allora ci chiediamo quanti siano i gruppi possibili di palline prescelte, ovvero le combinazioni di 5 palline su 8.
Qui entra in gioco il binomiale, siccome la risposta e': $( (8), (5) )$.
Allora la risposta al tuo quesito sara' la probabilita' di estrarre un certo gruppo fissato di palline, moltiplicato per il numero di gruppi possibili.
In generale quindi la risposta sara':
$\cancel{P(N,n,k) = ( (N), (h) ) (h/N)^k} $ edit: non risponde al problema dato !
con
$N = 8$ (palline nell'urna)
$k = 12$ (estrazioni)
$h = 5$
Si potrebbe iniziare stabilendo in modo fisso il gruppo di 5 palline che vogliamo che siano estratte.
Ad esempio fisso il gruppo $1,2,3,4,5$ oppure il gruppo $4,5,6,7,8$.
Quindi mi chiedo qual e' la probabilità' di fare 12 estrazioni con re-inserzione di una delle palline del gruppo che ho fissato.
E' facile, la probabilita' e' $(5/8)^{12}$.
Pero' siccome il problema che hai proposta prevede che il gruppo di palline "prescelte" non sia fissato, ma sia libero, una combinazione qualunque, allora ci chiediamo quanti siano i gruppi possibili di palline prescelte, ovvero le combinazioni di 5 palline su 8.
Qui entra in gioco il binomiale, siccome la risposta e': $( (8), (5) )$.
Allora la risposta al tuo quesito sara' la probabilita' di estrarre un certo gruppo fissato di palline, moltiplicato per il numero di gruppi possibili.
In generale quindi la risposta sara':
$\cancel{P(N,n,k) = ( (N), (h) ) (h/N)^k} $ edit: non risponde al problema dato !
con
$N = 8$ (palline nell'urna)
$k = 12$ (estrazioni)
$h = 5$
"Quinzio":
Allora, si potrebbe ragionare in questo modo.
Si potrebbe iniziare stabilendo in modo fisso il gruppo di 5 palline che vogliamo che siano estratte.
Ad esempio fisso il gruppo $1,2,3,4,5$ oppure il gruppo $4,5,6,7,8$.
Quindi mi chiedo qual e' la probabilità' di fare 12 estrazioni con re-inserzione di una delle palline del gruppo che ho fissato.
E' facile, la probabilita' e' $(5/8)^{12}$.
Ma ci potrebbero essere meno di 5 numeri distinti.
"Paolo-1":
Avrei necessità di un aiuto per capire come effettuare il seguente calcolo di probabilità.
Ho un urna contenente 8 palline, numerate da 1 a 8.
Eseguo 12 estrazioni con reinserzione generando una sequenza di 12 numeri corrispondente alla sequenza delle 12 palline estratte.
Mi chiedo quale è la probabilità che nella sequenza generata compaiano 5 qualunque delle 8 palline contenute nell'urna, e le altre 3 non vi compaiano.
Userei una Catena di Markov. https://it.wikipedia.org/wiki/Processo_markoviano ma faccio tutto con le Catene di Markov e magari ci sono altri metodi più immediati.
"ghira":
Ma ci potrebbero essere meno di 5 numeri distinti.
Si. Hai ragione.
A questo punto dal numero $h^k$ vanno tolte tutte le combinazioni che hanno meno di $h$ numeri distinti.
Questo pero' significa che viene una formula ricorsiva con tutti i fastidi del caso.
Probabilmente usando le catene markoviane suggerite da ghira si arriva alla stessa conclusione.
Non conosco le catene markoviane anche se sono nella lista delle cose da imparare in un qualche futuro.
Comunque la formula sarebbe questa:
$M(N, h, k) = ((N),(h))(h^k - \sum_{\bar h = 1}^{h-1} M(h, \bar h, k))$.
Questo e' il conteggio dei modi $M(N, h, k)$ di ottenere esattamente $h$ palline distinte in $k$ "estrazioni con reinserimento" da un'urna contenente $N$ palline.
Se si vuole la probabilita', basta dividere per $N^k$.
$P(N, h, k) = {M(N, h, k)} / N^k$
Qui sotto c'e' anche un programmino in Python per fare qualche esperimento.
Ovviamente non e' ottimizzato.
Se si vuole fare una cosa "seria" bisogna passare al C e salvare delle tabelle in memoria per il fattoriale e per le ricorsioni gia' calcolate.
import math
def M(N, h, k):
bino = int(math.factorial(N)/math.factorial(h)/math.factorial(N-h))
t = int(h**k)
for h_bar in range(0, h):
t -= M(h, h_bar, k)
return int(bino * t)
NN = int(input('inserisci numero palline nell\'urna N: '))
hh = int(input('inserisci numero palline distinte h: '))
kk = int(input('inserisci estrazioni k: '))
res = M(NN, hh, kk)
print ("Numero di modi M: ", res)
print ("Probabilita' P: ", res/NN**kk)
Ecco un tenativo:
0 0
1 1.16415321826935e-10
2 1.66811514645815e-06
3 0.000423063989728689
4 0.0149494979996234
5 0.134889967739582
6 0.388315301388502
7 0.368114076554775
8 0.0933064240962267
prob totale: 1
Probabilità di avere 5 numeri distinti dopo 12 estrazioni: 0,134889967739582
Ho calcolato gli altri valori solo per controllare la probabilità totale.
#!/usr/bin/perl
#p[i][j]=prob i numeri distinti dopo j estrazioni
$p[0][0]=1;
for (1..8) {
$p[$_][0]=0;
}
sub p {
my $i=shift;
my $j=shift;
#print "chiamata con $i $j\n";
if (!defined $p[$i][$j]) {
#print "valore sconsciuto\n";
if ($i==0) {
$p[$i][$j]=0;
} else {
$p[$i][$j]=p($i,$j-1)*$i/8+p($i-1,$j-1)*(8-$i+1)/8;
}
}
#print "nuovo valore $i $j -> $p[$i][$j]\n";
return $p[$i][$j];
}
for (0..8) {
$p=p($_,12);
$t+=$p;
print "$_ $p\n";
}
print "prob totale: $t\n";
0 0
1 1.16415321826935e-10
2 1.66811514645815e-06
3 0.000423063989728689
4 0.0149494979996234
5 0.134889967739582
6 0.388315301388502
7 0.368114076554775
8 0.0933064240962267
prob totale: 1
Probabilità di avere 5 numeri distinti dopo 12 estrazioni: 0,134889967739582
Ho calcolato gli altri valori solo per controllare la probabilità totale.
Vi ringrazio molto.
Prendo un po' di tempo per verificare entrambe le strade che avete suggerito e vi do un riscontro.
Paolo
Prendo un po' di tempo per verificare entrambe le strade che avete suggerito e vi do un riscontro.
Paolo
Partendo dalle vostre indicazioni ho ricalcolato la probabilità ottenendo i vostri stessi risultati.
Vi ringrazio per l'aiuto che mi avete dato!
Non ho usato il calcolo combinatorio, ma qualcosa simile a una catena di Markov. Riassumo a grandi linee l'idea.
1. Osservare che ogni estrazione può solo riconfermare lo stato del sistema (se esce una pallina già pescata prima) o trasformare lo stato del sistema nello stato immediatamente successivo (se esce una pallina nuova).
2. Introdurre un vettore di N+1 componenti che rappresenta, dopo ogni estrazione, lo stato del sistema, inteso come numero di palline diverse contenute nella sequenza dei k numeri.
Per esempio:
(1, 0, 0, 0, 0, 0, 0, 0, 0), rappresenta la situazione in cui nella sequenza non compare nemmeno una pallina (questo è ad esempio lo stato che si ha prima della prima estrazione).
(0, 1, 0, 0, 0, 0, 0, 0, 0), rappresenta la una sequenza che contiene una sola pallina (per esempio alla prima estrazione, o alla seconda estrazione se è uscita due volte la stessa pallina... o alla dodicesima estrazione, se la medesima pallina è uscita per 12 volte).
...e così via...
Per esempio:
(0, 0, 0, 0, 0, 0, 0, 0, 1), rappresenta la situazione la sequenza contiene 8, palline diverse (è ovvio che alla quarta estrazione il sistema non potrà certo trovarsi in questo stato).
3. Osservare che quelli sopra sono una base per il vettore di stato. Osservare che se si conosce come l'estrazione trasforma i vettori della base allora si conosce anche come l'estrazione trasforma ogni loro combinazione lineare; e conoscere i trasformati dei generatori significa conoscere le colonne della matrice di trasformazione.
4. Scrivere con il criterio appena detto le colonne della matrice di trasformazione.
Le colonne sono appunto:
Prima colonna: (0, 1, 0, 0, 0, 0, 0, 0, 0)^trasp, che rende conto che alla prima estrazione lo stato iniziale (1, 0, 0, 0, 0, 0, 0, 0, 0) non può che andare a finire nello stato (0, 1, 0, 0, 0, 0, 0, 0, 0)
Seconda colonna: (0, 1/8, 7/8, 0, 0, 0, 0, 0, 0)^trasp, che rende conto che lo stato (0, 1, 0, 0, 0, 0, 0, 0, 0) viene riconfermato con una probabilità 1/8 e trasformato nel successivo stato (0, 0 , 1, 0, 0, 0, 0, 0, 0) con probabilità 7/8.
Terza colonna: (0, 0, 2/8, 6/8, 0, 0, 0, 0, 0)^trasp, che rende conto lo stato (0, 0, 1, 0, 0, 0, 0, 0, 0) viene riconfermato con una probabilità su 2/8 e trasformato nel successivo stato (0, 0 , 0, 1, 0, 0, 0, 0, 0) con probabilità 6/8.
...e così via fino all'ultima colonna.
5. Una volta scritta la matrice, applicarla al vettore di stato tante volte quante sono le estrazioni.
Ecco il codice in VBA:
e i risultati, identici a quelli ottenuti da Ghira
h PkkN(k=12, N=8)
1 1,164153218269350E-10
2 1,668115146458150E-06
3 4,230639897286890E-04
4 1,494949799962340E-02
5 1,348899677395820E-01
6 3,883153013885020E-01
7 3,681140765547750E-01
8 9,330642409622670E-02
Somma 1
Grazie ancora e a presto!
Vi ringrazio per l'aiuto che mi avete dato!
Non ho usato il calcolo combinatorio, ma qualcosa simile a una catena di Markov. Riassumo a grandi linee l'idea.
1. Osservare che ogni estrazione può solo riconfermare lo stato del sistema (se esce una pallina già pescata prima) o trasformare lo stato del sistema nello stato immediatamente successivo (se esce una pallina nuova).
2. Introdurre un vettore di N+1 componenti che rappresenta, dopo ogni estrazione, lo stato del sistema, inteso come numero di palline diverse contenute nella sequenza dei k numeri.
Per esempio:
(1, 0, 0, 0, 0, 0, 0, 0, 0), rappresenta la situazione in cui nella sequenza non compare nemmeno una pallina (questo è ad esempio lo stato che si ha prima della prima estrazione).
(0, 1, 0, 0, 0, 0, 0, 0, 0), rappresenta la una sequenza che contiene una sola pallina (per esempio alla prima estrazione, o alla seconda estrazione se è uscita due volte la stessa pallina... o alla dodicesima estrazione, se la medesima pallina è uscita per 12 volte).
...e così via...
Per esempio:
(0, 0, 0, 0, 0, 0, 0, 0, 1), rappresenta la situazione la sequenza contiene 8, palline diverse (è ovvio che alla quarta estrazione il sistema non potrà certo trovarsi in questo stato).
3. Osservare che quelli sopra sono una base per il vettore di stato. Osservare che se si conosce come l'estrazione trasforma i vettori della base allora si conosce anche come l'estrazione trasforma ogni loro combinazione lineare; e conoscere i trasformati dei generatori significa conoscere le colonne della matrice di trasformazione.
4. Scrivere con il criterio appena detto le colonne della matrice di trasformazione.
Le colonne sono appunto:
Prima colonna: (0, 1, 0, 0, 0, 0, 0, 0, 0)^trasp, che rende conto che alla prima estrazione lo stato iniziale (1, 0, 0, 0, 0, 0, 0, 0, 0) non può che andare a finire nello stato (0, 1, 0, 0, 0, 0, 0, 0, 0)
Seconda colonna: (0, 1/8, 7/8, 0, 0, 0, 0, 0, 0)^trasp, che rende conto che lo stato (0, 1, 0, 0, 0, 0, 0, 0, 0) viene riconfermato con una probabilità 1/8 e trasformato nel successivo stato (0, 0 , 1, 0, 0, 0, 0, 0, 0) con probabilità 7/8.
Terza colonna: (0, 0, 2/8, 6/8, 0, 0, 0, 0, 0)^trasp, che rende conto lo stato (0, 0, 1, 0, 0, 0, 0, 0, 0) viene riconfermato con una probabilità su 2/8 e trasformato nel successivo stato (0, 0 , 0, 1, 0, 0, 0, 0, 0) con probabilità 6/8.
...e così via fino all'ultima colonna.
5. Una volta scritta la matrice, applicarla al vettore di stato tante volte quante sono le estrazioni.
Ecco il codice in VBA:
Function PhkN(h, k, N)
'
' Urna contenente N palline numerate da 1 a N
' Si eseguono k estrazioni con reinserzione generando una sequenza di k numeri corrispondente alla sequenza delle k palline estratte.
' Si vuole calcolare la probabilità che nella sequenza generata compaiano h qualunque delle N palline contenute nell'urna, e le altre N-h non vi compaiano.
' PhkN(h, k, N) restituisce la probabilità cercata
' (il codice funzione per urne contenenti fino a 1000 palline, ma basta sostituire 1000 con 10000 per aumentare fino a 10000)
'
' Esempio.
' Urna contenente 8 palline, numerate da 1 a 8.
' Si eseguono 12 estrazioni con reinserzione generando una sequenza di 12 numeri corrispondente alla sequenza delle 12 palline estratte.
' Si vuole calcolare la probabilità che nella sequenza generata compaiano 5 qualunque delle 8 palline contenute nell'urna, e le altre 3 non vi compaiano.
' Per esempio sarebbero favorevoli le seguenti sequenze:
' 1,2,3,4,5,1,1,1,1,1,1,1, in cui compaiono le 5 palline 1,2,3,4,5 e in cui le 3 palline 6,7,8 non compaiono
' 1,2,1,1,6,1,1,5,1,8,2,8, in cui compaiono le 5 palline 1,2,6,5,8 e in cui le 3 palline 3,4,7 non compaiono
' 2,1,1,1,1,6,5,1,7,1,7,2, in cui compaiono le 5 palline 2,1,6,5,7 e in cui le 3 palline 3,4,8 non compaiono
' 7,3,3,8,3,6,3,6,4,8,8,4, in cui compaiono le 5 palline 7,3,8,6,4 e in cui le 3 palline 1,2,5 non compaiono
' Sarebbero invece sfavorevoli le seguenti:
' 1,2,3,4,2,1,1,1,1,1,1,1, perché contiene solo le seguenti 4 palline: 1,2,3,4
' 1,2,1,1,6,1,1,5,1,3,2,8, perché contiene più di 5 palline: 1,2,6,5,3,8
'
' Ponendo:
' N = 8 (palline nell'urna)
' k = 12 (estrazioni)
' h = 5
' il codice fornisce PhkN(5, 12, 8) = 0,134889968
' vedere https://www.matematicamente.it/forum/viewtopic.php?f=34&t=216643
' Inizializzo il valore restituito a un numero assurdo
PhkN = -3
' Definisco il contatore di riga
Dim i As Double
i = 0
' Definisco il contatore di colonna
Dim j As Double
j = 0
' Definisco il vettore di probabilità
Dim hp(1000, 0) As Double
hp(0, 0) = 1
For i = 1 To N
hp(i, 0) = 0
Next
Dim hp_new(1000, 0) As Double
For i = 0 To N
hp_new(i, 0) = 0
Next
' Definisco la matrice di probabilità
Dim prop(1000, 1000) As Double
Dim rg As Double
rg = N
' Inizializzo la matrice di probabilità
For j = 0 To rg
For i = 0 To rg
If (i = j) Then
prop(i, j) = j / rg
ElseIf (i = j + 1) Then
prop(i, j) = 1 - prop(i - 1, j)
Else
prop(i, j) = 0
End If
Next
Next
' Applico la matrice di probabilità al vettore di stato tante volte quante sono le estrazioni
Do While (k - 1 >= 0)
For i = 0 To rg
For j = 0 To rg
hp_new(i, 0) = hp_new(i, 0) + prop(i, j) * hp(j, 0)
Next
Next
For i = 0 To N
hp(i, 0) = hp_new(i, 0)
hp_new(i, 0) = 0
Next
k = k - 1
Loop
PhkN = hp(h, 0)
End Function
e i risultati, identici a quelli ottenuti da Ghira
h PkkN(k=12, N=8)
1 1,164153218269350E-10
2 1,668115146458150E-06
3 4,230639897286890E-04
4 1,494949799962340E-02
5 1,348899677395820E-01
6 3,883153013885020E-01
7 3,681140765547750E-01
8 9,330642409622670E-02
Somma 1
Grazie ancora e a presto!
"Paolo-1":
Non ho usato il calcolo combinatorio, ma qualcosa simile a una catena di Markov.
Hai usato _esattamete_ una catena di Markov, direi.
Solitamente faccio come hai fatto tu: stato iniziale, ecc.
Se vuoi fare _tantissime_ iterazioni può essere utile calcolare l'$n$-esima potenza della matrice elevando al quadrato più volte di seguito o con gli autovettori ecc.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo