Cadeia de Markov

A cadeia de Markov é ferramenta que modela uma grande variedade de situações recorrentes em biologia, economia, química, engenharia e física envolvendo processos estocásticos . Nesses experimentos, a predição do estado seguinte depende apenas do estado atual. Esta propriedade é chamada de memória markoviana (ou falta de memória).

Considere a seguinte distribuição de probabilidade de uma população na zona urbana e zona rural:  

vo = [0.6 0.4]

Este vetor indica que 60% da população vive na zona urbana e 40% da população vive na zona rural.

O próximo estado pode ser encontrado aplicando uma matriz de transição  (matriz estocástica) é uma matriz quadrada com duas características:
1) todas as entradas são não negativas
2) todas as colunas tem soma igual a 1.

Por ano, 5% da população sai da zona urbana para a zona rural e 3% da população sai da zona rural para a zona urbana.

  sai urbana   rural
P = [ .95      0.03]urbana
      [ .05      0.97]rural
                           chega  


Podemos calcular a nova distribuição da população aplicando a matriz de transição:

Pvo = [0.95 0.03][0.6] = [0.582]
          [0.05 0.97][0.4]    [0.418]


A cadeia de Markov é a sequência de vetores de distribuição de probabilidade v0,v1,v2,..., com uma matriz de transição da seguinte maneira:

$v_{1} = Pv_0$
$v_2 = Pv_1$
$v_3 = Pv_2$
...
$v_n = Pv_{n-1}$

$v_n = P^{n} v_0$

Matriz de transição estacionária

A cadeia de Markov pode ser utilizada para encontrar . A matriz $P^{k}$ é a matriz de transição em k passos. A matriz $P^{k}$ converge para uma matriz estacionária. No nosso algoritmo, vamos considerar
um valor de k suficientemente grande para obter a matriz estacionária.

Primeiramente, temos a função que aloca uma matriz quadrada dinamicamente (alocam), a função multiplica que faz a multiplicação entre duas matrizes (a e b) devolvendo uma matriz c e a função que executa a exponenciação rápida de uma matriz $A^{n}$

double ** alocam(int n){
 int i;
 double ** p = (double **)malloc(n*sizeof(double *));
 
 for(i=0;i<n;i++)
  p[i] = (double *) malloc(n*sizeof(double));
 return p;
}

void multiplica(double  **a, double  **b, double  **c, int n){
int i,j,k;
 for(i=0;i<n;i++){

  for(j=0;j<n;j++){
 c[i][j] = 0.0;     
 for(k=0;k<n;k++){
   c[i][j] += a[i][k]*b[k][j];
 }
  }
 }
}
void exp(double **a, double **b,int n, int m){
  int i,j;
  double ** c = alocam(n);
  if(m==0){
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        if(i==j) b[i][j] = 1.0;
        else b[i][j] = 0.0;
  }else if(m==1){
 for(i=0;i<n;i++)
   for(j=0;j<n;j++)
     b[i][j] = a[i][j];
   }else if(m%2==0){
 exp(a,c,n,m/2);
 multiplica(c,c,b,n);
   }else if(m%2==1){
 exp(a,c,n,m-1);
 multiplica(c,a,b,n);
   }
   free(c);
}

Agora, precisamos apenas inicializar a matriz de transição e depois calcular $A^n$ para n suficientemente grande.

int main(){
 int n,s,b,c;
 int i,j,k; 
 double *v0;
 double *vf;

 m = alocam(2);
 r = alocam(2);
 v0 = aloca(2);
 vf = aloca(2);
 
 m[0][0] = 0.95;
 m[0][1] = 0.03;
 m[1][0] = 0.05;
 m[1][1] = 0.97;
 
 v0[0] = 0.4;
 v0[1] = 0.6;
 
 printf("Matriz Inicial\n"); 
 for(i=0;i<2;i++){
  for(j=0;j<2;j++){
   printf("%lf ",m[i][j]);
  }
  printf("\n");
 }
 printf("\n");
 exp(m,r,2,10000); 
 
 printf("Matriz Estacionaria\n");
 for(i=0;i<2;i++){
  for(j=0;j<2;j++){
   printf("%lf ",r[i][j]);
  }
  printf("\n");
 }
 printf("\n");
 free(m);
 free(r);
}

Matriz Inicial
0.950000 0.030000
0.050000 0.970000

Matriz Estacionaria
0.375000 0.375000
0.625000 0.625000


Podemos concluir que a longo prazo, a população urbana será 37,5% e a população rural será 62,5% considerando a manutenção dessas taxas.


Outra maneira de encontrar o estado estacionário da cadeia de Markov é resolver a seguinte equação:

Px = x
Px-x=0
Px-Ix=0
(P-I)x=0


Você pode resolver os seguintes problemas com essa ideia:
http://br.spoj.pl/problems/VAMPIROS/
http://www.urionlinejudge.com.br/urionlinejudge/problems/view/1227