Dalle bische clandestine agli
algoritmi stocastici:
la vita e gli amori della signorina
Fortuna
Fabio Fagnani
Dipartimento di Matematica
Politecnico di Torino
– p.
Una lezione sulla probabilità
•
La genesi: una breve introduzione storica.
•
Gli strumenti della probabilità.
•
Alcuni errori comuni.
•
Alcune applicazioni più avanzate.
– p.
La genesi della probabilità
Nasce nelle bische clandestine della Francia
seicentesca.
Ha una data di nascita ufficiale: il 1654.
Un importante precursore:
Cardano, Liber de Ludo Aleae, 1520, pubblicato nel
1663.
– p.
Che cosa accadde nel 1654?
– p.
Che cosa accadde nel 1654?
Un gioco delle bische parigine:
La ‘casa’ scommette alla pari con un giocatore che
quest’ultimo, lanciando per 4 volte un dado, ottenga
almeno una volta 6.
Questo gioco è favorevole alla casa che ‘in media’ vince il 52%
delle volte.
– p.
Che cosa accadde nel 1654?
Un gioco delle bische parigine:
La ‘casa’ scommette alla pari con un giocatore che
quest’ultimo, lanciando per 4 volte un dado, ottenga
almeno una volta 6.
Questo gioco è favorevole alla casa che ‘in media’ vince il 52%
delle volte.
Una variante di Antoine Gombauld Chevalier de
Méré:
la ‘casa’ scommette alla pari con un giocatore che
quest’ultimo, lanciando per 24 volte una coppia di
dadi, ottenga almeno una volta il doppio 6.
– p.
Che cosa accadde nel 1654?
Anche questo gioco, secondo il de Méré, dovrebbe
essere leggermente favorevole alla casa:
– p.
Che cosa accadde nel 1654?
Anche questo gioco, secondo il de Méré, dovrebbe
essere leggermente favorevole alla casa:
•
6 risultati possibili lanciando un dado: la
probabilità che esca il 6 è 1/6;
– p.
Che cosa accadde nel 1654?
Anche questo gioco, secondo il de Méré, dovrebbe
essere leggermente favorevole alla casa:
•
•
6 risultati possibili lanciando un dado: la
probabilità che esca il 6 è 1/6;
36 risultati possibili lanciando due dadi: la
probabilità che esca il doppio 6 è 1/36 (6 volte
più bassa);
– p.
Che cosa accadde nel 1654?
Anche questo gioco, secondo il de Méré, dovrebbe
essere leggermente favorevole alla casa:
•
•
•
6 risultati possibili lanciando un dado: la
probabilità che esca il 6 è 1/6;
36 risultati possibili lanciando due dadi: la
probabilità che esca il doppio 6 è 1/36 (6 volte
più bassa);
lanciando la coppia di dadi 6 volte di più
(24 = 6 × 4) si dovrebbe controbilanciare
l’effetto di considerare un evento meno probabile
di un fattore 6.
– p.
Che cosa accadde nel 1654?
Anche questo gioco, secondo il de Méré, dovrebbe
essere leggermente favorevole alla casa:
•
•
•
•
6 risultati possibili lanciando un dado: la
probabilità che esca il 6 è 1/6;
36 risultati possibili lanciando due dadi: la
probabilità che esca il doppio 6 è 1/36 (6 volte
più bassa);
lanciando la coppia di dadi 6 volte di più
(24 = 6 × 4) si dovrebbe controbilanciare
l’effetto di considerare un evento meno probabile
di un fattore 6.
.... si dovrebbe avere quindi la stessa probabilità.
– p.
Che cosa accadde nel 1654?
E invece no! Quest’ultimo gioco non è favorevole alla
casa, ma al giocatore.
Ne era consapevole il de Méré, non è chiaro se per
averlo provato a sue spese o per qualche intuizione
teorica.
Decise di parlarne con un brillante francese
dell’epoca, Blaise Pascal che risolse il problema
postogli dal de Méré provando anche che con 25 lanci
il gioco sarebbe allora stato favorevole alla casa.
– p.
Lo sviluppo successivo
Con Pascal, Fermat, Huygens, Leibnitz, Bernoulli si
sviluppa la probabilità. Per la fine del 1600 è già una
teoria autonoma.
– p.
Lo sviluppo successivo
Con Pascal, Fermat, Huygens, Leibnitz, Bernoulli si
sviluppa la probabilità. Per la fine del 1600 è già una
teoria autonoma.
Altri fondamentali contributi: Laplace, Poisson, De
Moivre, Gauss
Laplace 1812: E davvero notevole che una scienza
nata dall’osservazione dei giochi d’azzardo sia
divenuta l’oggetto più importante della umana
conoscenza!
– p.
Lo sviluppo successivo
Con Pascal, Fermat, Huygens, Leibnitz, Bernoulli si
sviluppa la probabilità. Per la fine del 1600 è già una
teoria autonoma.
Altri fondamentali contributi: Laplace, Poisson, De
Moivre, Gauss
Laplace 1812: E davvero notevole che una scienza
nata dall’osservazione dei giochi d’azzardo sia
divenuta l’oggetto più importante della umana
conoscenza!
Poi, per oltre 100 anni, fino al 1930 la probabilità
quasi scompare dai circoli matematici.
– p.
Lo sviluppo successivo
Il XX secolo consacra definitivamente la probabilità:
• Le spettacolari applicazioni alla fisica di
Maxwell, Boltzmann, Einstein.
• Le nuove applicazioni alla genetica, informatica,
teoria delle comunicazioni, modelli finanziari.
• Status di disciplina matematica autonoma.
– p.
Lo sviluppo successivo
Il XX secolo consacra definitivamente la probabilità:
• Le spettacolari applicazioni alla fisica di
Maxwell, Boltzmann, Einstein.
• Le nuove applicazioni alla genetica, informatica,
teoria delle comunicazioni, modelli finanziari.
• Status di disciplina matematica autonoma.
Tuttavia, le idee probabilistiche penetrano
scarsamente nella cultura comune...
– p.
Quando serve la probabilità?
– p.
Quando serve la probabilità?
La probabilità interviene ogni volta che effettuiamo,
assistiamo ad un esperimento l’esito del quale non è
completamente determinato a priori e può avere un
certo numero di diversi risultati.
– p.
Quando serve la probabilità?
La probabilità interviene ogni volta che effettuiamo,
assistiamo ad un esperimento l’esito del quale non è
completamente determinato a priori e può avere un
certo numero di diversi risultati.
•
Lancio di una moneta: 2 possibili risultati T o C.
– p.
Quando serve la probabilità?
La probabilità interviene ogni volta che effettuiamo,
assistiamo ad un esperimento l’esito del quale non è
completamente determinato a priori e può avere un
certo numero di diversi risultati.
•
•
Lancio di una moneta: 2 possibili risultati T o C.
Lancio di un dado: 6 possibili risultati.
– p.
Quando serve la probabilità?
La probabilità interviene ogni volta che effettuiamo,
assistiamo ad un esperimento l’esito del quale non è
completamente determinato a priori e può avere un
certo numero di diversi risultati.
•
•
•
Lancio di una moneta: 2 possibili risultati T o C.
Lancio di un dado: 6 possibili risultati.
Estrazione di una pallina da un’urna contenente
palline rosse, bianche, nere e gialle: 4 possibili
risultati.
– p.
Quando serve la probabilità?
La probabilità interviene ogni volta che effettuiamo,
assistiamo ad un esperimento l’esito del quale non è
completamente determinato a priori e può avere un
certo numero di diversi risultati.
•
•
•
•
Lancio di una moneta: 2 possibili risultati T o C.
Lancio di un dado: 6 possibili risultati.
Estrazione di una pallina da un’urna contenente
palline rosse, bianche, nere e gialle: 4 possibili
risultati.
Numero di connessioni ad un server in un giorno.
– p.
Quando serve la probabilità?
La probabilità interviene ogni volta che effettuiamo,
assistiamo ad un esperimento l’esito del quale non è
completamente determinato a priori e può avere un
certo numero di diversi risultati.
Il modello probabilistico serve a descrivere la nostra
mancanza di informazione, la nostra ignoranza su un
fenomeno e prescinde dalla causa di tale ignoranza.
– p. 1
Il modello probabilistico
Si fissa un insieme che contenga come elementi i
possibili esiti dell’esperimento sotto considerazione.
Questo insieme verrà generalmente indicato con il
simbolo Ω e chiamato spazio degli eventi elementari.
– p. 1
Il modello probabilistico
Si fissa un insieme che contenga come elementi i
possibili esiti dell’esperimento sotto considerazione.
Questo insieme verrà generalmente indicato con il
simbolo Ω e chiamato spazio degli eventi elementari.
L’insieme Ω negli esempi precedenti:
•
Lancio di una moneta: Ω = {T, C}.
•
Lancio di un dado: Ω = {1, 2, 3, 4, 5, 6}.
•
Estrazione dall’urna: Ω = {R, B, N, G}.
Numero di connessioni:
Ω = N = {0, 1, 2, 3, . . . }.
•
– p. 1
Il modello probabilistico
Si fissa un insieme che contenga come elementi i
possibili esiti dell’esperimento sotto considerazione.
Questo insieme verrà generalmente indicato con il
simbolo Ω e chiamato spazio degli eventi elementari.
Ad ogni evento elementare ω ∈ Ω si associa un
numero p(ω): la probabilità che si verifichi ω.
X
p(ω) = 1
p(ω) ≥ 0
ω∈Ω
– p. 1
Il modello probabilistico
Come si sceglie la probabilità p(ω)?
– p. 1
Il modello probabilistico
Come si sceglie la probabilità p(ω)?
– Ipotesi frequentista. In base ad informazioni
statistiche sull’esperimento
Es.: se l’evento ω accade 37 volte su 100, si pone
p(ω) = 37/100.
– p. 1
Il modello probabilistico
Come si sceglie la probabilità p(ω)?
– Ipotesi frequentista. In base ad informazioni
statistiche sull’esperimento
Es.: se l’evento ω accade 37 volte su 100, si pone
p(ω) = 37/100.
– Ipotesi classica. Ragionamenti di simmetria: tutti
gli eventi elementari hanno la stessa probabilità.
Se Ω ha N elementi (|Ω| = N ), si pone p(ω) = 1/N qualunque
sia ω ∈ Ω.
– p. 1
Il modello probabilistico
Come si sceglie la probabilità p(ω)?
– p. 1
Il modello probabilistico
Come si sceglie la probabilità p(ω)?
Moneta Ω = {T, C}
p(T ) = p(C) = 1/2
– p. 1
Il modello probabilistico
Come si sceglie la probabilità p(ω)?
Dado Ω = {1, 2, 3, 4, 5, 6}
p(ω) = 1/6, ω = 1, 2, . . . , 6
– p. 1
Il modello probabilistico
Come si sceglie la probabilità p(ω)?
Connessioni Ω = N
p(ω) =?
ipotesi frequentista, ...
– p. 1
Il calcolo delle probabilità
(Ω, p(ω)) spazio delle probabilità.
– p. 1
Il calcolo delle probabilità
(Ω, p(ω)) spazio delle probabilità.
La probabilità di eventi complessi:
X
A⊆Ω
p(A) =
p(ω)
ω∈A
– p. 1
Il calcolo delle probabilità
(Ω, p(ω)) spazio delle probabilità.
Caso di ipotesi classica:
p(A) =
X
ω∈A
|A| casi favorevoli
=
p(ω) =
.
|Ω|
casi possibili
– p. 1
Il calcolo delle probabilità
(Ω, p(ω)) spazio delle probabilità.
Caso di ipotesi classica:
p(A) =
X
ω∈A
|A| casi favorevoli
=
p(ω) =
.
|Ω|
casi possibili
Urna Ω = {R, B, N, G}
– p. 1
Il calcolo delle probabilità
(Ω, p(ω)) spazio delle probabilità.
Caso di ipotesi classica:
p(A) =
X
ω∈A
|A| casi favorevoli
=
p(ω) =
.
|Ω|
casi possibili
Urna Ω = {R, B, N, G}
Composizione dell’urna: 3 palline rosse, 4 bianche, 1
nera, 2 gialle. Totale 10 palline.
– p. 1
Il calcolo delle probabilità
(Ω, p(ω)) spazio delle probabilità.
Caso di ipotesi classica:
p(A) =
X
ω∈A
|A| casi favorevoli
=
p(ω) =
.
|Ω|
casi possibili
Urna Ω = {R, B, N, G}
Composizione dell’urna: 3 palline rosse, 4 bianche, 1
nera, 2 gialle. Totale 10 palline.
3
4
1
2
p(R) = , p(B) = , p(N ) = , p(G) =
.
10
10
10
10
– p. 1
Il calcolo delle probabilità
(Ω, p(ω)) spazio delle probabilità.
Regola del complementare:
c
p(A ) = 1 − p(A)
– p. 1
Esperimenti ripetuti
Esperimento base con risultati nell’insieme Ωo .
Ripetiamo l’esperimento k volte e annotiamo in
ordine i risultati ottenuti.
– p. 1
Esperimenti ripetuti
Esperimento base con risultati nell’insieme Ωo .
Ripetiamo l’esperimento k volte e annotiamo in
ordine i risultati ottenuti.
Otteniamo una sequenza ordinata di k elementi di Ωo :
(ω1 , ω2 , . . . , ωk )
dove ωi indica l’esito dell’i-esimo esperimento.
– p. 1
Esperimenti ripetuti
Esperimento base con risultati nell’insieme Ωo .
Ripetiamo l’esperimento k volte e annotiamo in
ordine i risultati ottenuti.
Otteniamo una sequenza ordinata di k elementi di Ωo :
(ω1 , ω2 , . . . , ωk )
dove ωi indica l’esito dell’i-esimo esperimento.
NOTAZIONE:
Ω = Ωko = {(ω1 , ω2 , . . . , ωk ) | ω1 , . . . ωk ∈ Ωo }
|Ωo | = No ,
|Ωko | = Nok .
– p. 1
Esperimenti ripetuti
Che probabilità su Ωko ?
– p. 1
Esperimenti ripetuti
Che probabilità su Ωko ?
Se gli eventi in Ω0 sono equiprobabili e i vari
esperimenti sono tra loro indipendenti è logico optare
per l’ipotesi classica:
1
p(ω1 , . . . ωk ) = k
No
(No = |Ωo |)
– p. 1
Ritorno al 1654
Qual’è la probabilità che lanciando per 4 volte un
dado si ottenga almeno una volta 6?
– p. 1
Ritorno al 1654
Qual’è la probabilità che lanciando per 4 volte un
dado si ottenga almeno una volta 6?
Ω0 = {1, 2, . . . , 6} , Ω = Ω40 .
A = {(ω1 , ω2 , ω3 , ω4 ) | almeno un ωi = 6}
– p. 1
Ritorno al 1654
Qual’è la probabilità che lanciando per 4 volte un
dado si ottenga almeno una volta 6?
Ω0 = {1, 2, . . . , 6} , Ω = Ω40 .
A = {(ω1 , ω2 , ω3 , ω4 ) | almeno un ωi = 6}
Ac = {(ω1 , ω2 , ω3 , ω4 ) | ωi 6= 6}
– p. 1
Ritorno al 1654
Qual’è la probabilità che lanciando per 4 volte un
dado si ottenga almeno una volta 6?
Ω0 = {1, 2, . . . , 6} , Ω = Ω40 .
A = {(ω1 , ω2 , ω3 , ω4 ) | almeno un ωi = 6}
Ac = {(ω1 , ω2 , ω3 , ω4 ) | ωi 6= 6}
4
casi
favorevoli
5
= 4
p(Ac ) =
casi possibili
6
– p. 1
Ritorno al 1654
Qual’è la probabilità che lanciando per 4 volte un
dado si ottenga almeno una volta 6?
Ω0 = {1, 2, . . . , 6} , Ω = Ω40 .
A = {(ω1 , ω2 , ω3 , ω4 ) | almeno un ωi = 6}
Ac = {(ω1 , ω2 , ω3 , ω4 ) | ωi 6= 6}
4
casi
favorevoli
5
= 4
p(Ac ) =
casi possibili
6
4
5
p(A) = 1 − p(Ac ) = 1 − 4 ≃ 0.52
6
– p. 1
Ritorno al 1654
Qual’è la probabilità che lanciando per 24 volte una
coppia di dadi si ottenga almeno una volta (6, 6)?
– p. 1
Ritorno al 1654
Qual’è la probabilità che lanciando per 24 volte una
coppia di dadi si ottenga almeno una volta (6, 6)?
Ω0 = {1, 2, . . . , 6}2 , Ω = Ω24
0 .
A = {(ω1 , . . . , ω24 ) | almeno un ωi = (6, 6)}
– p. 1
Ritorno al 1654
Qual’è la probabilità che lanciando per 24 volte una
coppia di dadi si ottenga almeno una volta (6, 6)?
Ω0 = {1, 2, . . . , 6}2 , Ω = Ω24
0 .
A = {(ω1 , . . . , ω24 ) | almeno un ωi = (6, 6)}
Ac = {(ω1 , . . . , ω24 ) | ωi 6= (6, 6)}
– p. 1
Ritorno al 1654
Qual’è la probabilità che lanciando per 24 volte una
coppia di dadi si ottenga almeno una volta (6, 6)?
Ω0 = {1, 2, . . . , 6}2 , Ω = Ω24
0 .
A = {(ω1 , . . . , ω24 ) | almeno un ωi = (6, 6)}
Ac = {(ω1 , . . . , ω24 ) | ωi 6= (6, 6)}
24
35
casi
favorevoli
= 24
p(Ac ) =
casi possibili
36
– p. 1
Ritorno al 1654
Qual’è la probabilità che lanciando per 24 volte una
coppia di dadi si ottenga almeno una volta (6, 6)?
Ω0 = {1, 2, . . . , 6}2 , Ω = Ω24
0 .
A = {(ω1 , . . . , ω24 ) | almeno un ωi = (6, 6)}
Ac = {(ω1 , . . . , ω24 ) | ωi 6= (6, 6)}
24
35
casi
favorevoli
= 24
p(Ac ) =
casi possibili
36
24
35
p(A) = 1 − p(Ac ) = 1 − 24 ≃ 0.49
36
– p. 1
L’errore del De Méré.
Era così sbagliato il ragionamento del De Méré?
– p. 2
L’errore del De Méré.
Era così sbagliato il ragionamento del De Méré?
In entrambi i casi si sta aspettando l’accadimento di
un certo evento ω che ha probabilità p(ω) = p e si
ripete l’esperimento k volte.
– p. 2
L’errore del De Méré.
Era così sbagliato il ragionamento del De Méré?
In entrambi i casi si sta aspettando l’accadimento di
un certo evento ω che ha probabilità p(ω) = p e si
ripete l’esperimento k volte.
primo caso: ω = 6, p = 1/6, k = 4.
p(non accade mai ω) =
54
64
= 1−
1 4
6
– p. 2
L’errore del De Méré.
Era così sbagliato il ragionamento del De Méré?
In entrambi i casi si sta aspettando l’accadimento di
un certo evento ω che ha probabilità p(ω) = p e si
ripete l’esperimento k volte.
primo caso: ω = 6, p = 1/6, k = 4.
p(non accade mai ω) =
54
64
= 1−
1 4
6
secondo caso: ω = (6, 6), p = 1/36, k = 24.
3524
1 24
p(non accade mai ω) = 3624 = 1 − 36
– p. 2
L’errore del De Méré.
Era così sbagliato il ragionamento del De Méré?
In entrambi i casi si sta aspettando l’accadimento di
un certo evento ω che ha probabilità p(ω) = p e si
ripete l’esperimento k volte.
primo caso: ω = 6, p = 1/6, k = 4.
p(non accade mai ω) =
54
64
= 1−
1 4
=
6
(1 − p)k
secondo caso: ω = (6, 6), p = 1/36, k = 24.
3524
1 24
p(non accade mai ω) = 3624 = 1 − 36 = (1 − p)k
– p. 2
L’errore del De Méré.
Era così sbagliato il ragionamento del De Méré?
In entrambi i casi si sta aspettando l’accadimento di
un certo evento ω che ha probabilità p(ω) = p e si
ripete l’esperimento k volte.
p(non accade mai ω) = (1 − p)k
– p. 2
L’errore del De Méré.
Era così sbagliato il ragionamento del De Méré?
In entrambi i casi si sta aspettando l’accadimento di
un certo evento ω che ha probabilità p(ω) = p e si
ripete l’esperimento k volte.
p(non accade mai ω) = (1 − p)k
Per la regola del complementare,
p(accade almeno una volta ω) = 1 − (1 − p)k
– p. 2
L’errore del De Méré.
Consideriamo f (p) = (1 − p)k
1
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
– p. 2
L’errore del De Méré.
Consideriamo f (p) = (1 − p)k
La retta tangente in (0, f (0)) è: y = 1 − kp.
1
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
0.8
1
– p. 2
L’errore del De Méré.
Consideriamo f (p) = (1 − p)k
La retta tangente in (0, f (0)) è: y = 1 − kp.
1
0.8
0.6
0.4
0.2
0
0
(1 − p)k ≃ 1 − kp
0.2
0.4
0.6
0.8
1
per p piccoli
– p. 2
L’errore del De Méré.
p(accade almeno una volta ω) = 1 − (1 − p)k
– p. 2
L’errore del De Méré.
p(accade almeno una volta ω) = 1 − (1 − p)k
≃ 1 − (1 − pk)
– p. 2
L’errore del De Méré.
p(accade almeno una volta ω) = 1 − (1 − p)k
≃ 1 − (1 − pk)
≃ pk
– p. 2
L’errore del De Méré.
p(accade almeno una volta ω) = 1 − (1 − p)k
≃ 1 − (1 − pk)
≃ pk
Negli esempi:
p = 1/6 , k = 4
p = 1/36 , k = 24
4/6 = 24/36
– p. 2
L’errore del De Méré.
p(accade almeno una volta ω) = 1 − (1 − p)k
≃ 1 − (1 − pk)
≃ pk
Negli esempi:
p = 1/6 , k = 4
p = 1/36 , k = 24
4/6 = 24/36
Sono eguali nell’approssimazione!
...De Méré non aveva sbagliato poi di tanto.
– p. 2
Allarghiamo lo sguardo.
Un esperimento ripetuto k volte. L’evento ω ha
probabilità p (piccola) di accadere.
p(accade almeno una volta ω) = 1 − (1 − p)k ≃ pk
– p. 2
Allarghiamo lo sguardo.
Un esperimento ripetuto k volte. L’evento ω ha
probabilità p (piccola) di accadere.
p(accade almeno una volta ω) = 1 − (1 − p)k ≃ pk
Se k è sufficientemente grande (dell’ordine di 1/p),
questa probabilità sarà significativa.
– p. 2
Allarghiamo lo sguardo.
Un esperimento ripetuto k volte. L’evento ω ha
probabilità p (piccola) di accadere.
p(accade almeno una volta ω) = 1 − (1 − p)k ≃ pk
Se k è sufficientemente grande (dell’ordine di 1/p),
questa probabilità sarà significativa.
Prima o poi anche gli eventi improbabili accadono.
CASO + TEMPO ⇒ QUALUNQUE COSA
– p. 2
Un grave errore.
La probabilità che esca il 53 nella ruota di Venezia è
1
5
=
p=
90 18
Quindi in 18 estrazioni c’è buona probabilità che esca.
– p. 2
Un grave errore.
La probabilità che esca il 53 nella ruota di Venezia è
1
5
=
p=
90 18
Quindi in 18 estrazioni c’è buona probabilità che esca.
Supponiamo che il 53 non esca per 17 estrazioni.
Possiamo dedurne che a questo punto la sua
probabilità di uscita è più alta?
– p. 2
Un grave errore.
La probabilità che esca il 53 nella ruota di Venezia è
1
5
=
p=
90 18
Quindi in 18 estrazioni c’è buona probabilità che esca.
Supponiamo che il 53 non esca per 17 estrazioni.
Possiamo dedurne che a questo punto la sua
probabilità di uscita è più alta?
Assolutamente no! Le estrazioni non hanno memoria.
Ogni volta si ricomincia da capo!
– p. 2
Un grave errore.
Il 53 non è uscito nella ruota di Venezia per 182
estrazioni.
– p. 2
Un grave errore.
Il 53 non è uscito nella ruota di Venezia per 182
estrazioni.
La probabilità che in 182 estrazioni questo accada è
182
5
1
=
p= 1−
18
164764
– p. 2
Un grave errore.
Il 53 non è uscito nella ruota di Venezia per 182
estrazioni.
La probabilità che in 182 estrazioni questo accada è
182
5
1
=
p= 1−
18
164764
Un’approssimazione: la probabilità che in 182
estrazioni ci sia un numero che non esce mai è circa
90 · p ≃ 1/400.
– p. 2
Un grave errore.
Il 53 non è uscito nella ruota di Venezia per 182
estrazioni.
La probabilità che in 182 estrazioni questo accada è
182
5
1
=
p= 1−
18
164764
Un’approssimazione: la probabilità che in 182
estrazioni ci sia un numero che non esce mai è circa
90 · p ≃ 1/400.
Quindi, ripetendo l’esperimento per circa 400 volte, è
probabile che capiti.
– p. 2
Un grave errore.
In altre parole, in 400 × 182 = 72800 estrazioni, è
altamente probabile che ci sia l’assenza di un numero
per 182 estrazioni consecutive.
– p. 2
Un grave errore.
In altre parole, in 400 × 182 = 72800 estrazioni, è
altamente probabile che ci sia l’assenza di un numero
per 182 estrazioni consecutive.
Se si considerano le estrazioni fatte in Italia in oltre
130 anni di lotto, si vede che ci si va abbastanza vicini.
– p. 2
Dal sito www.giocodellotto.com:
...come tutti i grandi giochi, il Lotto ha molte anime: se è vero,
infatti, che è semplicissimo fare una giocata, è altrettanto vero
che le possibilità di gioco sono moltissime: approfondendo la
conoscenza del Gioco del Lotto si entra in un mondo complesso,
affascinante, dalle mille sfumature.
... Come negli Scacchi o nei giochi di strategia, insomma, le
regole necessarie per iniziare sono poche e alla portata di tutti,
ma le possibili evoluzioni, le tecniche, le filosofie, le meccaniche
avanzate sono innumerevoli.
– p. 2
Il caso può generare qualunque cosa.
Il prezzo sono i tempi necessari.
E’ davvero sempre così?
– p. 2
L’appuntamento
100 persone (agenti) sono sparse in un territorio e si
vogliono incontrare (rendez-vous). Ciascuno ha a
disposizione
• un GPS,
• un cellulare,
• la lista dei numeri telefonici degli altri.
Quale è la strategia per incontrarsi tutti il più
velocemente possibile?
– p. 2
L’appuntamento: strategia I
Agenti etichettati con un numero i = 1, 2, . . . , 100.
(xi , yi ) posizione dell’agente i al tempo iniziale.
•
•
Ciascuno spedisce la propria posizione a tutti gli
altri.
Ciascuno media la propria posizione con quelle
di tutti gli altri:
1
xA = 100
(x1 + x2 + · · · + x100 )
1
yA = 100
(y1 + y2 + · · · + y100 )
•
Ciascuno si muove verso la posizione (xA , yA ).
– p. 3
L’appuntamento: strategia I
Vantaggi:
•
•
Il punto d’incontro (baricentro) è quello che
rende minimo gli spostamenti globali.
In un solo colpo si arriva al ’rendez-vous’.
Svantaggi:
•
•
99 trasmissioni ciascuno per un totale di 9900
trasmissioni.
100 operazioni ciascuno per un totale di 10000
operazioni.
La complessità di calcolo e di trasmissione cresce
quadraticamente nel numero degli agenti!
– p. 3
L’appuntamento: strategia II
(xi , yi ) posizione dell’agente i al tempo iniziale.
1. L’agente i spedisce la propria posizione
all’agente i + 1 (100 la spedisce ad 1).
2. L’agente i media la propria posizione con quella
che ha ricevuto da i − 1:
1
=
x+
i
2 (xi + xi−1 )
yi+ = 12 (yi + yi−1 )
+
,
y
3. L’agente i si muove in (x+
i
i ).
4. GOTO 1.
Si ipotizza che gli agenti siano sincronizzati.
– p. 3
L’appuntamento: strategia II
(xi (t), yi (t)) posizione dell’agente i dopo t iterazioni.
Vantaggi:
• (xi (t), yi (t)) converge a (xA , yA ).
• In ogni iterazione ci sono solo 100 trasmissioni e
200 operazioni complessive.
Svantaggi:
• Velocità di convergenza
– p. 3
Strategia II: l’analisi teorica
Una misura di distanza dal ’rendez-vous’
∆(t) =
100
X
[(xi (t) − xA )2 + (yi (t) − yA )2 ] .
i=1
Fattore di contrazione: (∆(t + 1) ≤ ρ∆(t))
2π
ρ = 12 + 12 cos 100
≃ 0.999.
– p. 3
Strategia II: l’analisi teorica
Una misura di distanza dal ’rendez-vous’
∆(t) =
100
X
[(xi (t) − xA )2 + (yi (t) − yA )2 ] .
i=1
Fattore di contrazione: (∆(t + 1) ≤ ρ∆(t))
2π
ρ = 12 + 12 cos 100
≃ 0.999.
Tempo di dimezzamento: (∆(τ ) ≤ 1/2∆(0))
log 2
τ = − log ρ ≃ 690,
– p. 3
Strategia II: l’analisi teorica
Una misura di distanza dal ’rendez-vous’
∆(t) =
100
X
[(xi (t) − xA )2 + (yi (t) − yA )2 ] .
i=1
Fattore di contrazione: (∆(t + 1) ≤ ρ∆(t))
2π
ρ = 12 + 12 cos 100
≃ 0.999.
Tempo di dimezzamento: (∆(τ ) ≤ 1/2∆(0))
log 2
τ = − log ρ ≃ 690,
Numero trasmissioni: 690 × 100 = 69000!
– p. 3
Strategia II: l’analisi teorica
Il caso generale 100 → N :
Fattore di contrazione: ρ =
1
2
1
2
+ cos
Tempo di dimezzamento: τ =
log 2
− log ρ
2π
N
≃1−
π2
N2 .
≃ CN 2 ,
Numero trasmissioni: τ × N = CN 3 !!
La complessità di calcolo e di trasmissione cresce con
il cubo del numero degli agenti!
– p. 3
L’appuntamento: una variante
L’architettura di comunicazione toroidale:
ρ≃1−
C
N,
τ ≃ N,
Numero trasmissioni: ≃ N 2 .
– p. 3
L’appuntamento: strategia III
1. L’agente i sceglie a caso, dalla lista, un agente j e
gli spedisce la propria posizione.
2. L’agente j media la propria posizione con quella
che ha ricevuto da i:
1
=
x+
j
2 (xj + xi )
yj+ = 12 (yj + yi )
+
3. L’agente j si muove in (x+
,
y
j
j ).
1. GOTO 1.
Si ipotizza che gli agenti siano sincronizzati.
– p. 3
L’appuntamento: strategia III
Ecco come si comporta:
gossip
gossip
Vantaggi:
• In ogni iterazione ci sono solo 100 trasmissioni e
300 operazioni complessive.
• E’ veloce: ρ ≃ 1/2 (indipendentemente dal
numero di agenti)!
Svantaggi:
• Non converge a (xA , yA ).
– p. 3
Confronto quantitativo
Completo : ρ = 0
τ =1
Trasmiss. ≃ N 2
Ciclo :
ρ≃1−
C
N2
τ ≃ N 2 Trasmiss. ≃ N 3
Toro :
ρ≃1−
C
N
τ ≃N
Trasmiss. ≃ N 2
Gossip :
ρ≃
τ =1
Trasmiss. ≃ N
1
2
– p. 3
Confronto quantitativo
Completo : ρ = 0
τ =1
Trasmiss. ≃ N 2
Ciclo :
ρ≃1−
C
N2
τ ≃ N 2 Trasmiss. ≃ N 3
Toro :
ρ≃1−
C
N
τ ≃N
Trasmiss. ≃ N 2
Gossip :
ρ≃
τ =1
Trasmiss. ≃ N
1
2
Gossip:
Distanza dal baricentro: ≃
1
N2 !
– p. 3
Ma è un vero problema?
– p. 4
Ma è un vero problema?
Multi-vehicle system: Gli agenti sono robot che si
devono incontrare in un punto, coordinandosi tra loro,
senza un leader, senza un supervisore.
– p. 4
Ma è un vero problema?
Multi-vehicle system: Gli agenti sono robot che si
devono incontrare in un punto, coordinandosi tra loro,
senza un leader, senza un supervisore.
Computer network: Gli agenti sono
processori/computer che si scambiano lavori da
eseguire in modo da equilibrare le code e
massimizzare le prestazioni.
– p. 4
Ma è un vero problema?
Multi-vehicle system: Gli agenti sono robot che si
devono incontrare in un punto, coordinandosi tra loro,
senza un leader, senza un supervisore.
Computer network: Gli agenti sono
processori/computer che si scambiano lavori da
eseguire in modo da equilibrare le code e
massimizzare le prestazioni.
Sensor network: Gli agenti sono sensori buttati a caso
in una zona e devono mediare le misure che hanno
fatto per aggregare i dati e filtrare il rumore
– p. 4
Ma è un vero problema?
Controllo coordinato di un ’multi-vehicle system’.
– p. 4
Ma è un vero problema?
Controllo coordinato di un ’multi-vehicle system’.
•
Molti agenti (robot)
– p. 4
Ma è un vero problema?
Controllo coordinato di un ’multi-vehicle system’.
•
•
Molti agenti (robot)
Obbiettivo comune: incontro, muoversi con la
stessa velocità, ...
– p. 4
Ma è un vero problema?
Controllo coordinato di un ’multi-vehicle system’.
•
•
•
Molti agenti (robot)
Obbiettivo comune: incontro, muoversi con la
stessa velocità, ...
Comunicazioni ridotte
– p. 4
Ma è un vero problema?
Controllo coordinato di un ’multi-vehicle system’.
•
•
•
•
Molti agenti (robot)
Obbiettivo comune: incontro, muoversi con la
stessa velocità, ...
Comunicazioni ridotte
Mancanza di un leader nel gruppo.
– p. 4
Ma è un vero problema?
Controllo coordinato di un ’multi-vehicle system’.
•
•
•
•
Molti agenti (robot)
Obbiettivo comune: incontro, muoversi con la
stessa velocità, ...
Comunicazioni ridotte
Mancanza di un leader nel gruppo.
Si cerca di riprodurre fenomeni presenti nel
comportamento degli animali in gruppo.
– p. 4
I comportamenti coordinati
– p. 4
I comportamenti coordinati
– p. 4
I comportamenti coordinati
– p. 4
I comportamenti coordinati
– p. 4
I comportamenti coordinati
– p. 4
Il gruppo di ricerca
•
Giacomo Como, Paolo Frasca, Federica Garin,
Valentina Martina, Chiara Ravazzi
(Laurea e Dottorato Ingegneria Matematica PoliTO)
•
Sophie Fosson (Perfezionamento SNS)
Gli argomenti di ricerca:
• Algoritmi stocastici gossip, controllo coordinato.
• Teoria dell’informazione, teoria dei codici.
[email protected]
http://calvino.polito.it/∼fagnani/
– p. 4