Tema 11 - Dinàmica de sistemes - Mètode estocàstic - Les cadenes de Markov PDF

Preview

Summary

T11 – Mètode estocàstic – Les cadenes de Markov Dinàmica sist. 1. Introducció al càlcul matricial Abans de parlar del mètode estocàstic i de les cadenes de Markov cal tenir en compte una sèrie de conceptes relatius a les matemàtiques de les matrius. - Matriu: ordenació rectangular de números. Vector...

Description

T11 – Mètode estocàstic – Les cadenes de Markov Din Dinàmi àmica sist.. àmi ca sist 1. Introducció al càlcul matricial Abans de parlar del mètode estocàstic i de les cadenes de Markov cal tenir en compte una sèrie de conceptes relatius a les matemàtiques de les matrius. -

Matriu: ordenació rectangular de números. Vector: element d’un espai vectorial. Vector fix (𝑢) d’una matriu (𝐴): aquell que compleix 𝑢 × 𝐴 = 𝑢. Vector probabilístic: vector les components del qual són totes positives i sumen 1. Conceptualment, representa una distribució de probabilitats. Matriu estocàstica: matriu les files de la qual són vectors probabilístics. Matriu estocàstica regular. Una matriu 𝑃 és estocàstica regular si tots els elements d’una potència de la matriu 𝑃𝑛 són positius. Matriu estocàstica regular

0 𝑃2 = ( 0,5

0 𝑃=( 0,5

1 0 )( 0,5 0,5

1 ) 0,5

0,5 1 )=( 0,25 0,5

Matriu no estocàstica regular

0,5 ) 0,75

𝑃2 és positiva en cada element ⇓ 𝑃 és regular

1 𝑃2 = ( 0,5

1 𝑃=( 0,5

1 0 )( 0,5 0,5

0 ) 0,5

0 1 )=( 0,5 0,75

0 ) 0,25

𝑃2 no és positiva en cada element (hi ha zeros) ⇓ 𝑃 no és regular

Els vectors fixos i les matrius estocàstiques regulars compleixen una sèrie de Teoremes. Sigui 𝑃 una matriu estocàstica regular. Aleshores:

Pàgina

1

1) 𝑃 té un vector fix (probabilístic) 𝑡, totes les components del qual són positives. 2) La successió 𝑃, 𝑃2 , 𝑃3 , … , 𝑃𝑛 de potències de 𝑃 s’aproxima a la matriu 𝑇, les files de la qual són el vector fix. 3) Si 𝑝 és un vector probabilístic de la matriu 𝑃, la successió 𝑝𝑃, 𝑝𝑃 2 , 𝑝𝑃3 , … , 𝑝𝑃 𝑛 s’aproxima al vector fix 𝑡.

En Pere de sa Somera

T11 – Mètode estocàstic – Les cadenes de Markov Din Dinàmi àmica sist.. àmi ca sist 2. Les cadenes de Markov Una cadena de Markov, que rep el seu nom del matemàtic rus Andrei Markov (18561922), és una sèrie d'esdeveniments, en la qual la probabilitat que passi un esdeveniment depèn de l'esdeveniment immediat anterior. Els esdeveniments (o resultats) satisfan les següents propietats: -

-

Cada resultat pertany a un conjunt finit de resultats, {𝑎1 , 𝑎2 , 𝑎3 , … , 𝑎𝑛 } , anomenat espai d’estats del sistema. Si el resultat de la prova 𝑛-èsima és 𝑎𝑖 , es considera que el sistema està en l’estat 𝑎𝑖 en la prova 𝑛-èsima. El resultat d’una prova depèn del resultat de la prova immediatament anterior (en cadenes de Markov d’ordre 1), però no d’altres resultats anteriors. Per a cada parell d’estats ( 𝑎𝑖 , 𝑎𝑗 ) s’estableix la probabilitat 𝑝𝑖𝑗 que 𝑎𝑗 ocorri immediatament després de 𝑎𝑖 . Els elements 𝑝𝑖𝑗 són probabilitats de transició, i són els elements d’una matriu de Markov 𝑃 (és una matriu estocàstica). 𝑝11 𝑃=( ⋮ 𝑝𝑛1

⋯ 𝑝1𝑛 𝑝𝑖𝑗 ⋮ ) ⋯ 𝑝𝑛𝑛

𝑝𝑖𝑗 : 𝑎𝑖 → 𝑎𝑗

L’ordre d’una cadena de Markov és la dependència del número de resultats anteriors en el resultat d’ordre un. Una cadena de Markov és d’ordre 0 si no hi ha dependència entre els resultats, d’ordre 1 si el resultat d’una prova depèn del resultat immediatament anterior, d’ordre 2 si el resultat d’una prova depèn dels 2 resultats anteriors... Els conceptes bàsics de què es parla en treballar amb cadenes de Markov són: -

Vectors. Són una distribució de probabilitats. Element d’un vector. Es defineix com la probabilitat que la variable prengui un valor determinat en un moment determinat. Matriu de la cadena de Markov. És una matriu de probabilitats de transició. Element de la matriu. Es defineix com la probabilitat de transició entre dos estats de l’espai d’estats. És una probabilitat condicionada.

Concepte de probabilitat condicionada

La probabilitat que una variable prengui el valor 𝑖 en un temps 𝑡 s’escriu com 𝑝(𝑖, 𝑡). Com que parlam de distribució de probabilitats, s’ha de complir que: ∑ 𝑝(𝑖, 𝑡)= 1 𝑖

𝑝(𝑖2 , 𝑡2 ) = 𝑝(𝑖1 , 𝑡1 ) × 𝑝(𝑖2 , 𝑡2 | 𝑖1 , 𝑡1 )

En Pere de sa Somera

Pàgina

La probabilitat que en un temps 𝑡2 ens trobem en un estat 𝑖2 és igual al producte de la probabilitat que en un temps 𝑡1 ens trobem en un estat 𝑖1 i de la probabilitat condicionada de passar de l’estat 𝑖2 en 𝑡2 si ens trobam en l’estat 𝑖1 en 𝑡1 :

2

Parlam de probabilitat condicionada en referir-nos a la probabilitat que ocorri 𝐴 si ens trobam a 𝐵. Això s’escriu com 𝑝(𝐴|𝐵).

T11 – Mètode estocàstic – Les cadenes de Markov Din Dinàmi àmica sist.. àmi ca sist Probabilitats de transició superiors

Com hem definit, si 𝑃 és la matriu estocàstica d’una cadena de Markov, l’element 𝑝𝑖𝑗 és la probabilitat que el sistema canviï de l’estat 𝑎𝑖 a l’estat 𝑎𝑗 en un pas.

Tanmateix, podem calcular la matriu de transició en 𝑛 passos, definint-la com la potència 𝑛-èsima de la matriu 𝑃. Obtenim així la matriu 𝑃𝑛 , que és la matriu estocàstica de la cadena de Markov d’ordre 𝑛.

A més a més, si 𝑝(0) és la distribució de probabilitat en un temps (inicial), aleshores la distribució de probabilitat després d’un pas, 𝑝(1), es calcula com: 𝑝(1) = 𝑝(0)𝑃

La distribució de probabilitat en un pas determinat (𝑛) es pot calcular o bé multiplicant la distribució de probabilitat en el pas anterior (𝑝(𝑛−1) ) per la matriu 𝑃, o bé multiplicant la distribució de probabilitat inicial (𝑝(0)) per la respectiva potència de 𝑃 (𝑃𝑛 ).

Distribució estacionària i estat absorbent

Considerant 𝑃 la matriu estocàstica de transició d’una cadena de Markov la probabilitat, a la llarga, que el sistema estigui en l’estat 𝑎𝑖 és igual a la component 𝑡𝑖 del vector fix ( 𝑡 ). Per tant, podem dir que el vector fix representa la distribució estacionària de la cadena de Markov. Per altra banda, si un estat entra en un estat i s ’hi queda es diu que aquest és un estat absorbent. Si 𝑎𝑖 és un estat absorbent d’una cadena de Markov de matriu estocàstica 𝑃, la probabilitat de transició de 𝑎𝑖 a 𝑎𝑗 és zero (𝑝𝑖𝑗 = 0). En conseqüència, 𝑃 no és regular.

Pàgina

3

Si una matriu estocàstica 𝑃 té un 1 en la diagonal principal (indicador de la presència d’un estat absorbent), aleshores 𝑃 no és regular.

En Pere de sa Somera...