Passeggiata aleatoria.

[3m0o]

Ho difficoltà a provare questo esercizio perché non saprei da dove cominciare.

Sia \(G\) un grafo connesso, e \(v,w \) due vertici di \(G\).

a) Dimostra che una passeggiata aleatoria semplice su \(G\) è ricorrente partendo da \(v\) se e solo se è ricorrente partendo da \(w\)

b) Dimostra se una passeggiata aleatoria semplice \((S_n)_{n\geq 0} \) su \(G\) è ricorrente partendo da \(v\), allora per ogni vertice \(w\) di \(G\), \( \mathbb{P}_v(\exists n, S_n=w) = 1 \) e \( \mathbb{P}_w(\exists n, \tilde{S}_n = v) =1 \) dove \( (\tilde{S}_n)_{n \geq 0} \) è una passeggiata aleatoria semplice su \(G\) partendo da \(w\).


Edit: Penso di aver sbagliato sezione scusate

[ghira]

Ho difficoltà a provare questo esercizio perché non saprei da dove cominciare.

Sia \(G\) un grafo connesso, e \(v,w \) due vertici di \(G\).

Il grafo è finito? Una passeggiata aleatoria semplice su $\mathbb{Z}^3$ non è ricorrente. C'è "se e solo se" quindi ok l'esercizio copre anche questo caso.

[3m0o]

Non è necessariamente finito ma credo che debba essere localmente finito, i.e. il grado di ogni vertice è finito.

Edit: la mia idea è dimostrare che se \( N(v) := \# \{ n \geq 0 : S_n = v \} \) allora abbiamo che \( \mathbb{E}[N(v)] = \infty \) se e solo se \( \mathbb{E}[N(w)] = \infty \).

[ghira]

H
a) Dimostra che una passeggiata aleatoria semplice su \(G\) è ricorrente partendo da \(v\) se e solo se è ricorrente partendo da \(w\)

Qualcosa del tipo:

Se la passeggiata è ricorrente:
La probabilità di tornare a $v$ è 1. La probabilità di passare per $w$ prima o poi è maggiore di 0 perché il grafo è connesso. Se la probabilità di passare per $v$, cominciando da $w$, fosse minore di 1, la passeggiata non sarebbe ricorrente.

?

[3m0o]

Mmh non sono convinto dalla tua argomentazione, in realtà mi sto confondendo anche sulla possibilità di aver capito male la domanda.

Nel senso prendiamo \(G=\mathbb{Z}\), sia \((S_n)_{n \geq 0} \) una passeggiata aleatoria semplice, questo vuol dire che per ogni \(n \geq 1 \) abbiamo che \(S_n \) è una variabile aleatoria che assume valori in \(\{S_{n-1}-1,S_{n-1}+1\}\) con probabilità \(1/2)\). Supponiamo che \(S_0=v \), \( \tilde{S}_0=w \) siano due interi, io interpreto la domanda nel seguente modo
\[ \sum_{n=0}^{\infty} \mathbb{P}_v(S_n=v) = \infty \]
se e solo se
\[ \sum_{n=0}^{\infty} \mathbb{P}_w(\tilde{S}_n=w) = \infty \]
con \(G=\mathbb{Z}\) in un certo senso mi sembra evidente perché stiamo semplicemente traslando la passeggiata aleatoria, quindi se \((S_n)_{n \geq 0} \) parte da \(v \) e ritorna con probabilità \(1\) a \(v\) se la trasliamo ottenendo \( (\tilde{S}_n)_{n \geq 0} \) che parte da \(w\) allora la "stessa" passeggiata aleatoria tornerà con probabilità \(1\) a \(w\).

Il problema è che questa intuizione non è troppo adatta a parer mio, perché passando ad un grafo generico localmente finito, abbiamo che già il grado \(v \) potrebbe essere differente dal grado di \(w\).
Quindi interpreto la domanda come dati \(v,w \in G \) e due passeggiate aleatorie semplici \((S_n)_n \) che parte da \(v\) e \( (\tilde{S}_n)_n\) che parte da \(w\) abbiamo che \((S_n)_{n \geq 0} \) è ricorrente se e solo se \( (\tilde{S}_n)_{n \geq 0}\). Quindi con la tua argomentazione se arrivo a \(w\) con probabilità positiva allora il futuro è una passeggiata aleatoria semplice che ritorna a \(v\) con probabilità \(1\) per quello che dici te (o quasi per definizione) ma nulla mi garantisce che ritornerà ancora \(w\) per dire che ritornerà a \(w\) dovrei dimostrare che la probabilità di arrivare a \(w\) partendo da \(v\) non solo sia positiva ma che sia pure \(1\). Il punto è che non è nemmeno chiaro che la probabilità di arrivare a \(w\) sia positiva. Sostanzialmente per dimostrare il claim a) dovrei dimostrare che dato un vertice \(v\) arbitrario di partenza di una passeggiata aleatoria semplice ricorrente allora ogni vertice è raggiunto con probabilità \(1\).

[ghira]

Ci sono varie definizioni di ricorrente.

Io solitamente uso "La probabilità di tornare è 1" ma per esempio questa pagina offre altre definizioni equivalenti:

https://mpaldridge.github.io/math2750/S ... ience.html

[3m0o]

Così dovrebbe funzionare

a)
Esiste un intero \(k\) tale che andiamo da \(v\) a \(w\) in \(k\) steps. Quindi per \(n \geq 2k \) consideriamo i cammini che vanno da \(w\) a \(v\) in \(k\) steps, e poi fanno \(n-2k\) steps e tornano a \(v\) e dopo \(k\) steps tornano indietro a \(w\) abbiamo che
\[ \mathbb{P}_w(S_n=w) \geq \mathbb{P}_w(S_k=v)\mathbb{P}_v(S_{n-2k}=v)\mathbb{P}_v(S_k=w) \]
sommando su \(n\) otteniamo che
\[ \sum_{n \geq 1} \mathbb{P}_w(S_n=w) \geq \mathbb{P}_w(S_k=v) \sum_{n \geq 1} \mathbb{P}_v(S_{n-2k}=v)\mathbb{P}_v(S_k=w) \]
poiché \( (S_n)_{n \geq 0} \) è ricorrente partendo da \(v\) abbiamo che
\[ \sum_{n \geq 1} \mathbb{P}_v(S_{n}=v) = \infty \]
da cui abbiamo che
\[ \sum_{n \geq 1} \mathbb{P}_v(S_{n-2k}=v) = \infty \]
Pertanto
\[ \sum_{n \geq 1} \mathbb{P}_w(S_n=w) = \infty \]
dunque la passeggiata è ricorrente anche partendo da \(w\).

b)
La prima asserzione è dimostrata nel punto precedente. Per la seconda asserzione abbiamo che partendo da \(w\) è anche ricorrente, quindi applicando di nuovo il punto a) permutando il ruolo di \(v\) e \(w\) ci da la seconda asserzione.

[vict85]

Ho spostato in statistica e probabilità.