Newsgroup: it.hobby.enigmi
Titolo: insisto sul footing di Lucia

Ripropongo un quesito che avevo posto alcuni giorni fa rispondendo ad una
domanda di Stefano Costa:
Lucia vive su una piccola isola dove si trovano 4 paesi come mostrato
sotto; le strade che li collegano sono lunghe ciascuna 1 Km (anche se non
si direbbe :)
 
    B--C
   /\  |
  /  \ |
 A    D
 
Lucia, che vive a D, pratica footing: quando fa una corsa, fa un giro di un
certo numero di Km per i paesi. Ora Stefano chiedeva in quanti modi
possibili Lucia poteva fare 10 Km tornando alla fine in D opure arrivando
in B, paese del suo ragazzo. 
La mia domanda, che ripropongo, era invece era questa: supponiamo che Lucia
corra senza meta, ogni volta scegliendo a caso tra le diverse possibili
svolte, senza preferenze, qual'e' la probabilita' che dopo 10 km Lucia si
ritrovi tra le braccia del suo ragazzo?
Alla lunga quali sono le probabilita' di trovarsi in una citta' prefissata?
Ciao, Silvio

Silvio wrote:

Ciao
secondo la tabella riportata da Dario nel thread di Stefano
risulta che con 10 Km ho il seguente numero di cammini
n     A    B    C    D
...
10  349  729  637  638
I possibili percorsi totali dovrebbero essere quindi
2353
la probabilita' che Lucia partendo da D finisca in B
dovrebbe essere 729 / 2353
per l'altra domanda ... a dopo
ciao
Italo

 Italo
Ciao, Silvio

 non e' esatto:
Ok, non avevo letto bene il testopensavo che Lucia scegliesse il cammino prima di
intraprenderlo tra quelli possibili
Ora e' chiaro ...
per arrivare alla soluzione si dovrebbe
costruire una tabella analoga a quella di Dario
considerando infatti che la probabilita' di arrivare
ad es. su A in n passi e' uguale ad arrivare in B in n-1 passi
per la propabilita' del tratto B-A (cioe' 1/3)
si possono costruire le seguenti relazioni
Px(n) leggasi probabilita' di arrivare in x in n passi
Pa(n) = Pb(n-1) / 3
Pb(n) = Pa(n-1) + Pd(n-1) / 2 + Pc(n-1) / 2
Pc(n) = Pb(n-1) / 3 + Pd(n-1) / 2
Pd(n) = Pb(n-1) / 3 + Pc(n-1) / 2
si ha quindi una tabella:
n    Pa    Pb    Pc    Pd
0     0     0     0     1
1     0    1/2   1/2    0
2    1/6   1/4   1/6   5/12
3    1/12 11/24  7/24  1/6
...
10   0.13 0.366  0.25  0.25
Per qunato riguarda a lungo andare
le equazioni di sopra (che sono delle equazioni
differenziali a tempo discreto)
raggiungono l'equilibrio
La condizione di equilibrio si calcola
imponendo che Px(n) = Px(n-1)
cosi' facendo ottengo un sistema di equazioni
Pa = Pb/3
Pb = Pa + Pd/2 +Pc/2
Pc = Pb/3 + Pd/2
Pd = Pc/2 + Pb/3
queste quattro equazioni sono tra loro linearmente dipendenti
(dalle ultime tre infatti si puo' ricavare la prima)
l'informazione che ci manca e' espressa dall'equazione
Pa + Pb + Pc + Pd = 1
risolvendo il sistema ottengo
Pa = 1/8
Pb = 3/8
Pc = 1/4
Pd = 1/4
ciao
Italo

Pd = 1/4
Forse non tutti sanno che in una catena di Markov del tipo in questo
problema (cioe' una cosa in cui scegli una porta a caso per uscire da
una stanza, ecc. ecc.) le probabilita' nel lungo andare di trovarsi in
stanza x sono (numero di porte in stanza x) / (numero totale di porte).
nel "numero totale" ogni porta viene contata due volte - una per stanza.
allora qui abbiamo 8 porte. e a, b, c, d ne hanno 1, 3, 2, 2
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
http://www.mistral.co.uk/ghira/homepage.html

 Pd = 1/4
Soluzione ineccepibile. 
Qualche considerazione: guardiamo la distribuzione di probabilita' di
trovarsi alla lunga in una citta' prefissata. si chiama anche distribuzione
stazionaria, e' la distribuzione verso la quale il sistema evolve, e, come
fai notare tu, una volta che il sistema raggiunge questa configurazione
ogni ulteriore iterazione ci riporta alla condizione precedente. possiamo
vedere la cosa in questo modo: supponiamo che i corridori sull'isola siano
otto: come devono essere distribuiti nelle varie citta' affinche'
mediamente il numero di atleti presenti in ogni centro non cambi? questa
distribuzione e' apppunto la distribuzione stazionaria. per raggiungerla
potremo far partire inizialmente gli atleti da una o piu' citta' scelte a
caso ed aspettare un tempo sufficientemente lungo: quale che sia la
distribuzione iniziale, alla gli atleti tenderanno a distribuirsi sempre
nella stessa maniera. pero' anziche' fare il limite delle iterazioni
conviene, come hai fatto tu, risolvere un sistema lineare, che sotto certe
semplici ipotesi (tutte le citta' devono comunicare, tra loro e altre
condizioni del genere), e' sicuramente determinato. se piazziamo gli 8
atleti come suggerito dalla soluzione, 1 in A, 3 in B, 2 in C e 2 in D e
proviamo a vedere cosa succede dopo un chilometro, vediamo che da A un
altleta e' partito alla volta di B, da B i tre atleti hanno preso tre
strade diverse e cosi' da C e D, ma sostanzialmente sempre 1, 3, 2 e 2
saranno dopo la corsetta. Il nostro esempio era articolarmente semplice,
perche' per ogni citta' le svolte erano equiprobabili: in questi casi, e
l'esempio portato ne e' una chiara giustificazione, la probabilita' di ogni
nodo e' sempre data dal numero di vertici che convergono nel nodo diviso il
numero totale di nodi, quindi potevamo evitare di risolvere il sistema.
Ciao, Silvio