Matriz estocástica - Stochastic matrix

Em matemática, uma matriz estocástica é uma matriz quadrada usada para descrever as transições de uma cadeia de Markov . Cada uma de suas entradas é um número real não negativo que representa uma probabilidade . Também é chamada de matriz de probabilidade , matriz de transição , matriz de substituição ou matriz de Markov . A matriz estocástica foi desenvolvida por Andrey Markov no início do século 20 e encontrou uso em uma ampla variedade de campos científicos, incluindo teoria da probabilidade , estatística, finanças matemáticas e álgebra linear , bem como ciência da computação e genética populacional . Existem várias definições e tipos diferentes de matrizes estocásticas:

Uma matriz estocástica direita é uma matriz quadrada real, com cada linha somando 1.
Uma matriz estocástica à esquerda é uma matriz quadrada real, com cada coluna somando 1.
Uma matriz duplamente estocástica é uma matriz quadrada de números reais não negativos com cada linha e coluna somando 1.

Na mesma linha, pode-se definir um vetor estocástico (também chamado de vetor de probabilidade ) como um vetor cujos elementos são números reais não negativos que somam 1. Assim, cada linha de uma matriz estocástica direita (ou coluna de uma matriz estocástica esquerda) é um vetor estocástico. Uma convenção comum na literatura matemática da língua inglesa é usar vetores linha de probabilidades e matrizes estocásticas direitas em vez de vetores coluna de probabilidades e matrizes estocásticas esquerdas; este artigo segue essa convenção.

História

Andrey Markov em 1886

A matriz estocástica foi desenvolvida juntamente com a cadeia de Markov por Andrey Markov , um matemático russo e professor da Universidade de São Petersburgo que publicou pela primeira vez sobre o assunto em 1906. Seus usos iniciais pretendidos eram para análise linguística e outros assuntos matemáticos como embaralhamento de cartas , mas ambos Cadeias e matrizes de Markov rapidamente encontraram uso em outros campos.

Matrizes estocásticas foram posteriormente desenvolvidas por estudiosos como Andrey Kolmogorov , que expandiram suas possibilidades permitindo processos de Markov em tempo contínuo. Na década de 1950, artigos usando matrizes estocásticas apareceram nas áreas de econometria e teoria de circuitos . Na década de 1960, as matrizes estocásticas apareceram em uma variedade ainda mais ampla de trabalhos científicos, da ciência comportamental à geologia e ao planejamento residencial . Além disso, muitos trabalhos matemáticos também foram realizados ao longo dessas décadas para melhorar a gama de usos e a funcionalidade da matriz estocástica e dos processos markovianos de maneira mais geral.

Da década de 1970 até o presente, as matrizes estocásticas encontraram uso em quase todos os campos que requerem análise formal, da ciência estrutural ao diagnóstico médico e gestão de pessoal . Além disso, as matrizes estocásticas encontraram amplo uso na modelagem de mudanças de terras , geralmente sob o termo matriz de Markov.

Definição e propriedades

Uma matriz estocástica descreve uma cadeia de Markov X t ao longo de um finito estado espaço S com cardinalidade S .

Se a probabilidade de mover de i para j em um intervalo de tempo é Pr ( j | i ) = P i , j , a matriz estocástica P é dada usando P i , j como o i -ésimo elemento da linha e j -ésimo elemento da coluna , por exemplo,

Uma vez que o total da probabilidade de transição de um estado i para todos os outros estados deve ser 1,

portanto, essa matriz é uma matriz estocástica correta.

A soma elemento a elemento acima em cada linha i de P pode ser mais concisamente escrita como P 1 = 1 , onde 1 é o vetor S- dimensional de todos os uns. Usando isso, pode-se ver que o produto de duas matrizes estocásticas direitas P e P ′ ′ também é estocástica direita: PP ′ ′ 1 = P ′ ( P ′ ′ 1 ) = P1 = 1 . Em geral, a k -ésima potência P k de uma matriz estocástica direita P também é estocástica direita. A probabilidade de transição de i para j em duas etapas é então dada pelo ( i , j ) -ésimo elemento do quadrado de P :

Em geral, a probabilidade de transição de ir de qualquer estado para outro estado em uma cadeia de Markov finita dada pela matriz P em k passos é dada por P k .

Uma distribuição de probabilidade inicial de estados, especificando onde o sistema pode estar inicialmente e com quais probabilidades, é fornecida como um vetor linha .

Um vetor de probabilidade estacionário π é definido como uma distribuição, escrita como um vetor linha, que não muda com a aplicação da matriz de transição; ou seja, é definido como uma distribuição de probabilidade no conjunto {1, ..., n } que também é um autovetor de linha da matriz de probabilidade, associado ao autovalor 1:

Pode-se mostrar que o raio espectral de qualquer matriz estocástica é um. Pelo teorema do círculo de Gershgorin , todos os autovalores de uma matriz estocástica têm valores absolutos menores ou iguais a um. Além disso, cada matriz estocástica direita tem uma coluna "óbvio" autovetor associado ao autovalor 1: o vetor 1 , cujas coordenadas são todos iguais a 1 (apenas observar que multiplicar uma fileira de A vezes 1 é igual à soma das entradas de linha e, portanto, é igual a 1). Como os autovalores esquerdo e direito de uma matriz quadrada são iguais, toda matriz estocástica tem, pelo menos, um autovetor de linha associado ao autovalor 1 e o maior valor absoluto de todos os seus autovalores também é 1. Finalmente, o Teorema de Ponto Fixo de Brouwer ( aplicada ao conjunto convexo compacto de todas as distribuições de probabilidade do conjunto finito {1, ..., n } ) implica que há algum autovetor esquerdo que também é um vetor de probabilidade estacionário.

Por outro lado, o teorema de Perron-Frobenius também garante que toda matriz estocástica irredutível tem tal vetor estacionário, e que o maior valor absoluto de um autovalor é sempre 1. No entanto, este teorema não pode ser aplicado diretamente a tais matrizes porque eles precisam não ser irredutível.

Em geral, pode haver vários desses vetores. No entanto, para uma matriz com entradas estritamente positivas (ou, mais geralmente, para uma matriz estocástica aperiódica irredutível), este vetor é único e pode ser calculado observando que para qualquer i temos o seguinte limite,

onde π j é o j -ésimo elemento do vetor linha π . Entre outras coisas, isso diz que a probabilidade de longo prazo de estar em um estado j é independente do estado inicial i . O fato de ambos os cálculos fornecerem o mesmo vetor estacionário é uma forma de teorema ergódico , que geralmente é verdadeiro em uma ampla variedade de sistemas dinâmicos dissipativos : o sistema evolui, ao longo do tempo, para um estado estacionário .

Intuitivamente, uma matriz estocástica representa uma cadeia de Markov; a aplicação da matriz estocástica a uma distribuição de probabilidade redistribui a massa de probabilidade da distribuição original enquanto preserva sua massa total. Se este processo for aplicado repetidamente, a distribuição converge para uma distribuição estacionária para a cadeia de Markov.

Exemplo: o gato e o rato

Suponha que haja um cronômetro e uma linha de cinco caixas adjacentes, com um gato na primeira caixa e um rato na quinta caixa no tempo zero. O gato e o rato saltam para uma caixa adjacente aleatória quando o cronômetro avança. Por exemplo, se o gato está na segunda caixa e o rato na quarta, a probabilidade é de um quarto de que o gato esteja na primeira caixa e o rato na quinta depois que o cronômetro avança . Se o gato estiver na primeira caixa e o rato na quinta, a probabilidade é que o gato esteja na casa dois e o rato na casa quatro depois que o cronômetro avança. O gato come o rato se ambos terminarem na mesma caixa, momento em que o jogo termina. A variável aleatória K fornece o número de passos de tempo que o mouse permanece no jogo.

A cadeia de Markov que representa este jogo contém os cinco estados a seguir especificados pela combinação de posições (gato, rato). Observe que, embora uma enumeração ingênua de estados listasse 25 estados, muitos são impossíveis porque o rato nunca pode ter um índice inferior ao do gato (pois isso significaria que o rato ocupou a caixa do gato e sobreviveu para passar por ela), ou porque a soma dos dois índices sempre terá paridade par . Além disso, os 3 estados possíveis que levam à morte do rato são combinados em um:

  • Estado 1: (1,3)
  • Estado 2: (1,5)
  • Estado 3: (2,4)
  • Estado 4: (3,5)
  • Estado 5: jogo terminado: (2,2), (3,3) e (4,4).

Usamos uma matriz estocástica, (abaixo), para representar as probabilidades de transição deste sistema (linhas e colunas nesta matriz são indexadas pelos possíveis estados listados acima, com o estado pré-transição como a linha e o estado pós-transição como o coluna). Por exemplo, partindo do estado 1 - 1ª linha - é impossível para o sistema permanecer neste estado, portanto ; o sistema também não pode fazer a transição para o estado 2 - porque o gato teria permanecido na mesma caixa - então , e por um argumento semelhante para o mouse ,. As transições para os estados 3 ou 5 são permitidas e, portanto .

Médias de longo prazo

Não importa qual seja o estado inicial, o gato acabará pegando o mouse (com probabilidade 1) e um estado estacionário π = (0,0,0,0,1) é aproximado como um limite. Para calcular a média de longo prazo ou o valor esperado de uma variável estocástica , para cada estado e tempo há uma contribuição de . A sobrevivência pode ser tratada como uma variável binária para um estado de sobrevivência e para o estado encerrado. Os estados com não contribuem para a média de longo prazo.

Representação de tipo de fase

A função de sobrevivência do mouse. O mouse sobreviverá pelo menos à primeira etapa.

Como o Estado 5 é um estado absorvente, a distribuição do tempo de absorção é discreta do tipo de fase . Suponha que o sistema comece no estado 2, representado pelo vetor . Os estados em que o mouse morreu não contribuem para a média de sobrevivência, portanto, o estado cinco pode ser ignorado. O estado inicial e a matriz de transição podem ser reduzidos a,

e

onde é a matriz de identidade e representa uma matriz de coluna de todas as que atuam como uma soma sobre os estados.

Uma vez que cada estado é ocupado por uma etapa de tempo, o tempo esperado de sobrevivência do mouse é apenas a soma da probabilidade de ocupação de todos os estados sobreviventes e etapas no tempo,

Momentos de ordem superior são dados por

Veja também

Referências