[teoria] Hitting Time nelle catene di Markov

[momo1]

Data una Catena di Markov $(X_n)_{n \ge 0}$ in $E$, lo Hitting Time (scusate l'anglicismo, ma non mi viene una traduzione accettabile) di un sottoinsieme $A \in E$ è definito come:

$T = \text{inf}\{n \ge 0, X_n \in A \}$

In molti esercizi base viene chiesto di calcolare quantità come:

$P(X_{T} | X_0=i)$

che si risolvono con il condizionamento al primo passo (first step analysis). Gli esercizi una volta visto il procedimento, sono facili.

La mia domanda però è relativa alla quantità di cui sopra: cosa significamente realmente? E' un limite di una somma di probabilità, cioè:
$P(X_{T} | X_0=i) =\lim_{j \to \infty} \sum\_{n=1}^{j}P(X_n \in A, X_{n-1} \notin A, ..., X_1\notin A |X_0=i)$
?

Sicuramente è una domanda abbastanza banale, che però da non matematico quale sono mi sta facendo dubitare di quello che so di probabilità.

[momo1]

Ciao, hitting time si dice istante di primo arrivo in italiano.
Comunque c'è un'inesattezza di scrittura: $ P(X_{T} | X_0=i) $ non vuole dire nulla. $X_T$ è una v.a., non un evento. Tu semmai vuoi calcolare, data una classe chiusa $A$ di $E$ la probabilità di entrarci se la catena parte da $i$. Tale probabilità si scrive così:
$\mathbb{P}(\tau_A<\infty|X_0=i)=\mathbb{P}_i(\tau_A<\infty)$

Il calcolo di tale probabilità porta in effetti a sciogliere questa quantità (tra le altre cose) in una serie numerica. C'è un teorema che riguarda questa cosa; lo conosci? Detto questo precisa meglio ciò che non capisci, potrei riportarti la dim. ma è inutile se non so nello specifico qual è il problema.

Il mio problema è capire esattamente cosa vuol dire calcolare la probabilità di un istante di primo arrivo.
Più precisamente, nella tecnica del condizionamento al primo passo, il punto chiave è che si può scrivere:
$P(X_n = c | X_1 = j)=P(X_{n-1} = c | X_0 = j)$
grazie alla assunzione di omogeneità della Catena di Markov e immagino, grazie alla definizione stessa di probabilità di un istante di primo arrivo (intuitivamente ho pensato che essendo quest'ultima una serie infinita, l'istante di primo arrivo sia indifferentemente $n$ o $n-1$).

Scusa per la notazione imprecisa, ma è quella usata nel libro di testo che usando. il Bremaud.

[momo1]

Il Bremaud è un buon libro ma non trovo quello che tu dici. A che capitolo/paragrafo sei? (Incidentalmente: è anche un libro molto orientato alle applicazioni, anche avanzate, forse per questo genere di cose puoi accontentarti di un libro più elementare ma più completo).

Per me il tuo problema è innanzitutto concettuale: non ha senso chiedersi "cosa vuol dire calcolare la probabilità di un istante di primo arrivo". L'istante di primo arrivo è una variabile aleatoria. Puoi calcolare la probabilità che essa assuma un determinato valore, o che abbia un valore finito, ma non puoi calcolare la sua probabilità.
.

Mi riferisco al paragrafo 3.1, in cui introduce per la prima volta la first step analysis con l'esempio della rovina del giocatore. Seguendo la notazione del libro, in questo caso l'insieme chiuso è dato da $A = {c,0}$. Quindi $T = \text{inf}\{n \ge 0 , X_n \in A\}$. Viene poi definita $u(i) = P(X_T=c | X_0 = i)$ e applicata la first step analysis.
Usando la tua notazione quindi si sta parlando di:
$ \mathbb{P}(\tau_A<\infty|X_0=i)=\mathbb{P}_i(\tau_A<\infty) $

Cioè ci si chiede se la v.a. istante di primo arrivo in $A$ assume un valore finito? E questo calcolo dunque coinvolge una serie numerica?

Quanto all'uguaglianza che scrivi:
$ P(X_n = c | X_1 = j)=P(X_{n-1} = c | X_0 = j) $
Essa vale perché esiste un teorema (detto a volte di traslazione) che afferma che avere una catena $ (X_n)_{n\ge0} $ che al passo $ m $ si trova deterministicamente in uno stato $ i $ è la stessa cosa che avere una catena $ (X_{n-m})_{n\gem} $ con distribuzione iniziale deterministica $ X_0=i $.

Ok, la traslazione mi è chiara, quello che non mi è chiaro è perché il passaggio da $n-1$ a $n$ sia ininfluente. E' dovuto a quanto detto sopra, cioè che stiamo cercando la probabilità che l'istante di primo arrivo assuma un valore finito?

[momo1]

Ti ringrazio, ho una visione di insieme più chiara.

La traslazione è rilevante al finito ma non all'infinito. Infatti è importante quando scrivi:
$ P(X_n = c | X_1 = j)=P(X_{n-1} = c | X_0 = j) $
Qui è stato traslato lo stato iniziale e di conseguenza anche lo stato n-esimo.
Non ha nessuna importanza invece all'infinito ed è per questo che B. dice the events "$X$ is absorbed by $0$" and "$Y$ is absorbed by $0$" are identical
quando $Y$ è una traslata temporale di $X$.
Infatti se il tempo di assorbimento è finito per $X$ sarà finito anche per $Y$ e viceversa.

Ok, cercando di formalizzare un attimo.
Nel nostro caso l'evento "$X$ è assorbito da $0$" sarebbe $\bigcup_{n \ge 1}X_n=0$ che logicamente è uguale a "$Y$ è assorbito da $0$".


Quindi se ho capito bene la probabilità dell'evento "$X$ è assorbito da $0$" nel caso semplice in cui il patrimonio iniziale $c$ sia uguale a $0,1,3$ prevederebbe il calcolo di serie geometriche, come ad esempio nel caso $c=3$, partendo da $X_0=1$ e probabilità di successo $p$ e di perdita $q$:
$P(\bigcup_{n \ge 1}X_n=0|X_0=1) = q\sum_{n=0}^{\infty}(pq)^{n}$
e l'utilizzo della first step analysis e delle equazioni alla differenze permette di trovare soluzioni con $c$ arbitrario.

Un ultima cosa, la definizione di istante di primo arrivo chiede necessariamente che $A$ sia chiuso?
Perché se per esempio venisse chiesto, data una matrice di transizione senza stati assorbenti, la probabilità che venga raggiunto lo stato $a$ prima dello stato $b$, in questo caso avrei:
$T = \text{inf}{n \ge 0, X_n = {a,b}}$
e applicherei lo stesso ragionamento del problema della rovina del giocatore per calcolare:
$P(\tau_a < \infty | X_0 = i)=u(i)$
con i vincoli che:
$u(a)=1$ e $u(b)=0$
risolvendo un sistema lineare.

[momo1]

Grazie, penso di aver capito un po' meglio tutto al di là dei meri esercizi, che sono piuttosto meccanici.

Qua mi trovi impreparato Io finora lo ho visto fare solo per classi chiuse ma non so.

Non vedo perché i ragionamenti fatti in precedenza debbano valere solo per classi chiuse. Alla fine il condizionamento al primo passo (o equivalentemente il teorema di cui parli tu) non mi sembra dipendano dal fatto che la catena non può uscire da $A$ una volta entrata.