SUPERCAT.DEV

Prendiamo sei giocatori e assegniamo a ciascuno un cartellino con il proprio numero:

1 2 3 4 5 6

Poi raccogliamo i sei cartellini, li mescoliamo in modo uniforme e ne restituiamo uno a ciascun giocatore.

Può capitare che qualcuno riceva il proprio numero. Può anche capitare che tutti ricevano un numero diverso dal proprio.

La domanda è:

Qual è la probabilità che nessuno dei sei giocatori riceva il proprio cartellino?

Questo è un caso del classico problema delle rencontres. In termini combinatori, stiamo cercando le permutazioni senza punti fissi, chiamate derangements.

Prima di calcolare: che cosa stiamo permutando?

Una restituzione completa dei sei cartellini è una permutazione dei numeri da 1 a 6.

Le permutazioni possibili sono:

6!
=
720

Assumiamo che il mescolamento sia uniforme, quindi ciascuna delle 720 permutazioni ha la stessa probabilità.

Chiamiamo punto fisso una posizione nella quale il cartellino coincide con il giocatore che lo riceve.

Per esempio:

giocatori:   1 2 3 4 5 6
cartellini:  2 1 3 6 4 5

il giocatore 3 ha ricevuto il cartellino 3.

Quella permutazione ha quindi un punto fisso.

Un derangement è invece una permutazione con:

0 punti fissi

Perché non possiamo moltiplicare semplicemente 5/6 sei volte?

Per il primo giocatore ci sono cinque cartellini sbagliati su sei, quindi potremmo essere tentati di scrivere:

(5/6)^6
≈
33,49%

Ma non è il modello giusto.

Dopo aver assegnato un cartellino al primo giocatore, quel cartellino non è più disponibile per gli altri. Le condizioni:

"il giocatore 1 non riceve 1"
"il giocatore 2 non riceve 2"
...

non sono eventi indipendenti.

Il problema non è una sequenza di sei prove Bernoulli con probabilità costante 5/6.

Dobbiamo contare direttamente le permutazioni che evitano tutti i punti fissi.

Usiamo inclusione-esclusione

Indichiamo con:

A_i

l'evento:

"il giocatore i riceve il proprio cartellino"

Se imponiamo un punto fisso specifico, per esempio il giocatore 1 corretto, restano da permutare liberamente cinque cartellini:

$$ 5! $$

Se imponiamo due punti fissi specifici, restano:

$$ 4! $$

permutazioni.

Con tre punti fissi specifici ne restano:

$$ 3! $$

E così via.

Ma dobbiamo anche scegliere quali giocatori sono fissati. Per k punti fissi specificati ci sono:

$$ \binom{6}{k} $$

scelte.

Il principio di inclusione-esclusione ci permette quindi di contare le permutazioni che non appartengono a nessuno degli eventi A_i:

D_6
=
6!
- C(6,1)5!
+ C(6,2)4!
- C(6,3)3!
+ C(6,4)2!
- C(6,5)1!
+ C(6,6)0!

Sostituendo i valori:

D_6
=
720
- 720
+ 360
- 120
+ 30
- 6
+ 1

quindi:

D_6
=
265

Esistono esattamente 265 permutazioni dei sei cartellini nelle quali nessuno torna al proprio posto.

La probabilità è dunque:

P(nessun punto fisso)
=
265/720
=
53/144
≈
36,8056%

Il valore è sensibilmente diverso dal 33,49% prodotto dall'ipotesi errata di indipendenza.

La formula generale dei derangements

Con n elementi, lo stesso ragionamento dà:

D_n
=
sum(k=0..n)
(-1)^k C(n,k)(n-k)!

Ma:

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

quindi possiamo raccogliere n!:

D_n
=
n!
sum(k=0..n)
(-1)^k/k!

La probabilità che una permutazione uniforme di n elementi non abbia punti fissi è allora:

D_n/n!
=
sum(k=0..n)
(-1)^k/k!

Questa formula è particolarmente interessante perché il fattoriale enorme del numero totale di permutazioni si semplifica completamente nella probabilità.

Perché compare 1/e?

La serie di Taylor di $e^{-1}$ è:

$$ e^{-1} = 1 - 1 + 1/2! - 1/3! + 1/4! - ... $$

La probabilità di un derangement è esattamente la somma troncata dopo il termine 1/n!.

Quindi, quando n cresce:

P(nessun punto fisso)
→
1/e
≈
36,787944%

La convergenza è molto rapida.

Per esempio:

n=4   -> 9/24        = 37,500000%
n=5   -> 44/120      = 36,666667%
n=6   -> 265/720     = 36,805556%
n=8   -> 14833/40320 = 36,788194%
n=10  -> 1334961/3628800
      ≈ 36,787946%

Già con dieci elementi la differenza rispetto a 1/e è di circa:

0,00000231 punti percentuali

La sorpresa è che la probabilità non tende a zero.

Anche con moltissimi elementi, una quota di circa il 36,8% delle permutazioni non lascia nessuno al proprio posto.

E se vogliamo esattamente k persone al proprio posto?

Il problema delle rencontres non si limita al caso 0.

Supponiamo di volere esattamente k punti fissi.

Prima scegliamo quali k elementi resteranno al proprio posto:

$$ \binom{n}{k} $$

Poi dobbiamo assicurarci che tutti gli altri n-k elementi non restino al proprio posto.

Quindi sui rimanenti serve un derangement:

$$ D_{n-k} $$

Il numero di permutazioni con esattamente k punti fissi è:

$$ N(n,k) = \binom{n}{k} D_{n-k} $$

Per n=6 otteniamo:

punti fissi 0 -> 265 permutazioni
punti fissi 1 -> 264
punti fissi 2 -> 135
punti fissi 3 -> 40
punti fissi 4 -> 15
punti fissi 5 -> 0
punti fissi 6 -> 1

La somma torna esattamente a:

265 + 264 + 135 + 40 + 15 + 0 + 1
=
720
=
6!

Il valore zero per cinque punti fissi non è un errore.

Se cinque elementi su sei sono già al proprio posto, il sesto elemento rimasto non può andare da nessun'altra parte: è costretto anch'esso a essere un punto fisso.

In media resta al proprio posto una persona

C'è un altro risultato molto semplice e sorprendente.

Chiamiamo I_i la variabile che vale:

1 se l'elemento i è un punto fisso
0 altrimenti

In una permutazione uniforme:

$$ P(I_i=1) = 1/n $$

Il numero totale di punti fissi è:

X
=
I_1 + I_2 + ... + I_n

Per linearità del valore atteso:

E[X]
=
n · 1/n
=
1

Quindi, per qualunque n >= 1, il numero medio di punti fissi è esattamente:

1

Non stiamo dicendo che “di solito ce n'è esattamente uno”. La distribuzione mostra infatti che possono essercene zero, uno, due o più.

E non abbiamo usato l'indipendenza: le variabili indicatrici dei punti fissi non sono indipendenti.

Calcoliamo D_n in C#

Lo standalone C# associato a questo articolo è:

DerangementsRencontres.cs

La formula con inclusione-esclusione è ottima per capire il problema. Per calcolare i valori interi possiamo usare anche la ricorrenza classica:

D_0 = 1
D_1 = 0

D_n
=
(n-1)(D_(n-1) + D_(n-2))

D_0 = 1 è una convenzione combinatoria naturale: esiste una sola permutazione dell'insieme vuoto, e non ha punti fissi.

In C#:

using System.Numerics;

static BigInteger Derangements(int n)
{
    if (n < 0)
        throw new ArgumentOutOfRangeException(nameof(n));

    if (n == 0)
        return BigInteger.One;

    if (n == 1)
        return BigInteger.Zero;

    BigInteger d0 = BigInteger.One;
    BigInteger d1 = BigInteger.Zero;

    for (int k = 2; k <= n; k++)
    {
        BigInteger d =
            (k - 1)
            *
            (d1 + d0);

        d0 = d1;
        d1 = d;
    }

    return d1;
}

Console.WriteLine(Derangements(6));
Console.WriteLine(Derangements(10));

L'output atteso è:

265
1334961

Per il numero di permutazioni con esattamente k punti fissi possiamo riutilizzare le combinazioni:

BigInteger conteggio =
    Combinazioni(n, k)
    *
    Derangements(n - k);

Verifichiamo enumerando tutte le permutazioni di sei elementi

Per n=6 l'intero spazio contiene soltanto:

720

permutazioni.

È quindi perfettamente praticabile generarle tutte e contare direttamente quanti punti fissi possiede ciascuna.

L'esempio standalone associato all'articolo esegue due calcoli indipendenti:

formula:
C(6,k) D_(6-k)

enumerazione:
genera tutte le 6! permutazioni
e conta le posizioni fisse

I due metodi devono produrre la stessa distribuzione:

0 -> 265
1 -> 264
2 -> 135
3 -> 40
4 -> 15
5 -> 0
6 -> 1

Questa è una verifica più forte di una simulazione Monte Carlo: per n=6 non stiamo campionando alcune permutazioni, le stiamo visitando tutte.

Il collegamento che riprenderemo più avanti

Abbiamo ottenuto una formula esatta per ogni n finito:

$$ P(X_n=k) = \binom{n}{k}D_{n-k} / n! $$

Per ora ci fermiamo qui.

La distribuzione di Poisson verrà introdotta più avanti, nell'articolo 34: non serve conoscerla per capire il calcolo corrente.

Nell'articolo 44 torneremo sulla stessa variabile X_n e chiederemo che cosa succede all'intera distribuzione quando n diventa grande. Scopriremo che il limite non riguarda soltanto il caso k=0: il numero di punti fissi converge verso una Poisson di parametro 1.

Il risultato 1/e incontrato qui sarà allora soltanto il caso:

P(Poisson(1)=0)
=
e^{-1}

Il punto pratico

Il problema delle rencontres mostra tre idee che torneranno più volte nella nuova parte della serie.

Una condizione apparentemente locale — “nessuno riceve il proprio elemento” — crea dipendenze globali nella permutazione, quindi non possiamo moltiplicare probabilità come se gli eventi fossero indipendenti.

L'inclusione-esclusione permette però di trasformare il vincolo in un conteggio esatto:

D_n
=
n!
sum(k=0..n)(-1)^k/k!

e da quel conteggio emerge un limite sorprendentemente stabile:

P(nessun punto fisso)
→
1/e
≈
36,8%

Nel prossimo articolo cambieremo completamente domanda: invece di contare una permutazione finale, misureremo quanto tempo bisogna aspettare per raccogliere tutti i risultati possibili. È il problema del coupon collector.