Esercizio - aggiornamenti del massimo corrente in una scansione (record)

Teoria: Linearità del valore atteso e variabili indicatrici (record).

Testo. Il codice seguente cerca il massimo di un array a di $n$ numeri distinti, dati in ordine casuale (ogni ordine con probabilità $1/n!$ ), e conta quante volte l'assegnazione m = x viene eseguita.

python

a = [5, 2, 8, 1, 9, 3]                 # un ordine possibile
m, aggiornamenti = float("-inf"), 0
for x in a:
    if x > m:
        m = x
        aggiornamenti += 1
print(m, aggiornamenti)                # 9 3 (aggiorna con 5, 8, 9)

Calcolare il valore atteso del numero di aggiornamenti $R$ per $n=3$ elencando tutti gli ordini.
Calcolarlo per $n$ generico con le variabili indicatrici, e poi per $n=10$ e $n=1000$ .
Qual è la probabilità che l'ultimo elemento causi un aggiornamento? E che gli aggiornamenti siano $n$ ?
Verificare con una simulazione.

Soluzione

1. Enumerazione ( $n=3$ ). Gli ordini di $\{1,2,3\}$ sono $6$ e gli aggiornamenti sono:

$123$ : aggiorna a $1,2,3$ ( $3$ );
$132$ : $1,3$ ( $2$ );
$213$ : $2,3$ ( $2$ );
$231$ : $2,3$ ( $2$ );
$312$ : solo $3$ ( $1$ );
$321$ : solo $3$ ( $1$ ).

Somma $3+2+2+2+1+1=11$ , media $\frac{11}6\approx1{,}833$ .

2. Indicatrici. L'elemento in posizione $i$ provoca un aggiornamento (è un record) se è il massimo dei primi $i$ elementi. I primi $i$ elementi sono in ordine casuale e il massimo di essi può trovarsi in ciascuna delle $i$ posizioni con la stessa probabilità $\frac1i$ (simmetria), quindi $P(I_i=1)=\frac1i$ . Per linearità $E[R]=\sum_{i=1}^n\frac1i=H_n.$ Per $n=3$ : $1+\frac12+\frac13=\frac{11}6$ , in accordo con l'enumerazione. Per $n=10$ : $H_{10}=\frac{7381}{2520}\approx2{,}929$ . Per $n=1000$ : $H_{1000}\approx\ln1000+0{,}5772+\frac1{2000}=6{,}9078+0{,}5772+0{,}0005=7{,}4855$ . Il massimo viene riassegnato meno di $8$ volte su mille elementi.

3. Casi particolari. L'ultimo elemento è un record se è il massimo di tutti: probabilità $\frac1n$ . Tutti gli elementi sono record solo nell'ordine crescente, che ha probabilità $\frac1{n!}$ (per $n=3$ : $\frac16$ , il solo caso $123$ ).

4. Simulazione.

python

import random
n, T, tot = 10, 100000, 0
for _ in range(T):
    p = random.sample(range(n), n); m = -1
    for x in p:
        if x > m: m = x; tot += 1
print(tot / T)    # circa 2.93

Risultato. $E[R]=H_n$ : $\frac{11}6$ per $n=3$ , $2{,}929$ per $n=10$ , $7{,}486$ per $n=1000$ ; $P(\text{ultimo è record})=\frac1n$ .

Verifica Python: enumerazione esatta per $n=3,4,6$ ( $\frac{11}6,\frac{25}{12},\frac{49}{20}$ , uguali a $H_n$ ); simulazione $n=10$ .

Versione ripasso

Aggiornamento in posizione $i$ $\iff$ l'elemento $i$ è il massimo dei primi $i$ : probabilità $\frac1i$ per simmetria; la linearità non richiede indipendenza (Linearità del valore atteso e variabili indicatrici).
$E[R]=\sum_{i=1}^n\frac1i=H_n$ . $n=3$ : enumerazione $3,2,2,2,1,1$ , media $\frac{11}6$ . $n=10$ : $\frac{7381}{2520}\approx2{,}929$ . $n=1000$ : $\ln1000+0{,}5772+\frac1{2000}\approx7{,}486$ .
$P(\text{ultimo è record})=\frac1n$ ; $P(R=n)=\frac1{n!}$ (solo ordine crescente).
Verifica: enumerazione $n=3,4,6$ e simulazione $\approx2{,}93$ .
Errore tipico: scrivere $E[R]\approx n/2$ o $\log_2 n$ (è $\ln n$ , a meno di una costante).

Teoria collegata

Linearità del valore atteso e variabili indicatrici