Tramite il passo induttivo
si ottiene la relazione
Enigma
Cosa c'entra la relazione di cui sopra con le catene di Markov?
Se non doveste venirne a capo, vi basta aspettare qualche giorno: al massimo sabato.
Visualizzazione post con etichetta markov. Mostra tutti i post
Visualizzazione post con etichetta markov. Mostra tutti i post
giovedì, settembre 04, 2008
Enigma
Cominciamo con la base dell'induzione:
Tramite il passo induttivo
si ottiene la relazione
Enigma
Cosa c'entra la relazione di cui sopra con le catene di Markov?
Se non doveste venirne a capo, vi basta aspettare qualche giorno: al massimo sabato.
Tramite il passo induttivo
si ottiene la relazione
Enigma
Cosa c'entra la relazione di cui sopra con le catene di Markov?
Se non doveste venirne a capo, vi basta aspettare qualche giorno: al massimo sabato.
venerdì, maggio 09, 2008
Disugualglianza di Markov
Una variabile casuale è una funzione che mappa un certo spazio di probabilità, che chiamiamo P, in uno spazio campionario V.
Per dirla in maniera un po' più semplice, anche se più imprecisa, è un elenco delle probabilità prob(v) con cui avvengono certi eventi v appartenenti ad una lista V. Assumiamo che questa lista di eventi sia un insieme di numeri.
Ricordo che EX denota il valore atteso della variabile casuale. È possibile allora, stimare direttamente la probabilità che un la variabile casuale sia maggiore di un certo numero.
Disuguaglianza di Markov
Sia X una variabile casuale e M un numero. Allora
prob(|X|>=M) =< EX/M
Dimostrazione
Per prima cosa si definisca 1:{|X|>=M} la funzione indicatrice del sottoinsieme dello spazio di probabilità P dove |X| è maggiore o uguale ad M.
Per definizione, nei punti di P dove |X|=M} vale 0, negli altri 1. Per cui M:{|X|>=M} =< |X|.
Integrando nello spazio P a destra e sinistra si ottiene per definizione di valore atteso, si veda la pagina wiki,
Dato che il termine a sinistra altro non è che Mprob(|X| >= M), si ha l'asserto.
Esempio
Come variabile casuale prendiamo l'età raggiunti dagli abitanti di un paese. Supponiamo che il valore medio sia 60 anni. Allora si ottiene la brutale approssimazione
prob(X > 600) =< 0.1
Sarebbe a dire che un abitante ha meno del 10% di probabilità di raggiungere i 600 anni.
Non molto informativo, se non si considera il fatto che non abbiamo fatto alcuna assunzione sulla nostra variabile casuale...
Per dirla in maniera un po' più semplice, anche se più imprecisa, è un elenco delle probabilità prob(v) con cui avvengono certi eventi v appartenenti ad una lista V. Assumiamo che questa lista di eventi sia un insieme di numeri.
Ricordo che EX denota il valore atteso della variabile casuale. È possibile allora, stimare direttamente la probabilità che un la variabile casuale sia maggiore di un certo numero.
Disuguaglianza di Markov
Sia X una variabile casuale e M un numero. Allora
prob(|X|>=M) =< EX/M
Dimostrazione
Per prima cosa si definisca 1:{|X|>=M} la funzione indicatrice del sottoinsieme dello spazio di probabilità P dove |X| è maggiore o uguale ad M.
Per definizione, nei punti di P dove |X|
Integrando nello spazio P a destra e sinistra si ottiene per definizione di valore atteso, si veda la pagina wiki,
Dato che il termine a sinistra altro non è che Mprob(|X| >= M), si ha l'asserto.
Esempio
Come variabile casuale prendiamo l'età raggiunti dagli abitanti di un paese. Supponiamo che il valore medio sia 60 anni. Allora si ottiene la brutale approssimazione
prob(X > 600) =< 0.1
Sarebbe a dire che un abitante ha meno del 10% di probabilità di raggiungere i 600 anni.
Non molto informativo, se non si considera il fatto che non abbiamo fatto alcuna assunzione sulla nostra variabile casuale...
martedì, marzo 18, 2008
Servizio Pubblico - Catene di Markov (II)
In risposta ad un commento, esplicito come si ottiene l'ultima formula in questo post.
Allora, quello che abbiamo a disposizione è una serie di numeri P(t,k) parametrizzati da t (il "tempo") e k (lo "stato"). P(t,k) rappresenta la probabilità che la nostra particella si trovi nello stato k al momento t. In altre parole P(t,k)=P(x(t)=k).
Vogliamo adesso che questa proabilità dipenda solamente dallo stato precedente del sistema, cioè da x(t-1). Ritradotto in formule
P(t,k)=P((x(t)=k)=f(x(t-1)).
Ancora non è preciso, perchè la funzione f non è quantificata*! Quello che vogliamo è che esista una certa funzione f: R --> R tale che P(t,k)=f(x(t-1)).
Nemmeno adesso è preciso, infatti nemmeno lo stato k è quantificato. In realtà vogliamo che per ogni stato k esista una funzione f (che in generale dipende da k!) tale che P(t,k)=f(x(t-1)).
Adesso abbiamo un problema; per ogni k esiste in generale una diversa funzione f. È comodo allora dare a ogni diversa f il nome f_k per specificare di quale delle funzioni stiamo parlando.
Quindi, scrivendo in maniera migliore l'ultima formula del post precedente, abbiamo
Nella formula, P(x(t+1=k | x(t)=h) è la probablità che x sia in k al momento t+1 supposto che si trovava in h al momento t.
*: «non è quantificata» vuol dire che non è specificato se deve esistere una funzione f con tali proprietà, o se tale proprietà deve valere per tutte le funzioni f in una certa classe.
Allora, quello che abbiamo a disposizione è una serie di numeri P(t,k) parametrizzati da t (il "tempo") e k (lo "stato"). P(t,k) rappresenta la probabilità che la nostra particella si trovi nello stato k al momento t. In altre parole P(t,k)=P(x(t)=k).
Vogliamo adesso che questa proabilità dipenda solamente dallo stato precedente del sistema, cioè da x(t-1). Ritradotto in formule
P(t,k)=P((x(t)=k)=f(x(t-1)).
Ancora non è preciso, perchè la funzione f non è quantificata*! Quello che vogliamo è che esista una certa funzione f: R --> R tale che P(t,k)=f(x(t-1)).
Nemmeno adesso è preciso, infatti nemmeno lo stato k è quantificato. In realtà vogliamo che per ogni stato k esista una funzione f (che in generale dipende da k!) tale che P(t,k)=f(x(t-1)).
Adesso abbiamo un problema; per ogni k esiste in generale una diversa funzione f. È comodo allora dare a ogni diversa f il nome f_k per specificare di quale delle funzioni stiamo parlando.
Quindi, scrivendo in maniera migliore l'ultima formula del post precedente, abbiamo
Nella formula, P(x(t+1=k | x(t)=h) è la probablità che x sia in k al momento t+1 supposto che si trovava in h al momento t.
*: «non è quantificata» vuol dire che non è specificato se deve esistere una funzione f con tali proprietà, o se tale proprietà deve valere per tutte le funzioni f in una certa classe.
mercoledì, marzo 12, 2008
Servizio Pubblico - Catene di Markov (I)
Per qualche motivo a me ancora ignoto (o meglio: probabilmente per questo motivo), la maggior parte dei visitatori del blog provenienti da motori di ricerca erano alla ricerca di informazioni su "catene di markov". Per non deludere ulteriormente questi visitatori, ecco un post sulle catene di Markov.
Premetto che Andrey Markov è stato un matematico russo della fine del 1800, membro dell'accademia di San Pietroburgo, allievo di Chebyshev, e con alcuni discendenti abbastanza famosi, come Lebiscovitsch, Sacks e Zygmund. Non entro nei dettagli storici e biografici, che possono essere trovati qui.
Cos'è una catena di Markov? Il caso che considero è quello di una catena a stati finiti.
Supponiamo di avere un oggetto (una particella, una persona, un ente divino) che può trovarsi in diversi stati, che chiameremo k, con k che varia fra 1 e n. Ad esempio, Se l'oggetto in considerazione è una persona, e l'unica informazione che ci interessè la sua età, allora i diversi stati sono numeri naturali, e per andare sul sicuro poniamo n=130.
Quello che vogliamo descrivere è l'evoluzione di questo oggetto: cioè come passa da uno stato all'altro; nelle catene di Markov questi cambiamenti di stato avvengono in step temporali discreti (che chiamiamo t e che è un numero naturale) e in maniera probabilistica. Per tornare al nostro esempio precedente: se fissiamo lo step temporale ad un anno, allora la persona in osservazione passa in ogni step temporale dallo stato k allo stato k+1 con probabilità 1. Se chiamiamo x(t) lo stato del nostro oggetto al tempo t, allora
per ogni t e per ogni k.
Ciò non è veramente probabilitstico (e per altro non si capisce che succede quando x(t)=130 per qualche t, si veda sotto), ma permette di evidenziare un aspetto importante: la probabilità che l'oggetto si trovi in un qualche stato nello step temporale t+1 deve essere 1: gli oggetti non possono essere distrutti in questa descrizione (e anche se lo potessero, si potrebbe correggere il tutto aggiungendo lo stato: oggetto distrutto - questo serve per correggere l'esempio precedente con le età sopra i 130 anni).
Riassumendo: quello che dobbiamo specificare per determinare l'evoluzione temporale di x, è la probabilità P(x(t)=k) che l'oggetto si trovi nello stato k al tempo t.
Introduciamo adesso il concetto fondamentale per una catena di Markov; supponiamo che per k=1, ... , n e t=1,2,... sia definita una famiglia di numeri 0 < P(x(t)=k) < 1 con la proprietà
![\left[\sum_{k=1}^n P(x(t)=k)\right] = 1](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vAwWvXNofD4B59AAUXfg_31QTLe2AWZv_yvO9y2kxQGbaFzcuSbGaaTTHSxaXWCp1V7NzSXuca1RDis1CYAK9LpPVlkkRYy09rsYmUKt6kSFtXIq6N2HXqSxPaTe701T8iRuDZdVqRQXARKhJdSvLpT9ZzsG6ZZhKy4NRLd07Aas5HODs51gBlw6_yF-7CUe7H0G9de0N1UfYt=s0-d)
per ogni t.
Allora la famiglia P(x(t)=k) definisce una catena di Markov omogenea se e solo se esiste una famiglia di vettori f_k=(f_k(1), ... , f_k(n)) tale che
Parlando in italiano, questo vuol dire che la probabilità che x si trovi in k al tempo t+1 dipende solamente da dove x si trovava al tempo t, e non dipende ne dal tempo t, ne' dalla storia di x fino al tempo t-1.
[La prossima volta che ho un po' di tempo, cerco di spiegare il rapporto fra catene di Markov e sistemi dinamici discreti, e poi fra questi e i random walks su grafi].
Premetto che Andrey Markov è stato un matematico russo della fine del 1800, membro dell'accademia di San Pietroburgo, allievo di Chebyshev, e con alcuni discendenti abbastanza famosi, come Lebiscovitsch, Sacks e Zygmund. Non entro nei dettagli storici e biografici, che possono essere trovati qui.
Cos'è una catena di Markov? Il caso che considero è quello di una catena a stati finiti.
Supponiamo di avere un oggetto (una particella, una persona, un ente divino) che può trovarsi in diversi stati, che chiameremo k, con k che varia fra 1 e n. Ad esempio, Se l'oggetto in considerazione è una persona, e l'unica informazione che ci interessè la sua età, allora i diversi stati sono numeri naturali, e per andare sul sicuro poniamo n=130.
Quello che vogliamo descrivere è l'evoluzione di questo oggetto: cioè come passa da uno stato all'altro; nelle catene di Markov questi cambiamenti di stato avvengono in step temporali discreti (che chiamiamo t e che è un numero naturale) e in maniera probabilistica. Per tornare al nostro esempio precedente: se fissiamo lo step temporale ad un anno, allora la persona in osservazione passa in ogni step temporale dallo stato k allo stato k+1 con probabilità 1. Se chiamiamo x(t) lo stato del nostro oggetto al tempo t, allora
per ogni t e per ogni k.
Ciò non è veramente probabilitstico (e per altro non si capisce che succede quando x(t)=130 per qualche t, si veda sotto), ma permette di evidenziare un aspetto importante: la probabilità che l'oggetto si trovi in un qualche stato nello step temporale t+1 deve essere 1: gli oggetti non possono essere distrutti in questa descrizione (e anche se lo potessero, si potrebbe correggere il tutto aggiungendo lo stato: oggetto distrutto - questo serve per correggere l'esempio precedente con le età sopra i 130 anni).
Riassumendo: quello che dobbiamo specificare per determinare l'evoluzione temporale di x, è la probabilità P(x(t)=k) che l'oggetto si trovi nello stato k al tempo t.
Introduciamo adesso il concetto fondamentale per una catena di Markov; supponiamo che per k=1, ... , n e t=1,2,... sia definita una famiglia di numeri 0 < P(x(t)=k) < 1 con la proprietà
per ogni t.
Allora la famiglia P(x(t)=k) definisce una catena di Markov omogenea se e solo se esiste una famiglia di vettori f_k=(f_k(1), ... , f_k(n)) tale che
Parlando in italiano, questo vuol dire che la probabilità che x si trovi in k al tempo t+1 dipende solamente da dove x si trovava al tempo t, e non dipende ne dal tempo t, ne' dalla storia di x fino al tempo t-1.
[La prossima volta che ho un po' di tempo, cerco di spiegare il rapporto fra catene di Markov e sistemi dinamici discreti, e poi fra questi e i random walks su grafi].
martedì, ottobre 16, 2007
sinapsi, catene di markov multiple e limiti secondo cesaro
i have never done anything 'useful'. no discovery of mine has made, or is likely to make, directly or indirectly, for good or ill, the least difference to the amenity of the world
g. h. hardy
in questi giorni discutevo con un ragazzo di friburgo, che sta studiando un modello di sinapsi per il riconoscimento locale di correlazioni. fra gli altri problemi che deve risolvere, me ne ha presentato uno, per lui statistico, per me di analisi funzionale, che vi presento in una forma lievemente modificata.
il nostro scenario è il seguente: ci sono una certa quantità di particelle che si muovono in uno spazio-tempo discreto. ad ogni step temporale si muovono dallo stato i allo stato j con probabilità a_{ij}. con questi a_{ij} si può formare una matrice, detta matrice di transizione. la nostra situazione è però un po' più complicata. ad ogni step temporale, si sceglie la matrice di transizione da un insieme di M matrici transizione, secondo un certo vettore di probabilità p=(p_k). per comodità diamo un nome a queste matrici di transizione
la domanda che ci poniamo: esiste, ed in che senso, una distribuzione limite delle particelle? più precisamente ci si chiede se il limite
esista ed a che condizioni.
se avessimo a che fare con una singola matrice di transizione, assumendo che essa sia primitiva, cioè che le sue potenze convergano ad una proiezione unidimensionale, cioè che l'unico autovalore sul cerchio unitario sia 1 e che abbia dimensione dell'autospazio relativo pari a 1, allora si dimostra facilmente che la probabilità che una particella x si trovi nello stato j converge verso
qui v è uno qualsiasi degli autovettori nell'autospazio relativo all'autovalore 1. si potrebbe dunque pensare che nel caso di M matrici di transizione il tutto si comporti come se la matrice di transizione fosse
qui p è il vettore di probabilità le cui componenti p_k sono le probabilità con cui A_k viene scelta in uno step temporale.
simulando al computer (per un numero alto ma fisso di particelle e di iterazioni) questo sistema dinamico discreto abbiamo subito notato che non erà così, ma che lo era solo se si faceva la media di varie simulazioni. mentro ero in bicicletta ho capito perchè: facendo la media su varie simulazioni non facevamo altro che passare dal limite della distribuzione di probabilità, che evidentemente non esiste a a causa delle oscillazioni dovute al passare da una catena di markov all'altra, al limite secondo cesaro che, altrettanto ovviamente, esiste.
la cosa più divertente è che quando ho tentato di spiegare al mio collega, fisico, che stavamo tentando di calcolare un limite che non esiste, lui non riusciva a capacitarsi di questo fenomeno...
g. h. hardy
in questi giorni discutevo con un ragazzo di friburgo, che sta studiando un modello di sinapsi per il riconoscimento locale di correlazioni. fra gli altri problemi che deve risolvere, me ne ha presentato uno, per lui statistico, per me di analisi funzionale, che vi presento in una forma lievemente modificata.
il nostro scenario è il seguente: ci sono una certa quantità di particelle che si muovono in uno spazio-tempo discreto. ad ogni step temporale si muovono dallo stato i allo stato j con probabilità a_{ij}. con questi a_{ij} si può formare una matrice, detta matrice di transizione. la nostra situazione è però un po' più complicata. ad ogni step temporale, si sceglie la matrice di transizione da un insieme di M matrici transizione, secondo un certo vettore di probabilità p=(p_k). per comodità diamo un nome a queste matrici di transizione
la domanda che ci poniamo: esiste, ed in che senso, una distribuzione limite delle particelle? più precisamente ci si chiede se il limite
esista ed a che condizioni.
se avessimo a che fare con una singola matrice di transizione, assumendo che essa sia primitiva, cioè che le sue potenze convergano ad una proiezione unidimensionale, cioè che l'unico autovalore sul cerchio unitario sia 1 e che abbia dimensione dell'autospazio relativo pari a 1, allora si dimostra facilmente che la probabilità che una particella x si trovi nello stato j converge verso
qui v è uno qualsiasi degli autovettori nell'autospazio relativo all'autovalore 1. si potrebbe dunque pensare che nel caso di M matrici di transizione il tutto si comporti come se la matrice di transizione fosse
qui p è il vettore di probabilità le cui componenti p_k sono le probabilità con cui A_k viene scelta in uno step temporale.
simulando al computer (per un numero alto ma fisso di particelle e di iterazioni) questo sistema dinamico discreto abbiamo subito notato che non erà così, ma che lo era solo se si faceva la media di varie simulazioni. mentro ero in bicicletta ho capito perchè: facendo la media su varie simulazioni non facevamo altro che passare dal limite della distribuzione di probabilità, che evidentemente non esiste a a causa delle oscillazioni dovute al passare da una catena di markov all'altra, al limite secondo cesaro che, altrettanto ovviamente, esiste.
la cosa più divertente è che quando ho tentato di spiegare al mio collega, fisico, che stavamo tentando di calcolare un limite che non esiste, lui non riusciva a capacitarsi di questo fenomeno...
Iscriviti a:
Post (Atom)
