Cadeia de Markov
Minha área de pesquisa no mestrado envolve equações diferenciais estocásticas em que usamos também as ideias da cadeia de Markov. Porém para entender, mesmo que em nível introdutório, sobre esse assunto, torna-se necessário saber sobre algumas teorias matemáticas básicas. Tentei resumir em palavras e simplificar ao máximo possível para que o leitor com pouca afinidade a matemática consiga entender a ideia principal desse tema que é tão fascinante para mim, segue abaixo as teorias que dão base as cadeias de Markov.
Teoria da probabilidade: É o ramo da matemática expressa em axiomas que formalizam a probabilidade em termos de um espaço de probabilidade, que atribui as ocorrências possíveis em medidas de valores entre 0 e 1 (medida de probabilidade), a um conjunto de resultados denominado espaço amostral.
Os assuntos centrais na teoria da probabilidade incluem variáveis aleatórias discretas e contínuas, distribuições de probabilidade e processos estocásticos, que fornecem abstrações matemáticas de processos não determinísticos ou incertos, e também observar as quantidades de medidas que podem ser ocorrências únicas ou evoluir ao longo do tempo de forma aleatória.
Probabilidade condicional: É uma medida da probabilidade de um evento (ocorrendo alguma situação particular), dado que (por suposição, presunção, asserção ou evidência) ocorreu outro evento. Se o evento de interesse é A e o evento B é conhecido ou assumido como tendo ocorrido, "a probabilidade condicional de A dado B ", ou "a probabilidade de A sob a condição B ", é geralmente escrita como P ( A | B ), ou às vezes P B ( A) ou P ( A / B ).
Lei da probabilidade total: É uma regra fundamental que relaciona as probabilidades marginais às probabilidades condicionais . Expressa a probabilidade total de um resultado que pode ser realizado através de vários eventos distintos.
Variável aleatória: É uma variável cujo valor é definido como o resultado de um fenômeno aleatório. Observe também que o espaço de resultados possíveis de uma variável aleatória pode ser discreto ou contínuo: por exemplo, uma variável aleatória normal é contínua, enquanto uma variável aleatória de poisson é discreta.
Podemos então definir um processo aleatório(também chamado de processo estocástico) como uma coleção de variáveis aleatórias indexadas por um conjunto T que freqüentemente representam instantes diferentes de tempo. Sendo os dois casos mais comuns: T é um conjunto de números naturais (processo aleatório de tempo discreto) ou T é um conjunto de números reais (processo aleatório de tempo contínuo).
Propriedade de Markov: Diz que em qualquer momento dado, a distribuição condicional de estados futuros, dados os estados presentes e passados, depende apenas do estado presente e não dos estados passados (propriedade do processo sem memória )
Processo de Markov: Diz que para um dado histórico (onde estou agora e onde eu estava antes), a distribuição de probabilidade para o próximo estado (onde vou a seguir) depende apenas do estado atual. Não considerando os estados passados.
Com essas definições em mente, pode-se avançar na ideia da cadeia de Markov, onde temos que é um processo de Markov com tempo discreto e espaço de estados discretos. Assim, uma cadeia de Markov é uma seqüência discreta de estados, cada um extraído de um espaço discreto (finito ou não) e que segue a propriedade Markov.
Observe que a caracterização completa de um processo aleatório de tempo discreto que não verifica a propriedade Markov pode ser trabalhosa: a distribuição de probabilidade em um determinado momento pode depender de um ou vários instantes de tempo passado e / ou futuro. Todas essas possíveis dependências de tempo tornam qualquer descrição adequada do processo potencialmente difícil.
No entanto, graças à propriedade Markov, a dinâmica de eventos que seguem a cadeia de Markov é muito fácil de definir. De fato, precisamos especificar apenas duas coisas: uma distribuição de probabilidade inicial (que é uma distribuição de probabilidade para o instante de tempo n = 0) e um kernel de probabilidade de transição (que dá as probabilidades de cada estado, no tempo n + 1, sucede a outro, no tempo n). Com os dois objetos anteriores conhecidos, a dinâmica probabilística do processo é bem definida. De fato, a probabilidade de qualquer realização do processo pode então ser computada de maneira recorrente.
Propriedades da cadeia de Markov
Irredutibilidade, periodicidade, transitoriedade e recorrência:
Uma cadeia de Markov é irredutível se for possível alcançar qualquer estado a partir de qualquer outro estado (não necessariamente em um único intervalo de tempo).
Um estado tem o período k se, ao sair dele, qualquer retorno a esse estado exigir um múltiplo de k etapas de tempo (k é o maior divisor comum de todo o comprimento possível do caminho de retorno). Se k = 1, então o estado é dito aperiódico e toda a cadeia de Markov é aperiódica se todos os estados forem aperiódicos.
Para uma cadeia de Markov irredutível, podemos também mencionar o fato de que se um estado é aperiódico, então todos os estados são aperiódicos.
Um estado é transitório se, quando sairmos desse estado, houver uma probabilidade diferente de zero de nunca mais voltarmos a ele. Inversamente, um estado é recorrente se soubermos que retornaremos a esse estado, no futuro, com probabilidade 1 depois de deixá-lo.
Distribuição estacionária, comportamento limitante e ergodicidade:
Por definição, uma distribuição de probabilidade é dita estacionária quando não evolui ao longo do tempo. Portanto, se a distribuição inicial for uma distribuição estacionária, ela permanecerá a mesma para todas as etapas de tempo futuras.
Outra propriedade interessante relacionada à distribuição de probabilidade estacionária é que se a cadeia é recorrente positiva e aperiódica então, não importa quais sejam as probabilidades iniciais, a distribuição de probabilidade da cadeia converge quando o tempo passa para o infinito: a cadeia é dita ter uma distribuição limitante isso nada mais é do que a distribuição estacionária.
Finalmente, a ergodicidade é outra propriedade interessante relacionada ao comportamento de uma cadeia de Markov. Se uma cadeia de Markov é irredutível, então também dizemos que esta cadeia é “ergódica”, pois verifica o seguinte teorema ergódico. Suponha que temos um processo f (.) Que possui espaço amostral de E até os reais. Podemos definir o valor médio deste processo ao longo de uma dada trajetória (média temporal).O teorema ergódico nos diz que a média temporal quando a trajetória se torna infinitamente longa é igual à média espacial (ponderada pela distribuição estacionária).
Dito de outra maneira, diz que, no limite, o comportamento inicial da trajetória se torna insignificante e apenas o comportamento estacionário de longo prazo realmente importa ao se computar a média temporal.
Resumo:
Para concluir, vale a pena enfatizar como as cadeias de Markov são úteis para modelagem de problemas ao lidar com processos dinâmicos e aleatórias. Devido às suas propriedades elas são usadas em vários campos, como a teoria das filas (otimizando o desempenho das redes de telecomunicações, onde as mensagens devem competir por recursos limitados e enfileiradas quando todos os recursos já estão alocados), estatísticas (o conhecido A técnica de geração de variáveis aleatórias de cadeia Monte Carlo baseia-se em cadeias de Markov), biologia (modelagem da evolução de populações biológicas), ciência da computação (modelos ocultos de Markov são ferramentas importantes na teoria da informação e reconhecimento de fala) e outros.
Obviamente, tanto o conteúdo quanto as possibilidades oferecidas pelas cadeias de Markov em termos de modelação matemática está muito aquém do que foi apresentado nesta introdução modesta e, portanto, existe ainda muitos assuntos que são essenciais para esse estudo mas que não foram abordados aqui neste post, como a noção de filtração por exemplo, que se encaixa nesse tema, porém está além do escopo introdutório. Mas espero que esteja bem explicado e que eu tenha conseguido passar a ideia de forma organizada, concisa e certeira.
Teoria da probabilidade: É o ramo da matemática expressa em axiomas que formalizam a probabilidade em termos de um espaço de probabilidade, que atribui as ocorrências possíveis em medidas de valores entre 0 e 1 (medida de probabilidade), a um conjunto de resultados denominado espaço amostral.
Os assuntos centrais na teoria da probabilidade incluem variáveis aleatórias discretas e contínuas, distribuições de probabilidade e processos estocásticos, que fornecem abstrações matemáticas de processos não determinísticos ou incertos, e também observar as quantidades de medidas que podem ser ocorrências únicas ou evoluir ao longo do tempo de forma aleatória.
Probabilidade condicional: É uma medida da probabilidade de um evento (ocorrendo alguma situação particular), dado que (por suposição, presunção, asserção ou evidência) ocorreu outro evento. Se o evento de interesse é A e o evento B é conhecido ou assumido como tendo ocorrido, "a probabilidade condicional de A dado B ", ou "a probabilidade de A sob a condição B ", é geralmente escrita como P ( A | B ), ou às vezes P B ( A) ou P ( A / B ).
Lei da probabilidade total: É uma regra fundamental que relaciona as probabilidades marginais às probabilidades condicionais . Expressa a probabilidade total de um resultado que pode ser realizado através de vários eventos distintos.
Variável aleatória: É uma variável cujo valor é definido como o resultado de um fenômeno aleatório. Observe também que o espaço de resultados possíveis de uma variável aleatória pode ser discreto ou contínuo: por exemplo, uma variável aleatória normal é contínua, enquanto uma variável aleatória de poisson é discreta.
Podemos então definir um processo aleatório(também chamado de processo estocástico) como uma coleção de variáveis aleatórias indexadas por um conjunto T que freqüentemente representam instantes diferentes de tempo. Sendo os dois casos mais comuns: T é um conjunto de números naturais (processo aleatório de tempo discreto) ou T é um conjunto de números reais (processo aleatório de tempo contínuo).
Propriedade de Markov: Diz que em qualquer momento dado, a distribuição condicional de estados futuros, dados os estados presentes e passados, depende apenas do estado presente e não dos estados passados (propriedade do processo sem memória )
Processo de Markov: Diz que para um dado histórico (onde estou agora e onde eu estava antes), a distribuição de probabilidade para o próximo estado (onde vou a seguir) depende apenas do estado atual. Não considerando os estados passados.
Com essas definições em mente, pode-se avançar na ideia da cadeia de Markov, onde temos que é um processo de Markov com tempo discreto e espaço de estados discretos. Assim, uma cadeia de Markov é uma seqüência discreta de estados, cada um extraído de um espaço discreto (finito ou não) e que segue a propriedade Markov.
Observe que a caracterização completa de um processo aleatório de tempo discreto que não verifica a propriedade Markov pode ser trabalhosa: a distribuição de probabilidade em um determinado momento pode depender de um ou vários instantes de tempo passado e / ou futuro. Todas essas possíveis dependências de tempo tornam qualquer descrição adequada do processo potencialmente difícil.
No entanto, graças à propriedade Markov, a dinâmica de eventos que seguem a cadeia de Markov é muito fácil de definir. De fato, precisamos especificar apenas duas coisas: uma distribuição de probabilidade inicial (que é uma distribuição de probabilidade para o instante de tempo n = 0) e um kernel de probabilidade de transição (que dá as probabilidades de cada estado, no tempo n + 1, sucede a outro, no tempo n). Com os dois objetos anteriores conhecidos, a dinâmica probabilística do processo é bem definida. De fato, a probabilidade de qualquer realização do processo pode então ser computada de maneira recorrente.
Propriedades da cadeia de Markov
Irredutibilidade, periodicidade, transitoriedade e recorrência:
Uma cadeia de Markov é irredutível se for possível alcançar qualquer estado a partir de qualquer outro estado (não necessariamente em um único intervalo de tempo).
Um estado tem o período k se, ao sair dele, qualquer retorno a esse estado exigir um múltiplo de k etapas de tempo (k é o maior divisor comum de todo o comprimento possível do caminho de retorno). Se k = 1, então o estado é dito aperiódico e toda a cadeia de Markov é aperiódica se todos os estados forem aperiódicos.
Para uma cadeia de Markov irredutível, podemos também mencionar o fato de que se um estado é aperiódico, então todos os estados são aperiódicos.
Um estado é transitório se, quando sairmos desse estado, houver uma probabilidade diferente de zero de nunca mais voltarmos a ele. Inversamente, um estado é recorrente se soubermos que retornaremos a esse estado, no futuro, com probabilidade 1 depois de deixá-lo.
Distribuição estacionária, comportamento limitante e ergodicidade:
Por definição, uma distribuição de probabilidade é dita estacionária quando não evolui ao longo do tempo. Portanto, se a distribuição inicial for uma distribuição estacionária, ela permanecerá a mesma para todas as etapas de tempo futuras.
Outra propriedade interessante relacionada à distribuição de probabilidade estacionária é que se a cadeia é recorrente positiva e aperiódica então, não importa quais sejam as probabilidades iniciais, a distribuição de probabilidade da cadeia converge quando o tempo passa para o infinito: a cadeia é dita ter uma distribuição limitante isso nada mais é do que a distribuição estacionária.
Finalmente, a ergodicidade é outra propriedade interessante relacionada ao comportamento de uma cadeia de Markov. Se uma cadeia de Markov é irredutível, então também dizemos que esta cadeia é “ergódica”, pois verifica o seguinte teorema ergódico. Suponha que temos um processo f (.) Que possui espaço amostral de E até os reais. Podemos definir o valor médio deste processo ao longo de uma dada trajetória (média temporal).O teorema ergódico nos diz que a média temporal quando a trajetória se torna infinitamente longa é igual à média espacial (ponderada pela distribuição estacionária).
Dito de outra maneira, diz que, no limite, o comportamento inicial da trajetória se torna insignificante e apenas o comportamento estacionário de longo prazo realmente importa ao se computar a média temporal.
Resumo:
- Processos aleatórios são coleções de variáveis aleatórias, muitas vezes indexadas ao longo do tempo (os índices geralmente representam tempo discreto ou contínuo)
- Para um processo aleatório, a propriedade Markov diz que, dado o presente, a probabilidade do futuro é independente do passado (essa propriedade também é chamada de "propriedade sem memória").
- Cadeia de Markov de tempo discreto são processos aleatórios com índices de tempo discretos e que verificam a propriedade de Markov
- A propriedade Markov das cadeias de Markov torna o estudo desses processos muito mais tratável e permite derivar alguns resultados explícitos interessantes (tempo médio de recorrência, distribuição estacionária ...)
Para concluir, vale a pena enfatizar como as cadeias de Markov são úteis para modelagem de problemas ao lidar com processos dinâmicos e aleatórias. Devido às suas propriedades elas são usadas em vários campos, como a teoria das filas (otimizando o desempenho das redes de telecomunicações, onde as mensagens devem competir por recursos limitados e enfileiradas quando todos os recursos já estão alocados), estatísticas (o conhecido A técnica de geração de variáveis aleatórias de cadeia Monte Carlo baseia-se em cadeias de Markov), biologia (modelagem da evolução de populações biológicas), ciência da computação (modelos ocultos de Markov são ferramentas importantes na teoria da informação e reconhecimento de fala) e outros.
Obviamente, tanto o conteúdo quanto as possibilidades oferecidas pelas cadeias de Markov em termos de modelação matemática está muito aquém do que foi apresentado nesta introdução modesta e, portanto, existe ainda muitos assuntos que são essenciais para esse estudo mas que não foram abordados aqui neste post, como a noção de filtração por exemplo, que se encaixa nesse tema, porém está além do escopo introdutório. Mas espero que esteja bem explicado e que eu tenha conseguido passar a ideia de forma organizada, concisa e certeira.
Comentários
Postar um comentário