Calcolo combinatorio per la probabilità

Prima: Spazi di probabilità discreti e uniformiIn uno spazio discreto la probabilità è determinata dalla densità discreta p(ω) = P({ω}), con somma 1, e P(A) è la somma di p(ω) sugli esiti di A; negli spazi uniformi (esiti equiprobabili) P(A) = |A| / |Ω|, casi favorevoli su casi possibili.Spazi di probabilità discreti e uniformi →. Dopo: Probabilità condizionataLa probabilità di A sapendo che si è verificato B è P(A ∣ B) = P(A ∩ B) / P(B), con P(B) > 0; è una nuova misura di probabilità, e da essa seguono la regola del prodotto e la regola della catena.Probabilità condizionata →. Esercizi svolti: Esercizio 4 · 42 teste in 100 lanci di una moneta e, in un appello, il lotto (probabilità che il 33 esca in un'estrazione di 5 numeri su 90).

In uno spazio uniformeΩ finito con esiti equiprobabili: P(A) = casi favorevoli / casi possibili.Spazi di probabilità discreti e uniformi → $\mathbb{P}(A) = |A| / |\Omega|$: servono regole per contare gli elementi di $A$ e di $\Omega$ senza elencarli.

Principio di moltiplicazione

Se una scelta si fa in $k$ passi successivi, e al passo $i$ ci sono $n_i$ possibilità qualunque siano le scelte fatte prima, il numero totale di scelte è $$n_1 \cdot n_2 \cdots n_k$$

Esempio. Un menù con 3 primi, 4 secondi e 2 dolci permette $3 \cdot 4 \cdot 2 = 24$ pasti diversi. Una targa con 2 lettere (26 possibili) e 3 cifre: $26^2 \cdot 10^3 = 676\,000$.

Tutte le formule seguenti sono casi particolari di questo principio.

Le quattro formule fondamentali

Si scelgono $k$ oggetti da un insieme di $n$ oggetti distinti. Le domande da farsi sono due:

1. L'ordine conta? ($(1, 2)$ e $(2, 1)$ sono scelte diverse?)
2. Si possono ripetere gli oggetti? (lo stesso oggetto può essere scelto più volte?)

Disposizioni con ripetizione: $n^k$

Sequenze ordinate di $k$ elementi presi da $n$, con ripetizioni ammesse. Per ogni posizione ci sono $n$ scelte, indipendentemente dalle altre: $n \cdot n \cdots n = n^k$.

Esempi: risultati di $k$ lanci di un dado: $6^k$; sequenze di $100$ lanci di moneta: $2^{100}$; parole binarie di 8 bit: $2^8 = 256$.

Disposizioni semplici: $\frac{n!}{(n-k)!}$

Sequenze ordinate di $k$ elementi distinti presi da $n$ ($k \le n$). Il primo si sceglie in $n$ modi, il secondo in $n - 1$ (non si può ripetere il primo), ..., il $k$-esimo in $n - k + 1$:

$$n (n-1) \cdots (n - k + 1) = \frac{n!}{(n-k)!}$$

Esempio: podio (oro, argento, bronzo) tra 10 atleti: $10 \cdot 9 \cdot 8 = 720$.

Permutazioni: $n!$

Caso $k = n$: modi di ordinare $n$ oggetti distinti, $n! = n (n-1) \cdots 2 \cdot 1$ (con la convenzione $0! = 1$).

Esempio: modi di mescolare un mazzo di 52 carte: $52! \approx 8 \cdot 10^{67}$.

Combinazioni: $\binom{n}{k}$

Sottoinsiemi di $k$ elementi di un insieme di $n$: ordine irrilevante, niente ripetizioni. Si contano le disposizioni semplici, $\frac{n!}{(n-k)!}$, e si osserva che ogni sottoinsieme di $k$ elementi è stato contato $k!$ volte (una per ogni ordine dei suoi elementi). Quindi

$$\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$$

Esempi: mani di 5 carte da un mazzo di 52: $\binom{52}{5} = 2\,598\,960$; cinquine del lotto da 90 numeri: $\binom{90}{5} = 43\,949\,268$.

Proprietà utili: $\binom{n}{0} = \binom{n}{n} = 1$, $\binom{n}{1} = n$, $\binom{n}{k} = \binom{n}{n-k}$ (scegliere i $k$ da prendere equivale a scegliere gli $n - k$ da lasciare).

Sequenze con un numero fissato di successi

Quante sequenze di lunghezza $n$ in $\{T, C\}$ hanno esattamente $k$ teste? Una sequenza è individuata dalle posizioni delle teste, cioè da un sottoinsieme di $k$ posizioni tra le $n$: sono $\binom{n}{k}$.

Esempio: con $n = 4$, $k = 2$: $TTCC, TCTC, TCCT, CTTC, CTCT, CCTT$, cioè $\binom42 = 6$ ✓.

Questo conteggio risolve il problema delle 42 teste su 100 lanci ($\binom{100}{42}$ sequenze favorevoli) e sta alla base del modello binomialeP(k successi in n prove) = (n su k) p^k (1−p)^(n−k).Prove ripetute e modello binomiale →.

Estrazioni da un'urna

Un'urna contiene $N$ palline, di cui $M$ nere e $N - M$ bianche. Se ne estraggono $n$. Le palline si pensano numerate (anche se dello stesso colore), così gli esiti sono equiprobabili.

Con reinserimento

Dopo ogni estrazione la pallina viene rimessa nell'urna: la composizione non cambia. Esiti: sequenze ordinate con ripetizione, $|\Omega| = N^n$. Ogni estrazione dà nera con probabilità $\frac{M}{N}$, indipendentemente dalle altre, e

$$\mathbb{P}(k \text{ nere}) = \binom{n}{k} \left(\frac{M}{N}\right)^k \left(1 - \frac{M}{N}\right)^{n-k}$$

(si scelgono le $k$ posizioni delle nere, poi per ciascuna posizione si sceglie la pallina: $\binom{n}{k} M^k (N - M)^{n-k}$ casi favorevoli su $N^n$).

Senza reinserimento

Le palline estratte non vengono rimesse. Conviene guardare l'insieme delle $n$ palline estratte (ordine irrilevante): $|\Omega| = \binom{N}{n}$. Per avere $k$ nere si scelgono $k$ nere tra le $M$ e $n - k$ bianche tra le $N - M$:

$$\boxed{\mathbb{P}(k \text{ nere}) = \frac{\binom{M}{k} \binom{N - M}{n - k}}{\binom{N}{n}}} \qquad \text{(distribuzione ipergeometrica)}$$

Esempio numerico: 8 nere e 6 bianche, 3 estrazioni

$N = 14$, $M = 8$, $n = 3$; probabilità di estrarre esattamente 2 nere.

• Senza reinserimento: $\dfrac{\binom82 \binom61}{\binom{14}3} = \dfrac{28 \cdot 6}{364} = \dfrac{168}{364} = \dfrac{6}{13} \approx 0{,}462$. Controllo con le sequenze ordinate: la sequenza $NNB$ ha probabilità $\frac{8}{14} \cdot \frac{7}{13} \cdot \frac{6}{12}$ (ogni pallina estratta cambia l'urna), e le posizioni della bianca sono 3: $3 \cdot \frac{8 \cdot 7 \cdot 6}{14 \cdot 13 \cdot 12} = \frac{1008}{2184} = \frac6{13}$ ✓. Contare con o senza ordine dà lo stesso risultato, purché si faccia la stessa scelta al numeratore e al denominatore.
• Con reinserimento: $\binom32 \left(\frac8{14}\right)^2 \frac6{14} = 3 \cdot \frac{16}{49} \cdot \frac37 = \frac{144}{343} \approx 0{,}420$.

La stessa urna (8 nere, 6 bianche, 2 estrazioni con reinserimento) compare nell'esercizio 3 del I parziale.

Esempio: il lotto

Si estraggono 5 numeri su 90 senza ripetizione. Probabilità che tra questi ci sia il 33:

$$\mathbb{P} = \frac{\binom{89}{4}}{\binom{90}{5}} = \frac{5}{90} = \frac1{18} \approx 0{,}056$$

Perché: le cinquine che contengono il 33 si ottengono fissando il 33 e scegliendo gli altri 4 numeri tra gli 89 rimanenti. La semplificazione: $\binom{89}{4} / \binom{90}{5} = \frac{89!}{4!\,85!} \cdot \frac{5!\,85!}{90!} = \frac{5}{90}$. Interpretazione: ciascuno dei 90 numeri ha la stessa probabilità di essere tra i 5 estratti, quindi $\frac{5}{90}$.

Esempio: il problema dei compleanni

In una classe di $k$ persone (365 giorni equiprobabili, niente anni bisestili), probabilità che almeno due compiano gli anni lo stesso giorno?

• $\Omega =$ sequenze ordinate di $k$ compleanni, con ripetizione: $|\Omega| = 365^k$.
• Il complementare "tutti i compleanni diversi" è fatto di disposizioni semplici: $365 \cdot 364 \cdots (365 - k + 1)$.

$$\mathbb{P}(\text{almeno due uguali}) = 1 - \frac{365 \cdot 364 \cdots (365 - k + 1)}{365^k}$$

Con $k = 23$ si ottiene già $\approx 0{,}507$: più di una possibilità su due. È un buon esempio di passaggio al complementareP(A) = 1 − P(Aᶜ): "almeno due uguali" è difficile da contare, "tutti diversi" è facile.Misura di probabilità e sue proprietà →.

Come scegliere la formula

1. Fissare $\Omega$ in modo che gli esiti siano equiprobabili (oggetti numerati, sequenze ordinate se c'è un ordine naturale).
2. Chiedersi se l'ordine conta e se ci sono ripetizioni → tabella sopra.
3. Contare $A$ con la stessa convenzione usata per $\Omega$.
4. Se $A$ è "almeno uno", provare a contare il complementare.

Errori comuni

• Mescolare convenzioni: contare $\Omega$ con l'ordine e $A$ senza (o viceversa).
• Confondere con e senza reinserimento: con reinserimento le estrazioni sono indipendenti e si usa la binomiale; senza, l'ipergeometrica.
• Dimenticare di moltiplicare per il numero di posizioni (es. $3$ posizioni per la bianca in $NNB$, $NBN$, $BNN$).
• Trattare come non distinguibili palline dello stesso colore: gli esiti "per colore" non sono equiprobabili.