2.5 Diagrammi ad albero

La formula di decomposizione combinata con la regola del prodotto e delle sue conseguenze viste nella sezione precedente forniscono (quasi) tutti gli strumenti utili per analizzare problemi di probabilità, riducendoli a problemi più semplici: tutta l’arte sta nell’individuare opportuni sistemi di alternative per cui il robot sia in grado di calcolare agevolmente le varie probabilità condizionate.

È particolarmente utile rappresentare allora l’introduzione di sistemi di sistemi di alternative tramite diagrammi ad albero, ossia di grafi (insiemi di nodi collegati da archi) in cui ogni nodo è etichettato da una affermazione ($A$, $B$, $I$ ecc.) e gli archi sono orientati e pesati con opportune probabilità, costruiti con il seguente algoritmo.

Si introduce un nodo “radice” la cui etichetta è l’informazione iniziale che si evince dal testo del problema (tipicamente si riserva la lettera greca $\Omega$ (omega) per tale informazione). Succesivamente si itera un numero finito di volte la seguente procedura:

si considera un nodo del grafo che sia una “foglia”, ossia senza archi uscenti, etichettato da una affermazione $B$,
si sceglie un sistema di alternative $(A_i)_{i=1}^n$, e si introducono tanti nodi quante le alternative, etichettate appunto da esse,
si introducono archi uscenti dalla foglia ($B$) verso il nodo corrispondente a ciascuna alternativa ($A_i$),
si pesa ciascun arco introdotto sopra con la probabilità \[P(A_i| B, I),\] dove $I$ consiste della congiunzione di tutte le affermazioni nell’unico cammino (orientato) che collega l’informazione iniziale $\Omega$ a $B$.

Si può mostrare che in questo modo si produce un grafo connesso e senza cicli (detto quindi un albero). Un albero costruito opportunamente può notevolmente semplificare le applicazioni delle regole di calcolo della probabilità.

Consideriamo un esempio più concreto, introducendo il cosiddetto modello delle estrazioni da un’urna. Supponiamo che vi sia una scatola (urna) contenente un certo numero di palline, tra di loro indistinguibili, eccetto che per il colore (che può essere rosso oppure blu). Il robot è informato che l’urna contiene un numero $N$ palline di cui $R$ sono rosse e $B$ blu, con $N$, $R$, $B$ numeri noti (per fissare le idee, potrebbe essere $R=3$, $B=2$ e quindi $N=5$, ma teniamoli qui come parametri, per ottenere delle formule generali). Una persona effettua un certo numero di estrazioni di palline, una dopo l’altra, senza rimpiazzo, ossia una volta tolte le palline e osservate, non vengono rimesse dentro l’urna (vedremo in seguito cosa cambia nel caso con rimpiazzo, ossia se le palline vengono rimesse dentro l’urna).

Indichiamo allora con $\Omega$ l’informazione iniziale descritta sopra, e supponendo che la persona effettui $n \le N$ estrazioni (anche qui $n$ è un parametro noto, ad esempio $n=2$), e per ciascuna estrazione $i =1, \ldots, n$ si introducono le due alternative semplici \[ R^i = \text{l'$i$-esima pallina estratta è rossa},\] \[ B^i = \text{l'$i$-esima pallina estratta è blu}.\] Una domanda naturale, cui il robot deve rispondere, è di calcolare \[P(R^i | \Omega),\] ossia la probabilità di estrarre una pallina rossa all’$i$-esima estrazione, senza che sia informato dell’esito di una qualsiasi estrazione.

Il caso $i=1$ è il più semplice da argomentare: la probabilità che si estragga una pallina rossa dall’urna è \[ P( R^1 | I) = \frac{R}{N}.\] Questo segue dal fatto che l’indistinguibilità delle palline (eccetto per il colore) fa sì che la probabilità di estrarre una pallina qualsiasi è uniforme (e vale $1/N$), mentre l’affermazione $R^1$ si scrive come disgiunzione (unione) tra $R$ affermazioni (corrispondenti alle $R$ palline rosse): la regola della somma allora implica la probabilità sopra. Notiamo che questo argomento mette in forma più precisa l’intuizione che la probabilità sia il rapporto tra numero di casi favorevoli ($R$) e numero di casi totali ($N$), vero solamente se la densità discreta attribuita alle alternative (i “casi”) sia uniforme.

Cosa accade alla seconda estrazione? Viene in aiuto la rappresentazione ad albero descritta sopra. Iniziamo dalla radice $\Omega$, cui aggiungiamo il primo sistema di alternative $R^1$, $B^1$. Osserviamo che le probabilità indicate sopra ciascun arco uscente (verso destra) sommano ad $1$, proprio perché è un sistema di alternative.

Figura 2.10: Diagramma ad albero per la prima estrazione.

Concentriamoci ora sul calcolo di $P(R^2 | \Omega)$, e decomponiamo ciascuna foglia (i nodi più a destra) rispetto al sistema di alternative $R^2$, $B^2$. Come determinare i pesi dati dalle probabilità $P(R^2 | R^1)$, $P(R^2 | B^1)$ ecc.? Possiamo argomentare così: se ad esempio si aggiunge l’informazione $R^1$, significa che prima della seconda estrazione il robot sa che l’urna contiene $R-1$ palline rosse e $B$ blu. Dovendo usare solo questa informazione, segue usando una sottostante probabilità uniforme che \[ P(R^2 | R^1) = \frac{R-1}{N-1},\] e similmente per gli altri casi.

Figura 2.11: Diagramma ad albero per la prima e seconda estrazione.

Possiamo calcolare quindi la probabilità $P(R^2|\Omega)$. Usando la formula di disintegrazione, troviamo (omettiamo $\Omega$ per semplicità) \[ \begin{split} P(R^2 ) & = P(R^2 | R^1) P(R^1) + P(R^2 | B^1) P(B^1) \\ & = \frac{R-1}{N-1} \cdot \frac R N + \frac{R}{N-1}\cdot \frac{B}{N-1} = \frac R N.\end{split}\] Possiamo allora ritrovare lo stesso risultato direttamente sfruttando l’albero, nel seguente modo:

per ciascun cammino (“ramo”) che collega il nodo $\Omega$ ad una foglia corrispondente all’evento $R^2$, si determina la probabilità ottenuta moltiplicando i pesi corrispondenti agli archi percorsi,
si sommano tutte le probabilità così ottenute.

Nell’esempio, abbiamo due soli rami e si trova esattamente la stessa formula per la probabilità di $R^2$.

Ma possiamo anche fare di più, una volta decomposto un problema in un albero abbastanza dettagliato, possiamo calcolare la probabilità di una qualsiasi affermazione $C$ (in questo caso, riguardante le prime due estrazioni). Basta infatti aggiungere un nodo etichettato con l’evento $C$ a ciascuna foglia dell’albero già costruito (con un arco pesato con la probabilità condizionata, come nell’algoritmo di costruzione dell’albero) e calcolare la probabilità con lo stesso metodo, ossia sommando le probabilità corrispondenti a ciascun ramo, partendo dalla radice fino a $C$. Ad esempio, sia \[ C = \text{nelle prime due estrazioni si estraggono due palline dello stesso colore}.\] Aggiungiamo $C$ all’albero nel seguente modo.

Figura 2.12: Un diagramma ad albero per l’evento $C$.

Calcolando la probabilità di ciascun ramo (notiamo che due hanno un peso nullo, quindi possiamo trascurarli) e sommando su tutti i rami, troviamo quindi che \[ P(C) = \frac{R}N \cdot \frac{R-1}{N-1} + \frac B N \cdot \frac{B-1}{N-1}.\]

La validità di questa tecnica si estende ad alberi arbitrariamente complessi, purché si faccia attenzione a due aspetti fondamentali quando, a partire da una foglia, si introduce un sistema di alternative:

tutte le alternative vanno inserite (eccetto quelle trascurabili, che possono essere tralasciate)
i pesi degli archi inseriti sono probabilità condizionate rispetto a tutta l’informazione complessiva dalla foglia fino alla radice.

Un controllo da fare per evitare l’errore comune di tralasciare qualche alternativa è di verificare che la somma delle probabilità sugli archi uscenti da ciascun nodo sia sempre $1$.

Osserviamo infine che non è necessario, come negli esempi visti, che l’albero sia ottenuto usando lo stesso sistema di alternative ad ogni passo della costruzione: a partire da una foglia siamo liberi di scegliere se proseguire con la costruzione e, nel caso, un sistema di alternative che riteniamo utile. Bisogna infatti bilanciare tra la necessità di creare un diagramma sufficientemente dettagliato e d’altra parte non introdurre troppe ramificazioni, che rendono i calcoli complicati con il rischio di perdere qualche termine nel corso della risoluzione.

Ad esempio, se è richiesta la probabilità di \[ D = \text{si estrae almeno una pallina blu nelle prime tre estrazioni},\] possiamo creare un albero in cui interrompiamo la costruzione nelle foglie in cui una pallina blu è estratta:

Figura 2.13: Un diagramma per il calcolo della probabilità di estrarre almeno una pallina blu in tre estrazioni.

Otteniamo quindi \[ P(D ) = \frac B N + \frac{R} N \cdot \frac {B}{N-1} + \frac R N \cdot \frac {R-1}{N-1}\cdot \frac{B}{N-2}.\] Concludiamo osservando che il modello delle estrazioni senza rimpiazzo è abbastanza semplice per poter ottenere molte formule esplicite per la probabilità di affermazioni interessanti. Ad esempio, tramite un uso ripetuto della regola del prodotto, si ottiene che la probabilità (rispetto all’informazione inizale $\Omega$) di estrarre una precisa sequenza ordinata di $n \le N$ palline colorate, di cui $r \le R$ sono rosse e le rimanenti $b \le B$ sono blu è data dalla formula \[ \frac{R(R-1)\cdot \ldots \cdot (R-r+1) \cdot B(B-1) \cdot \ldots \cdot (B-b+1)}{N(N-1)\cdot \ldots (N-n+1)}.\] Ad esempio, \[ P( R^1, B^2, R^3, B^4, R^5, B^6 ) = \frac{ R(R-1)(R-2)B(B-1)(B-2)}{N(N-1)(N-2)(N-3)(N-4)(N-5)}.\] In particolare, la probabilità non dipende dall’ordine in cui le palline rosse e blu vengono estratte nella precisa sequenza. Perciò, grazie alla regola della somma, possiamo anche ottenere la probabilità di estrarre una qualsiasi sequenza di $n \le N$ palline, di cui $r \le R$ rosse e le rimanenti $n-r=b \le B$ sono blu: si tratta di moltiplicare la probabilità di ottenere una di queste (ad esempio quella in cui si estraggono prima $r$ rosse e poi $b$ blu) per il numero totale di tali sequenze. Tale numero, è detto coefficiente binomiale e si scrive \[ {n \choose r} = \frac{n(n-1) \cdot \ldots \cdot (n-r+1)}{r (r-1) \cdot\ldots \cdot 1} = \frac{ n!}{r! (n-r)!},\] dove nell’ultima espressione abbiamo usato la funzione fattoriale \[ k! = k(k-1)\cdot \ldots \cdot 1.\]

Con semplici passaggi algebrici, si ottiene una formula piuttosto elegante, che usa solamente opportuni coefficienti binomiali: \[ P( \text{si estrae una qualsiasi sequenza con $r$ rosse e $b$ blu} | \Omega) = \frac{{R \choose r} {B \choose b}}{ {N \choose n}}.\] Osserviamo che, fissata la lunghezza $n$, al variare di $r \in \cur{0, \ldots, n}$, le affermazioni $A_r =$ “si estrae una qualsiasi sequenza con $r$ rosse e $b$ blu”, costituiscono un sistema di alternative. La formula è quindi la densità discreta di alternative (rispetto all’informazione iniziale $\Omega$) ed è detta per ragioni storiche densità ipergeometrica.

2.5.1 Esercizi

Esercizio 2.9 Tracciare un grafico a barre della densità ipergeometrica per i parametri $N=10$, $R= 5$ ed $n=6$, e determinarne la moda (si consiglia di usare il comando dhyper()).

Esercizio 2.10 Vi sono due urne dall’esterno indistinguibili, ciascuna contenente $3$ palline: la prima contiene $1$ pallina rossa e due blu, la seconda $2$ rosse e una blu. Si sceglie a caso un’urna tra le due e si estrae una pallina. Quale probabilità il robot attribuisce all’evento $R^1$? e all’evento “$R^1 \text{ e } R^2$”?