Informazione e Stima (Probabilità)

Analisi combinatoria

Il principio fondamentale del calcolo combinatorio

Il principio afferma che se un esperimento ha m esiti possibili e se un altro esperimento ha n esiti possibili, allora i due esperimenti hanno m × n esiti possibili.

Generalizzazione: si realizzino r esperimenti. Si supponga che il primo esperimento abbia n₁ esiti possibili, che per ognuno di questi il secondo esperimento abbia n₂ esiti possibili, che per ognuno degli esiti dei primi due esperimenti il terzo esperimento abbia n₃ esiti possibili ecc. Allora, se sequenze distinte di esiti degli esperimenti producono esiti finali distinti, allora gli esperimenti hanno in tutto n₁ × n₂ × ... × n_r esiti possibili.

Permutazioni

In quanti modi si possono ordinare le lettere a, b, c? Elencando tutti i casi possibili (abc, acb, bac, bca, cab, cba) si vede che ce ne sono sei. Ciascuno di questi ordinamenti prende il nome di permutazione.

Supponiamo ora di disporre di n oggetti; con un ragionamento simile si vede che ci sono n! = n × (n-1) × (n-2) × ... × 3 × 2 × 1 permutazioni di n oggetti.

Supponiamo ora di disporre di n oggetti, vediamo che ci sono n! permutazioni distinte di n oggetti, dei quali n₁ sono identici fra loro, n₂ sono identici tra loro e distinti dai precedenti, ..., n_r sono identici tra loro e distinti dai precedenti.

Combinazioni

Si vuole determinare il numero di insiemi che si possono formare con r oggetti a partire da un insieme di n oggetti, con r ≤ n.

Dato che (n × (n-1) × ... × (n-r+1)) / r! rappresenta il numero di scelte di r oggetti tra n tenendo conto dell'ordine nel quale questi vengono selezionati, e dato che un insieme di r oggetti viene in tal modo contato r! volte, si ha che il numero di sottoinsiemi di r oggetti che si possono formare da un insieme di n oggetti è (n × (n-1) × ... × (n-r+1)) / (r! × (n-r)!).

Definiamo per r ≤ n come C(n, r) = n! / ((n-r)! × r!). Il coefficiente binomiale, rappresenta il numero di combinazioni di r oggetti tra n, ovvero è il numero di sottoinsiemi di r oggetti che si possono formare con un insieme di n oggetti, senza tener conto dell'ordine di selezione.

Per convenzione si definisce 0! = 1. Pertanto C(n, 0) = C(n, n) = 1.

Coefficienti multinomiali

Si devono distribuire n oggetti distinti in r scatole distinte, in modo che ciascuna di esse contenga, nell'ordine, n₁, n₂, ..., n_r oggetti, dove n = n₁ + n₂ + ... + n_r.

In quanti modi si può effettuare questa suddivisione?

Ci sono n! possibili scelte per gli oggetti della prima scatola; per ogni tale scelta ci sono (n-n₁)! possibili scelte per gli oggetti della seconda scatola; per ogni scelta effettuata nelle prime due scatole ci sono (n-n₁-n₂)! scelte per gli oggetti della terza ecc.

Segue allora dal principio fondamentale della combinatoria che ci sono n! / (n₁! × n₂! × ... × n_r!) scelte possibili.

Probabilità

Definizioni, terminologia e assiomi

Si indica con prova o esperimento la singola esecuzione dell’esperimento casuale. Si noti che la prova può consistere ad esempio in un singolo lancio di moneta, in cui si considerano possibili i risultati [testa] [croce], ma può anche consistere nel lancio successivo di 10 monete in cui sono considerati risultati le 2¹⁰ sequenze di teste e croci.

È quindi indispensabile precisare quale sia l’esperimento a cui si fa riferimento e quali siano i suoi risultati elementari; quando si esegue la prova si ottiene un risultato elementare.

L’insieme di tutti i possibili risultati elementari è detto spazio campionario S (spazio degli eventi). Un evento è un sottoinsieme dello spazio degli eventi, cioè una qualunque collezione di risultati elementari. In particolare un evento può contenere un solo risultato elementare; in tal caso lo si chiama anche evento elementare.

Si dice che l’evento A si è verificato se il risultato della prova è contenuto in A.

• Evento impossibile: cioè l’insieme vuoto che non contiene alcun risultato e quindi non si verifica mai.
• Evento certo: che contiene tutti i risultati e quindi si verifica sempre.

Se A e B sono eventi anche l’unione (A o B) e l’intersezione (A e B) sono eventi:

• Unione: si verifica se il risultato appartiene ad A o a B.
• Intersezione: si verifica se il risultato appartiene sia ad A sia a B.

Si dicono disgiunti o mutuamente esclusivi eventi che hanno intersezione nulla, cioè che non possono verificarsi entrambi nella stessa prova.

• Assioma 1: Ad ogni evento A è assegnata una probabilità P(A) non negativa.
• Assioma 2: La probabilità dell'evento certo vale P(S) = 1.
• Assioma 3: Se l’intersezione A ∩ B = Ø si ha P(A ∪ B) = P(A) + P(B).

Ogni evento A ha probabilità P(A) ≤ 1.

• L’evento vuoto Ø ha probabilità nulla.
• La probabilità dell’unione di due eventi A e B è data da P(A ∪ B) = P(A) + P(B) - P(A ∩ B).

La probabilità che si verifichino sia A sia B (tale è il significato dell’intersezione) viene detta probabilità congiunta degli eventi A e B.

Variabili aleatorie

Gli spazi in cui i risultati sono equiprobabili hanno una semplice generalizzazione al caso di infiniti risultati, quando il risultato dell'esperimento è un numero reale, che viene detto variabile aleatoria.

Per una generica variabile aleatoria X, una significativa assegnazione di probabilità consiste nel definire la densità di probabilità, funzione per ogni possibile valore dell'argomento x.

Un modo alternativo per assegnare la probabilità è considerare gli eventi X<a, per ogni a, definendo la funzione di distribuzione.

Probabilità condizionate

Fissato un evento qualsiasi B con probabilità non nulla, il rapporto P(A ∩ B) / P(B) esprime la probabilità di quale evento? Tra i risultati che compongono l’evento A sono rilevanti solo quelli che appartengono anche a B, poiché al numeratore si ha l’intersezione di A con B.

Le probabilità P(A ∩ B) / P(B) sono quelle relative all’esperimento condizionato dall’evento B: lo spazio degli eventi dell’esperimento originale viene ridotto a B e tutti gli eventi non appartenenti a B sono irrilevanti. Le probabilità sono rinormalizzate dividendo per P(B), in modo che la loro somma sia unitaria e che B risulti l’evento certo; è come se l’esperimento originale venisse considerato valido solo se il risultato appartiene a B, cioè se si verifica B.

Le probabilità dell’esperimento condizionato si chiamano probabilità condizionate:

P(A|B) = P(A ∩ B) / P(B)

La definizione di probabilità condizionata è spesso utilizzata per calcolare la probabilità congiunta:

P(A ∩ B) = P(A|B) × P(B)

Teorema della probabilità totale:

Nel caso di variabili aleatorie, possiamo scrivere Densità marginale:

Indipendenza statistica

In generale una probabilità condizionata P(A|B) è diversa dalla probabilità P(A) non condizionata.

Nel caso in cui P(A|B) = P(A) l’evento A è altrettanto probabile nell’esperimento originale ed in quello condizionato a B; ovvero, sapere che si è verificato B non modifica le nostre attese sull’evento A. Gli eventi A e B si dicono indipendenti.

Quando assumiamo l’indipendenza di due eventi calcoliamo la probabilità congiunta come prodotto delle probabilità, ovvero P(A ∩ B) = P(A) × P(B).

Regola di Bayes

Una generica probabilità congiunta P(A ∩ B) può essere scritta in due modi, condizionando all’evento A oppure a B, scrivendo:

P(A ∩ B) = P(A|B) × P(B) = P(B|A) × P(A)

e quindi si può calcolare analogamente, per valutare le probabilità condizionate all'evento B di un insieme di eventi A mutuamente esclusivi e la cui unione sia l'evento certo.

Assiomi della probabilità

Spazio campionario ed eventi

Consideriamo un esperimento il cui risultato non possa essere previsto con certezza. Sebbene l’esito dell’esperimento non sia a priori noto, supponiamo che l’insieme di tutti i possibili esiti lo sia. Definiamo questo insieme spazio campionario S dell’esperimento.

Ogni sottoinsieme dello spazio campionario viene definito evento; cioè un evento è un insieme formato da possibili esiti di un esperimento. Se l’esito di un esperimento è contenuto in E, affermiamo che si è verificato.

Per due eventi E e F nello spazio campionario definiamo un nuovo evento unione E ∪ F formato da tutti gli esiti che stanno in E o in F o in entrambi. Questo significa che l’evento si verifica se almeno uno tra E e F si verifica.

Per due eventi E e F nello spazio campionario definiamo un nuovo evento intersezione E ∩ F formato da tutti gli esiti che sono contenuti sia in E che in F. Questo significa che l’evento si verifica se entrambi E e F si verificano.

Assiomi della probabilità

Consideriamo un esperimento il cui spazio campionario sia S. Per ogni evento E dello spazio campionario, definiamo un numero P(E) (probabilità dell’evento E), il quale soddisfi i seguenti tre assiomi:

• Assioma 1: P(E) ≥ 0: la probabilità è un numero non negativo.
• Assioma 2: P(S) = 1: la probabilità dello spazio campionario è 1.
• Assioma 3: Se l’intersezione di due eventi è Ø, si ha che P(E ∪ F) = P(E) + P(F).

Proprietà

P(E') = 1 - P(E)

Se E ⊆ F, allora P(E) ≤ P(F).