L'ameba

[Dani Ferrari]

Spreco volentieri qualche fiume di parole in più, perché si tratta di un concetto fondamentale in matematica ricreativa, e lo devi capire bene. Sia $x$ la probabilità di estinzione di un'ameba. Ora dico: so che tra un minuto l'ameba passerà a un nuovo stato. Io mi riferisco a tale nuovo stato, e calcolo le probabilità di estinzione. Poiché all'ameba possono essere successe con uguale probabilità quattro cose, la prob. di estinzione sarà la media di questi 4 casi.
Se l'ameba è morta, la sua prob. di morire è 1. Se è rimasta invariata, la prob. è $x$. Se si è scissa in due, dato che le due amebe e le loro discendenze si evolvono indipendentemente, ognuna ha prob. $x$ di estinguersi, e la prob. che si estinguano entrambe è $x^2$. E analogamente, se si è scissa in 3, la sua prob, di estinzione è $x^3$. Ho detto che dobbiamo prendere la media di queste 4 prob., 1, $x$, $x^2$, $x^3$, quindi le sommiamo e dividiamo per 4. Abbiamo così una bella formulina che ci esprime la prob. cercata ragionando sulla situazione dopo la prima trasformazione. Ma all'inizio ho detto che la prob. di estinzione è $x$; e mica è cambiata se ragiono su un minuto dopo. Quindi questa formulina è uguale a $x$. Ecco così che hai l'equazione scritta da Gianfranco.

Dani

[Dani Ferrari]

Ho detto che questo procedimento è fondamentale in matematica ricreativa. Cerchiamo allora di caprine meglio la sostanza. Abbiamo un sistema che può passare attraverso una molteplicità di stati. Conosciamo perfettamente le regole di passaggio da uno stato ai successivi. Dobbiamo calcolare il valore di una certa grandezza in un certo stato. Possiamo esprimere questa grandezza in funzione dei valori che essa assumerà negli stati successivi. Avete visto come abbiamo utilizzato questo principio qui; ma... Non vi fa venire in mente nulla? Ripensate a "Corri corri topolino". Il principio di soluzione, coi debiti adattamenti, è lo stesso. Vi darò altri problemi con lo stesso principio.

Dani

[Pasquale]

Chiaro il ragionamento Dani, grazie; tuttavia avrei ancora una domanda:

poniamo che all'inizio le amebe siano 3 e che ognuna evolva, come prima, in uno dei 4 stati citati; la probabilità di estinzione quale sarebbe?

[Dani Ferrari]

L'ho scritto sopra, Pasquale: le 3 discendenze si evolvono indipendentemente, ognuna ha prob. $x$ di estinguersi, la prob. che si estinguano tutte e tre è $x^3$.

Dani

[Gianfranco]

Allora Dani, eccomi qui, con un po' di ritardo perche ero impegnato con gli esami scolastici.
Vedo che ci sono state varie risposte che hanno spiegato i dettagli della soluzione, in particolare quelle di Pietro e di Dani.
Premetto che ci ho dovuto lavorare un po' su perché non sapevo praticamente nulla sui processi di diramazione e affini, perciò ho pasticciato per alcune ore ma mi sono divertito.
Ecco, in sintesi il mio processo di lavorazione.

1) Mi è servito molto fare un programmino di simulazione perché ho dovuto creare una funzione di generazione G(n) che:
a) riceve in INPUT n (numero di individui, che all'inizio è 1)
b) calcola una generazione casuale
c) restituisce G(n) che è il numero di individui della generazione successiva.
Il programmino non è altro che una chiamata ricorsiva di questa funzione per un certo numero di volte:
G(G(G(G(G(n)))))

2) Poi ho riempito alcuni fogli di grafi ad albero dai quali ho capito che:
(indico: $E(n)$ = probabilità di estinzione alla generazione $n$; $p=\frac{1}{4}$).
$E(1) = p$

$E(2) = {p}^{4}+{p}^{3}+{p}^{2}+p$

$E(3) = p\,{\left( {p}^{4}+{p}^{3}+{p}^{2}+p\right) }^{3}+p\,{\left( {p}^{4}+{p}^{3}+{p}^{2}+p\right) }^{2}+p\,\left( {p}^{4}+{p}^{3}+{p}^{2}+p\right) +p$

3) Risulta evidente (?) che $E(n)$ è una funzione ricorsiva che si può definire così:

${E}\left( n\right) ={p\cdot\[{E}\left( n-1\right) }\]^{3}+{p\cdot\[{E}\left( n-1\right) }\]^{2}+ p\cdot{E}\left( n-1\right)+p$

Questa è la probability generating function

4) A questo punto mi sono bloccato e ho dovuto studiare un po' di teoria.
Ho trovato il seguente teorema:
The probability of eventual extinction of a branching process is the smallest root in [0,1] of E(x)=x, where E is the probability generating function.

Allora, sostituendo i valori del nostro problema:

$E(i) = x$
$p=\frac{1}{4}$

ho ottenuto l'equazione:

$x=\frac{{x}^{3}}{4}+\frac{{x}^{2}}{4}+\frac{x}{4}+\frac{1}{4}$

che ha le seguenti soluzioni:
$[x=-\sqrt{2}-1,x=\sqrt{2}-1,x=1]$

La soluzione buona è questa:
$x=\sqrt{2}-1$

Mi sembra giusto dire che wxMaxima (http://andrejv.github.io/wxmaxima/) mi ha aiutato molto.

[Pasquale]

Si d'accordo, volevo dire: l'equazione risolutrice resta la stessa o $x= x^3$ ?

[Gianfranco]

Pasquale, non ho capito la tua domanda. Ma forse non era per me...

[Gianfranco]

Caso 1) Supponiamo che una popolazione formata inizialmente da 1 individuo, abbia la probabilità x di estinguersi.

Caso 2) Se invece si parte con n individui, qual è la probabilità di estinzione?

E' come se avessimo n popolazioni indipendenti come quella del caso 1).
Per avere l'estinzione coompleta, dovrebbero estinguersi tutte.
Perciò la probabilità P di estinzione è:
$P = x^n$

[Dani Ferrari]

Giancarlo, ormai avrai capito, da quanto abbiamo scritto io e Pietro, che non c'era alcun bisogno di dedurre faticosamente quell'equazione: la si scriveva direttamente. Ma perché seguite sempre le strade più difficili? Partite subito con un Montecarlo. Salvo rari casi particolari, il Montecarlo si usa quando uno è proprio nella *beep* e non sa dove battere la testa: avere un'idea di dove si deve andare a parare non è un grande aiuto. Anche il Panurgo ha risolto il problema, per fortuna non ci ha detto come: ha detto solo che secondo lui non è roba da matematica del liceo. Be', è da matematica del liceo. Ah, risolvere l'equazione di 3^ grado: io l'ho risolta numericamente, per tentativi (metodo delle corde, se volete essere scientifici - ma io non ho fatto interpolazioni, sono andato a naso). Più o meno, con la mini-calcolatrice dell'Ipad, trovavo una cifra al minuto. E solo quando sono arrivato alla 6^ cifra (io sono un po' tardo...) mi sono accorto che stavo scrivendo la parte frazionaria della radice di 2.


Dani

[Gianfranco]

Ciao Dani,
ti ringrazio per aver proposto questo problema, mi ha permesso di imparare qualcosa che non sapevo e ci ho lavorato con piacere. Dopo aver letto l'approccio di Enrico e la risposta di Panurgo, ho preferito non visitare questo post proprio per non farmi influenzare da scritti di altre persone.
Provo a rispondere alle tue domande perché mi sembrano importanti per una migliore comprensione.

Giancarlo, ormai avrai capito, da quanto abbiamo scritto io e Pietro, che non c'era alcun bisogno di dedurre faticosamente quell'equazione: la si scriveva direttamente.

Mi piacciono quei problemi che mi permettono di scoprire qualcosa di nuovo (per me), di sviluppare un po' di teoria matematica, di fare qualche generalizzazione e di collegare questi sviluppi con quello che so già. Risolvere un problema è come raggiungere una meta, ma in certi casi il viaggio è più interessante della meta.

Ma perché seguite sempre le strade più difficili? Partite subito con un Montecarlo. Salvo rari casi particolari, il Montecarlo si usa quando uno è proprio nella *beep* e non sa dove battere la testa: avere un'idea di dove si deve andare a parare non è un grande aiuto.

Perché mi piace scrivere programmini per computer. In questo caso, comunque, scrivere il programmino mi ha aiutato a comprendere meglio la natura ricorsiva dei problemi di questo tipo.

Anche il Panurgo ha risolto il problema, per fortuna non ci ha detto come: ha detto solo che secondo lui non è roba da matematica del liceo.

Sono d'accordo che per fortuna non ci ha detto come. Così ho avuto più tempo per lavorarci su. Io, quando ho fatto il liceo scientifico (tanti anni fa) queste cose non me le sognavo nemmeno. Ma magari oggi le cose sono cambiate.

Be', è da matematica del liceo. Ah, risolvere l'equazione di 3^ grado: io l'ho risolta numericamente, per tentativi (metodo delle corde, se volete essere scientifici - ma io non ho fatto interpolazioni, sono andato a naso). Più o meno, con la mini-calcolatrice dell'Ipad, trovavo una cifra al minuto. E solo quando sono arrivato alla 6^ cifra (io sono un po' tardo...) mi sono accorto che stavo scrivendo la parte frazionaria della radice di 2.

Vedi che un po' di computer lo hai usato anche tu? Come è giusto che sia.

[Pasquale]

Per me che sono duro di comprendonio, resta il dubbio:

se partiamo con 1 ameba, l'equazione che abbiamo visto determina il relativo risultato, ma se ipotizziamo che fra le varie possibilità si verifica che l'ameba si triplica e studiamo a posteriori questo risultato, abbiamo un'equazione diversa, se ho capito bene, con un risultato diverso, e così procedendo, se ancora ipotizziamo che le tre amebe ancora si triplicano. ?

[Dani Ferrari]

Poiché lo sviluppo della discendenza di un'ameba è indipendente dalle altre, che io abbia un'ameba, 3 o 50 studio il caso elementare, l'estinzione di un'ameba. e ne deduco quella di 3 o 50. Ma tu, se capisco bene, dici: e se voglio studiare direttamente 3 amebe? In questo caso, chiamerei sempre $x$ la prob. di estinzione di un'ameba, e quindi $x^3$ la prob. di estinzione di 3 amebe; eguaglierei questo alla media delle prob. di estinzione della popolazione risultante, che però va da 0 a 9 amebe, con prob. diverse fra i vari numeri; troverei così un'equazione di 9° grado, che risolta dovrebbe darmi la stessa soluzione di prima. Io certo a fare una pazzia simile non ci provo, ma se tu vuoi provarci...

Dani

[Gianfranco]

Ciao Pasquale e Dani,
concordo con quanto detto da Dani e aggiungo alcune considerazioni e lo schema che avevo disegnato.
Nella figura, con p indico la probabilità di morire o scindersi in 1, 2, 3 amebe.
Le frecce tratteggiate indicano le successive espansioni non disegnate nel grafico.
In questo caso le probabilità sono tutte uguali a 1/4 ma in generale potrebbero essere anche diverse fra di loro.

ameba.gif (25.68 KiB) Visto 12950 volte

Considerazioni.
1) Se consideriamo statisticamente tutte le popolazioni che partono con 1 ameba, queste hanno la probabilità $\sqr 2-1$ di estinguersi. Naturalmente, la maggior parte di esse si stingueranno presto, già nei primi due o tre passaggi.

2) Nella popolazione, ogni ameba è indipendente dalle altre (questa è un'ipotesi tacita del problema). Cioè ogni ameba che si riproduce (o muore) può essere considerata come l'inizio di una nuova popolazione indipendente dalle altre.

3) Se un'ameba si divide in 3, non credo che dobbiamo cambiare l'equazione: statisticamente è semplicemente uno di quei casi in cui la popolazione ha meno probabilità di estinguersi, per la precisione $(\sqr 2-1)^3$

[Pasquale]

Vabbè, partendo con 3 amebe, la simulazione per l'estinzione si stabilizza intorno al 21% e comunque è funzione del tempo di osservazione; cioè, se la domanda è: "qual è la probabilità che le amebe di estinguano al secondo minuto (partendo da 3 amebe)?", il responso della simulazione non è più sul 21%, ma intorno al 15% .
Ritorniamo all'unica ameba iniziale: impostiamo l'equazione e si ottiene un risultato fra il 41% e 42%; qual è il significato?
L'ameba può estinguersi con una probabilità del 41%...quando? Non si sa, ovvero ogni momento è buono. Come si fa a verificare se è vero? Metodo sperimentale! Prendiamo ad esempio un milione di amebe ed una alla volta, stiamo a guardare se la relativa popolazione discendente si estingue.
Se non si estingue (questo avviene per la maggior parte del milione di esperimenti), siamo fregati, perché fra due milioni di anni non ancora sapremo se la popolazione di amebe discendenti dalla prima si estinguerà o meno, a parte il fatto che nel frattempo, prima delle amebe, saremo tutti morti da un bel pezzo, dannati per non aver potuto effettuare la verifica, a meno che..............

[Gianfranco]

Ciao Pasquale,

Non è un individuo che si estingue ma una popolazione.

L'ameba può estinguersi con una probabilità del 41%...quando? Non si sa, ovvero ogni momento è buono. Come si fa a verificare se è vero? Metodo sperimentale! Prendiamo ad esempio un milione di amebe ed una alla volta, stiamo a guardare se la relativa popolazione discendente si estingue.

Non è necessario fare un milione di esperimenti separati e sprecare un milione di capsule di Petri! Basta creare una sola colonia e considerare ogni nuova ameba che si forma come se fosse l'inizio di un nuovo esperimento.

Se non si estingue (questo avviene per la maggior parte del milione di esperimenti), siamo fregati, perché fra due milioni di anni non ancora sapremo...

Tranquillo, si estinguono...
Comunque lo stesso discorso, al limite, vale per il lancio di una moneta: potresti aspettare un milione di anni che esca croce...

Questi ragionamenti hanno un significato statistico: c'è da aspettarsi che accada qualcosa con una certa frequenza entro un certo tempo.
Comunque, la probabilità che una popolazione che parte da 1 ameba si estingua entro 1, 2, 3, ... minuti è data dalla formula ricorsiva:

${E}\left( n\right) ={p\cdot\[{E}\left( n-1\right) }\]^{3}+{p\cdot\[{E}\left( n-1\right) }\]^{2}+ p\cdot{E}\left( n-1\right)+p$

dove: $E(n)$ = probabilità di estinzione alla generazione n; $p=\frac{1}{4}$.

E(1) = 0.25
E(2) = 0.33203125
E(3) = 0.369720175862312
E(4) = 0.389237836855358
E(5) = 0.399928958663493
E(6) = 0.405959509213881
E(7) = 0.409416506828561
E(8) = 0.411416386464578
E(9) = 0.412579395904245
E(10) = 0.413257785970823
...

Se parti con una popolazione di n amebe, è come avere n popolazioni distinte e indipendenti, perciò le probabilità della lista precedente vanno elevate alla n-esima potenza.