Visite totali di uno stato in una catena di Markov
Studiando le catene di Markov omogenee, ho avuto delle difficoltà in questo argomento:
$\{X_n\}$ catena di Markov omogenea, $N^j:=$numero totale di visite allo stato $j$ partendo da $X_0=i $,
Devo dimostrare per induzione che,
Posto $f_{ij}:=\sum_{n=1}^\infty P(X_1\ne j,...,X_{n-1}\ne j, X_n=j |X_0=i)$
$P(N^j=0)=1- f_{ij}$
$P(N^j=n)=f_{ij}(f_{jj})^{n-1}(1-f_{jj})$ se $n\geq 1$
La dimostrazione è per induzione, il caso $n=0 $ è facile:
$B:=\{N^j=0\}$, $A_n^i:=\{X_1\ne j,...,X_{n-1}\ne j, X_n=j |X_0=i \}$ e $j\ne i$
$B=\cap_{n=1}^\infty (A_n^i)^C=(\cup_{n=1}^\infty A_n^i)^C$ quindi $P(B)=1-\sum_{n=1}^\infty P(A_n^i)=1- f_{ij}$.
Se $n=1$, $B:=\{N^j=1\}$ e $A_n^j:=\{X_1\ne j,...,X_{n-1}\ne j, X_n=j |X_0=j \}$, ora arriva il passaggio al quale non riesco a dare senso, quindi $B=(\cup_{n=1}^\infty A_n^i)\cap(\cap_{n=1}^\infty (A_n^j)^C)$.
Non riesco a capire come si possa fare l'intersezione o prodotto logico tra quei due eventi, visto che uno condiziona rispeto a $X_0=i$ e uno rispetto a $X_0=j$. Proprio non capisco che ragionamento sta dietro. Il secondo fattore del prodotto logico rappresenta l'evento che se la catena parte da $j$, allora non deve più ritornare in$ j$; mentre il primo fattore mi dice che la catena visita lo stato $j$ una volta ad un qualsiasi stato che non sia quello iniziale.
Credo di aver intuito che questa cosa del prodotto logico si fa perché se $i$ e $j $ sono uguali, il primo fattore mi dice che una visita la faccio al tempo zero e una la rifaccio più avanti, quindi quel prodotto logico dovrebbe servire a eliminare questi eventi aggiuntivi, andando appunto a restringermi ai soli eventi in cui la catena visita $ j$ alla partenza, ma così vado anche ad eliminare tutti gli altri eventi dove la catena non parte da $ j $ e lo visita solo una volta!
Non riesco a visualizzare come possa funzionare quella formula perché credo di non avere dimestichezza con questi eventi condizionati.
Una volta provato ciò, l'asserto segue facilmente da cose basilari.
$\{X_n\}$ catena di Markov omogenea, $N^j:=$numero totale di visite allo stato $j$ partendo da $X_0=i $,
Devo dimostrare per induzione che,
Posto $f_{ij}:=\sum_{n=1}^\infty P(X_1\ne j,...,X_{n-1}\ne j, X_n=j |X_0=i)$
$P(N^j=0)=1- f_{ij}$
$P(N^j=n)=f_{ij}(f_{jj})^{n-1}(1-f_{jj})$ se $n\geq 1$
La dimostrazione è per induzione, il caso $n=0 $ è facile:
$B:=\{N^j=0\}$, $A_n^i:=\{X_1\ne j,...,X_{n-1}\ne j, X_n=j |X_0=i \}$ e $j\ne i$
$B=\cap_{n=1}^\infty (A_n^i)^C=(\cup_{n=1}^\infty A_n^i)^C$ quindi $P(B)=1-\sum_{n=1}^\infty P(A_n^i)=1- f_{ij}$.
Se $n=1$, $B:=\{N^j=1\}$ e $A_n^j:=\{X_1\ne j,...,X_{n-1}\ne j, X_n=j |X_0=j \}$, ora arriva il passaggio al quale non riesco a dare senso, quindi $B=(\cup_{n=1}^\infty A_n^i)\cap(\cap_{n=1}^\infty (A_n^j)^C)$.
Non riesco a capire come si possa fare l'intersezione o prodotto logico tra quei due eventi, visto che uno condiziona rispeto a $X_0=i$ e uno rispetto a $X_0=j$. Proprio non capisco che ragionamento sta dietro. Il secondo fattore del prodotto logico rappresenta l'evento che se la catena parte da $j$, allora non deve più ritornare in$ j$; mentre il primo fattore mi dice che la catena visita lo stato $j$ una volta ad un qualsiasi stato che non sia quello iniziale.
Credo di aver intuito che questa cosa del prodotto logico si fa perché se $i$ e $j $ sono uguali, il primo fattore mi dice che una visita la faccio al tempo zero e una la rifaccio più avanti, quindi quel prodotto logico dovrebbe servire a eliminare questi eventi aggiuntivi, andando appunto a restringermi ai soli eventi in cui la catena visita $ j$ alla partenza, ma così vado anche ad eliminare tutti gli altri eventi dove la catena non parte da $ j $ e lo visita solo una volta!
Non riesco a visualizzare come possa funzionare quella formula perché credo di non avere dimestichezza con questi eventi condizionati.
Una volta provato ciò, l'asserto segue facilmente da cose basilari.
Risposte
"materia":
Credo di aver intuito che questa cosa del prodotto logico si fa perché se $i$ e $j $ sono uguali, il primo fattore mi dice che una visita la faccio al tempo zero e una la rifaccio più avanti, quindi quel prodotto logico dovrebbe servire a eliminare questi eventi aggiuntivi, andando appunto a restringermi ai soli eventi in cui la catena visita $ j$ alla partenza, ma così vado anche ad eliminare tutti gli altri eventi dove la catena non parte da $ j $ e lo visita solo una volta!
Non riesco a visualizzare come possa funzionare quella formula perché credo di non avere dimestichezza con questi eventi condizionati.
Una volta provato ciò, l'asserto segue facilmente da cose basilari.
Tu non li elimini, perché la tua catena parte da $i$, quindi prima di fare un loop attorno a $j$ deve visitare $j$. Quello che vuoi scrivere è che $j$ è visitato una sola volta.
Usa direttamente la probabilità, senza stare a usare degli "eventi condizionati"... Secondo me (e anche su un piano teorico mi sembra più sensato) è meglio definire il condizionamento sulla misura di probabilità che usi, non sull'evento.
In questo senso per il caso $n=1$ e i successivi potresti ragionare cosi': Usando le tue notazioni avresti $\{N^j=1\} =\cup_{n=1}^\infty \{A_n^i, X_k\ne j\, \forall k\ge n+1\}$.
cosi' $P(N^j=1|X_0=i)= \sum_{n=1}^\infty P(A_n^i, X_k\ne j\, \forall k\ge n+1 | X_0=i)$ e qua usi la proprietà di markov per fattorizzare e ti ritrovi con la formula iniziale.
La soluzione è tua o è data da qualcuno ? per curiosità
). Sinceramente ho difficoltà a capire cosa intendi con questi eventi condizionati, che definizione dai all'evento $\{A|B\}$ ?
"fu^2":
Tu non li elimini, perché la tua catena parte da $i$, quindi prima di fare un loop attorno a $j$ deve visitare $j$. Quello che vuoi scrivere è che $j$ è visitato una sola volta.
In questo senso per il caso $n=1$ e i successivi potresti ragionare cosi': Usando le tue notazioni avresti $\{N^j=1\} =\cup_{n=1}^\infty \{A_n^i, X_k\ne j\, \forall k\ge n+1\}$.
cosi' $P(N^j=1|X_0=i)= \sum_{n=1}^\infty P(A_n^i, X_k\ne j\, \forall k\ge n+1 | X_0=i)$ e qua usi la proprietà di markov per fattorizzare e ti ritrovi con la formula iniziale.
La soluzione è tua o è data da qualcuno ? per curiosità
Non capisco come, ponendo $\{N^j=1\} =\cup_{n=1}^\infty \{A_n^i, X_k\ne j\, \forall k\ge n+1\}$, tu riesca ad escludere che nel caso in cui $i=j$, ossia in cui la catena parta già da $j$, in nessun'altro stato ripassi per $j$.
Secondo me in quel modo consideri tutte le catene che, se $i\ne j$ partono da $i$ e visitano $j$ solo una volta, mentre se $i=j$ partono da $j$ e lo rivisitano una seconda volta.
L'ultimo caso non lo voglio, mi serve che se $i=j$, allora la catena non deve mai più passare per lo stato $j$.
Credo che la tua difficoltà nel comprendere cosa intendo con gli eventi condizionati nasca dal fatto che non ho chiari gli eventi condizionati.
Direi che $P(A|B)$, se il condizionante non ha probabilità nulla, è la probabilità dell'evento $A$, supposto che l'evento $B$ sia realizzato, quindi senza fare nessuna inferenza su $B$, ma semplicemente andando a restringere lo spazio campionario $\Omega$ dei possibili risultati di un esperimento, a $B|B$.
Non sono sicuro di aver capito cosa intendi con
Usa direttamente la probabilità, senza stare a usare degli "eventi condizionati"... Secondo me (e anche su un piano teorico mi sembra più sensato) è meglio definire il condizionamento sulla misura di probabilità che usi, non sull'evento.
La cosa che mi confonde è che qui devo ragionare con due condizionanti diversi.
A tal proposito mi sono interrogato su questo fatto, che credo possa essere una chiave per dar senso alla dimostrazione:
Se $C\subset B$ e $D\subset A$, si può definire l'evento $A|B \cap D|C$? E la sua definizione potrebbe essere $A|B-C \cup D|C$?
Mi hai anche fatto notare che c'è un'altra cosa che non torna, ossia che $\cup_{n=1}^\infty \A_n^i$ rappresenta l'evento "la catena visita lo stato $j$ almeno una volta", non "esattamente una volta" come erroneamente avevo dato per buono.
Comunque pensavo di essermi esplicitato, sto ripercorrendo la dimostrazione che ho negli appunti, alla quale sto cercando di dare un senso. Non ho alcun testo di riferimento per questa proposizione.
Grazie per la risposta
Se non leggo male mi sembra che $N^j$ conti le visite allo stato $j$ partendo da $n\ge 1$, ovvero $N^j=\sum_{k=1}^{\infty }1_{\{X_k=j\}}$, altrimenti la formula per ricorrenza non mi torna: se poniamo $\tilde N^j=\sum_{k=0}^{\infty }1_{\{X_k=j\}}$, alora si ha che $P(\tilde N^j=0|X_0=j)=0$, che non è quello che dice la tua formula di ricorrenza. Concordi ?
Il tuo esercizio riguarda $N^j$, mi sembra. Ti lascio pensare a quale sia l'importanza del punto di partenza in questo caso.
L'evento $\cup_{n=1}^\infty A_n^i$ è l'evento "$j$ è visitato per la prima volta dal il tempo $n\ge 1$". Devo correggermi un attimo, quello che volevo scrivere nel mio post precedente è che $A_n^i=A_n=\{X_1\ne j,...,X_{n-1}\ne j, X_n=j\}$ senza il condizionamento (quindi non c'è dipendenza da $i$).
Per chiarire il significato di $\cup_{n=1}^\infty A_n$ , si puo' definire la va $\tau=\text{inf}\{n\ge 1: X_n=j\}$, allora $\{\tau < +\infty\}=\cup_{n=1}^\infty A_n$, in particolare $\{\tau =n\}=A_n$.
A questo punto puoi scrivere
$ P(N^j=1|X_0=i)= P(\tau<\infty, X_{\tau+k}\ne j,\, \forall k>0 | X_0=i) = \sum_{n=1}^\infty P(A_n, X_{k+n}\ne j\, \forall k>0 | X_0=i) $
Qua usi la proprietà di markov : $P(A_n, X_{k+n}\ne j\, \forall k>0 | X_0=i) =P(A_n |X_0=i) P(X_{k+n}\ne j\, \forall k>0 | X_n=j) =P(A_n |X_0=1) P(X_k\ne j\, \forall k>0 | X_0=j) $.
Ti torna questa uguaglianza ? Qui si usano le proprietà della probabilità condizionata e il fatto che $X$ sia una catena di Markov omogenea.
Nota che $P(X_k\ne j\, \forall k\ge 1 | X_0=j) =P(\tau=\infty |X_0=j)$ ovvero non visitiamo più lo stato $j$.
Mi sembra un po' confuso. Più semplicemente $ P(A|B)=(P(A\cap B))/(P(B))$.
Il tuo esercizio riguarda $N^j$, mi sembra. Ti lascio pensare a quale sia l'importanza del punto di partenza in questo caso.
L'evento $\cup_{n=1}^\infty A_n^i$ è l'evento "$j$ è visitato per la prima volta dal il tempo $n\ge 1$". Devo correggermi un attimo, quello che volevo scrivere nel mio post precedente è che $A_n^i=A_n=\{X_1\ne j,...,X_{n-1}\ne j, X_n=j\}$ senza il condizionamento (quindi non c'è dipendenza da $i$).
Per chiarire il significato di $\cup_{n=1}^\infty A_n$ , si puo' definire la va $\tau=\text{inf}\{n\ge 1: X_n=j\}$, allora $\{\tau < +\infty\}=\cup_{n=1}^\infty A_n$, in particolare $\{\tau =n\}=A_n$.
A questo punto puoi scrivere
$ P(N^j=1|X_0=i)= P(\tau<\infty, X_{\tau+k}\ne j,\, \forall k>0 | X_0=i) = \sum_{n=1}^\infty P(A_n, X_{k+n}\ne j\, \forall k>0 | X_0=i) $
Qua usi la proprietà di markov : $P(A_n, X_{k+n}\ne j\, \forall k>0 | X_0=i) =P(A_n |X_0=i) P(X_{k+n}\ne j\, \forall k>0 | X_n=j) =P(A_n |X_0=1) P(X_k\ne j\, \forall k>0 | X_0=j) $.
Ti torna questa uguaglianza ? Qui si usano le proprietà della probabilità condizionata e il fatto che $X$ sia una catena di Markov omogenea.
Nota che $P(X_k\ne j\, \forall k\ge 1 | X_0=j) =P(\tau=\infty |X_0=j)$ ovvero non visitiamo più lo stato $j$.
"materia":
Direi che $ P(A|B) $, se il condizionante non ha probabilità nulla, è la probabilità dell'evento $ A $, supposto che l'evento $ B $ sia realizzato, quindi senza fare nessuna inferenza su $ B $, ma semplicemente andando a restringere lo spazio campionario $ \Omega $ dei possibili risultati di un esperimento, a $ B|B $.
Mi sembra un po' confuso. Più semplicemente $ P(A|B)=(P(A\cap B))/(P(B))$.
//
"fu^2":
Se non leggo male mi sembra che $N^j$ conti le visite allo stato $j$ partendo da $n\ge 1$, ovvero $N^j=\sum_{k=1}^{\infty }1_{\{X_k=j\}}$, altrimenti la formula per ricorrenza non mi torna: se poniamo $\tilde N^j=\sum_{k=0}^{\infty }1_{\{X_k=j\}}$, alora si ha che $P(\tilde N^j=0|X_0=j)=0$, che non è quello che dice la tua formula di ricorrenza. Concordi ?
Il fatto è che secondo me in effetti questa cosa è ambigua, almeno nella dimostrazione che ho, nel caso $n=0$ la dimostrazione specifica che $i\ne j$ come se desse per buono che se fossero uguali quella probabilità fosse nulla, esattamente come hai scritto tu qua sopra. Credo che dovrò ricorrere ad un ricevimento per chiarire il tutto perché andando a risentire la lezione online, nel passaggio dove richiedo spiegazioni nel primo post, il Docente afferma proprio che se la catena parte da $j$ allora non deve ritornarci.
La cosa che volevi dirmi nel messaggio precedente è $A_n$ è "il tempo di primo passaggio per $j$ è $n$", si ok lì ci sono.
Grazie ancora, farò sapere aggiornamenti perché ci sono molte cose che non mi filano.
Mi sono messo giù con carta e penna e ho compreso che nel primo passaggio hai usato $P(A\cap B|C)=P(B|A\cap C)P(A|C)$ e poi hai usato come pensavo la markovianità ed infine l'omogeneità.
Ho compreso rileggendomi la teoria che effettivamente lo stato di partenza non deve essere contato, quindi dal momento che questa dimostrazione mi fila, userò questa.
Grazie per la pazienza
Ho compreso rileggendomi la teoria che effettivamente lo stato di partenza non deve essere contato, quindi dal momento che questa dimostrazione mi fila, userò questa.
Grazie per la pazienza
Una volta formulata l'ipotesi induttiva non è per niente facile dimostrare il passo induttivo. Per un generico $n\>1$ si ha che $\{N^j=n\}=\cup_{r\leq 1}\{A_r, \cup_{l_2\ne l_3\ne...\ne l_n\geq 1 }\{X_{r+m}=j \forall m\in\{l_2,...,l_n\},X_{r+s}\ne j \forall s\notin \{l_2,...,l_n\} \}|X_0=i\}$
So che la notazione è pesante, a parole non ho scritto altro che "prendo tutte le catene che supposto partino da $i$, fino a un certo $n$ visitano una unica volta lo stato $j$ poi lo visitano esattamente altre $r-1$ volte.
Questa è una mia congettura, ma sono abbastanza sicuro che vada bene, perché se si fa il calcolo della probabilità con $n=2$, otteniamo l'asserto desiderato
Il punto è che andando a calcolarne la probabilità non so come andare avanti. Ho anche dei dubbi circa la sua dimostrabilità per induzione
So che la notazione è pesante, a parole non ho scritto altro che "prendo tutte le catene che supposto partino da $i$, fino a un certo $n$ visitano una unica volta lo stato $j$ poi lo visitano esattamente altre $r-1$ volte.
Questa è una mia congettura, ma sono abbastanza sicuro che vada bene, perché se si fa il calcolo della probabilità con $n=2$, otteniamo l'asserto desiderato
Il punto è che andando a calcolarne la probabilità non so come andare avanti. Ho anche dei dubbi circa la sua dimostrabilità per induzione
"materia":
Una volta formulata l'ipotesi induttiva non è per niente facile dimostrare il passo induttivo. Per un generico $n\>1$ si ha che $\{N^j=n\}=\cup_{r\leq 1}\{A_r, \cup_{l_2\ne l_3\ne...\ne l_n\geq 1 }\{X_{r+m}=j \forall m\in\{l_2,...,l_n\},X_{r+s}\ne j \forall s\notin \{l_2,...,l_n\} \}|X_0=i\}$
So che la notazione è pesante, a parole non ho scritto altro che "prendo tutte le catene che supposto partino da $i$, fino a un certo $n$ visitano una unica volta lo stato $j$ poi lo visitano esattamente altre $r-1$ volte.
Questa è una mia congettura, ma sono abbastanza sicuro che vadi bene, perché se si fa il calcolo della probabilità con $n=2$, otteniamo l'asserto desiderato
Il punto è che andando a calcolarne la probabilità non so come andare avanti. Ho anche dei dubbi circa la sua dimostrabilità per induzione
Ho trovato un modo migliore di scrivere l'evento, si devono introdurre degli insiemi $A_{r-upla}$ che descrivono "la catena è $j$ negli stati indicati dalla $r$-upla e diverso da $j$ negli stati compresi tra un indice e il suo successivo".
Ciò mi permette di scrivere l'evento $\{N^j=r\}$ $=\cup_{n\ge 1}\{ A_{n,n+l_2,...,n+l_2+...+l_r}, X_{n+l_2+...+l_r+k}\ne j \forall k\ge 0|X_0=i\}.$
Da qui procedendo iterativamente sempre coi due soliti passaggi visti nell'uguaglianza che mi ha postato "fu^2", si arriva alla tesi.
Se vuoi un modo più leggero (ma equivalente al tuo) di scrivere $\{N^j=n\}$ (che è abbastanza standard) è quella di usare le variabile $\tau$ che avevo introdotto prima. Ovvero
$\tau_1=\text{int}\{k>0 | X_k=j\}$,
$\tau_k=\text{int}\{k>\tau_{k-1} | X_k=j\}$. In questo modo hai che $\tau_k-\tau_{k-1}$ è il tempo che passa tra una visita di $j$ e la successiva.
Quindi $\{N^j=n\}=\{\tau_1<\infty, ...,\tau_n<\infty, X_k\ne j,\, \forall \, k>\tau_{n}\}$ e poi usi la proprietà di Markov sull'ultimo $\tau_n$ e l'ipotesi induttiva (non ho verificato i dettagli).
$\tau_1=\text{int}\{k>0 | X_k=j\}$,
$\tau_k=\text{int}\{k>\tau_{k-1} | X_k=j\}$. In questo modo hai che $\tau_k-\tau_{k-1}$ è il tempo che passa tra una visita di $j$ e la successiva.
Quindi $\{N^j=n\}=\{\tau_1<\infty, ...,\tau_n<\infty, X_k\ne j,\, \forall \, k>\tau_{n}\}$ e poi usi la proprietà di Markov sull'ultimo $\tau_n$ e l'ipotesi induttiva (non ho verificato i dettagli).
Grazie, sono l'ufficio complicazioni affari semplici 
Come osservazione al teorema ho che se $j$ è uno stato ricorrente, posto $N(i)$ il numero totale di visite allo stato iniziale $i$, allora dal teorema $P(N(i)\<\infty)=0$ e quindi $P(N(i)=\infty)=1$, la cosa che a mente non mi torna è che prosegue dicendo che se invece lo stato è transiente, banalmente $P(N(i)=\infty)=0$. Questa cosa non mi è chiarissima, e a me intuitivamente verrebbe solo da dire che quella probabilità non è $1$. Come posso ragionare per comprendere questa cosa?
Come osservazione al teorema ho che se $j$ è uno stato ricorrente, posto $N(i)$ il numero totale di visite allo stato iniziale $i$, allora dal teorema $P(N(i)\<\infty)=0$ e quindi $P(N(i)=\infty)=1$, la cosa che a mente non mi torna è che prosegue dicendo che se invece lo stato è transiente, banalmente $P(N(i)=\infty)=0$. Questa cosa non mi è chiarissima, e a me intuitivamente verrebbe solo da dire che quella probabilità non è $1$. Come posso ragionare per comprendere questa cosa?
Per lo stato transiente usa la formula che hai dimostrato per induzione
$P(N^j=n)=f_{ij}(f_{jj})^{n-1}(1-f_{jj})$ se $n\geq 1$
con la definizione di stato transiente : https://en.wikipedia.org/wiki/Markov_chain "A state $i$ is said to be transient if, starting from $i$, there is a non-zero probability that the chain will never return to $i$" (non so quale definizione esatta hai usato nel tuo corso). Questo ti dice che $f_{jj}<1$: $f_{jj} $ è la probabilità che partendo da $j$, lo stato $j$ sia rivisitato.
Come deduci $P(N^j=+\infty)$ da $P(N^j=n)$?
$P(N^j=n)=f_{ij}(f_{jj})^{n-1}(1-f_{jj})$ se $n\geq 1$
con la definizione di stato transiente : https://en.wikipedia.org/wiki/Markov_chain "A state $i$ is said to be transient if, starting from $i$, there is a non-zero probability that the chain will never return to $i$" (non so quale definizione esatta hai usato nel tuo corso). Questo ti dice che $f_{jj}<1$: $f_{jj} $ è la probabilità che partendo da $j$, lo stato $j$ sia rivisitato.
Come deduci $P(N^j=+\infty)$ da $P(N^j=n)$?
$P(N(i)=\infty)=1-\sum_{n=1}^\infty P(N(i)=n)=1-(1-f_{jj})\sum_{n=1}^\infty f_{jj}^n=1-1=0$
La condizione di convergenza è garantita dallo stato transiente
Grazie e scusa l'ovvietà
La condizione di convergenza è garantita dallo stato transiente
Grazie e scusa l'ovvietà
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo