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
