Dadas duas cadeias de Markov absorventes, qual é a probabilidade de uma terminar antes da outra?

9

Eu tenho duas cadeias de Markov diferentes, cada uma com um estado de absorção e uma posição inicial conhecida. Quero determinar a probabilidade de que a cadeia 1 atinja um estado de absorção em menos etapas que a cadeia 2.

Acho que posso calcular a probabilidade de atingir um estado de absorção em uma cadeia específica após n etapas: dada uma matriz de transição a probabilidade de ser absorvida após etapas é onde é o estado inicial e é o estado absorvente.n P n i j i jPnPEujnEuj

Eu não tenho certeza para onde ir daqui embora. Problemas análogos que eu já vi envolvem dados (por exemplo, rolar uma soma de 7 antes de uma soma de 8), mas isso é mais fácil de resolver, porque a probabilidade de rolar uma soma específica é constante e independente do número de etapas realizadas até agora.

Jeff
fonte

Respostas:

13

Passe as correntes em paralelo. Defina três estados de absorção na cadeia de produtos resultante:

  1. A primeira cadeia atinge um estado absorvente, mas a segunda não.

  2. A segunda cadeia atinge um estado absorvente, mas a primeira não.

  3. Ambas as cadeias atingem simultaneamente um estado de absorção.

As probabilidades limitantes desses três estados na cadeia de produtos dão as chances de interesse.


Esta solução envolve algumas construções (simples). Como no questão, deixe ser uma matriz de transição para uma cadeia P . Quando a cadeia está no estado i , P i j fornece a probabilidade de uma transição para o estado j . Um estado absorvente faz uma transição para si mesmo com probabilidade 1 .P=PEuj,1 1Eu,jnPEuPEujj1 1

  1. Qualquer estado pode ser absorvido ao substituir a linha P i = ( P i j , j = 1 , 2 , , n ) por um vetor indicador ( 0 , 0 , , 0 , 1 , 0 , , 0 ) com 1 na posição i .EuPEu=(PEuj,j=1 1,2,,n)(0 0,0 0,,0 0,1 1,0 0,,0 0)1 1Eu
  2. Qualquer conjunto de estados absorventes pode ser mesclado criando uma nova cadeia de P / A cujos estados são { iUMAP/UMA . A matriz de transição é dada por{Eu|EuUMA}{UMA}

    (P/UMA)Euj={PEujEuUMA,jUMAkUMAPEukEuUMA,j=UMA0 0Eu=UMA,jUMA1 1Eu=j=UMA.

    Isso equivale a somar as colunas de correspondentes a A e substituir as linhas correspondentes a A por uma única linha que faz uma transição para si mesma.PUMAUMA

  3. O produto de duas cadeias nos estados S P e Q nos estados S Q , com matrizes de transição P e Q , respectivamente, é uma cadeia de Markov nos estados S P × S Q = { ( p , q )PSPQSQPQ com matriz de transiçãoSP×SQ={(p,q)|pSP,qSQ}

    (PQ)(Eu,j),(k,eu)=PEukQjeu.

    Com efeito, a cadeia de produtos executa as duas cadeias em paralelo, rastreando separadamente onde cada uma está e fazendo transições independentemente.


Um exemplo simples pode esclarecer essas construções. Suponha que Polly esteja jogando uma moeda com uma chance de cabeças de aterrissagem. Ela planeja fazer isso até observar uma cabeça. Os estados para o processo de troca de moedas são S P = { T , H }, representando os resultados do lançamento mais recente: T para coroa, H para cabeça. Ao planejar parar na frente, Polly aplicará a primeira construção, tornando H um estado absorvente. A matriz de transição resultante épSP={T,H}THH

P=(1 1-pp0 01 1).

Começa em um estado aleatório dado pelo primeiro lançamento.(1 1-p,p)

A par de Polly, Quincy jogará uma moeda justa. Ele planeja parar quando vê duas cabeças seguidas. Sua cadeia de Markov, portanto, precisa acompanhar o resultado anterior, bem como o resultado atual. Existem quatro combinações de duas caras e duas caudas, que abreviarei como " ", por exemplo, onde a primeira letra é o resultado anterior e a segunda letra é o resultado atual . Quincy aplica a construção (1) para fazer da HH um estado absorvente. Depois de fazer isso, ele percebe que não precisa realmente de quatro estados: ele pode simplificar sua cadeia para três estados: T significa que o resultado atual é coroa, H significa que o resultado atual é cara e XºHHTHXsignifica que os dois últimos resultados foram de ambas as cabeças - este é o estado de absorção. A matriz de transição é

Q=(1 121 120 01 120 01 120 00 01 1).

A cadeia de produtos funciona em seis estados: . A matriz de transição é umproduto tensorialde P e Q e é facilmente calculada. Por exemplo, ( PQ ) ( T ,(T,T),(T,H),(T,X);(H,T),(H,H),(H,X)PQ , é a possibilidade de que Polly faz uma transição deTparaTe, ao mesmo tempo (e de forma independente), Quincy faz uma transição deTparaH. O primeiro tem uma possibilidade de1-pe o último a oportunidade de1 / 2. Como as cadeias são executadas de forma independente, essas chances se multiplicam, resultando em(1-p) / 2. A matriz de transição completa é(PQ)(T,T),(T,H)TTTH1 1-p1 1/2(1 1-p)/2

PQ=(1 1-p21 1-p20 0p2p20 01 1-p20 01 1-p2p20 0p20 00 01 1-p0 00 0p0 00 00 01 121 120 00 00 00 01 120 01 120 00 00 00 00 01 1).

Está na forma de matriz de blocos com blocos correspondentes à segunda matriz :Q

PQ=(P11QP12QP21QP22Q)=((1p)QpQ0Q).

Polly e Quincy competem para ver quem alcançará seu objetivo primeiro. O vencedor será Polly sempre que uma transição for feita para onde ambos absorvem (via construção (1)) e depois os mesclam (via construção (2)). A matriz de transição resultante, ordenada pelos estados ( T , T ) , ( T ,(H,*) não é X ; o vencedor será Quincy sempre que uma transição for feita para ( T , X ) ; e se antes que qualquer um desses itens possa ocorrer uma transição para ( H , X ) , o resultado será um empate. Para acompanhar, criaremos os estados ( H , T ) e ( H , H )*X(T,X)(H,X)(H,T)(H,H) é(T,T),(T,H),(T,X),{(H,T),(H,H)},(H,X)

R=(1 1-p21 1-p20 0p0 01 1-p20 01 1-p2p2p20 00 01 10 00 00 00 00 01 10 00 00 00 00 01 1).

Os resultados do primeiro arremesso simultâneo de Polly e Quincy serão os estados com probabilidades μ = ( ( 1 - p ) / 2 , ( 1 - p(T,T),(T,H),(T,X),{(H,T),(H,H)},(H,X) , respectivamente: este é o estado inicial no qual iniciar a cadeia.μ=((1 1-p)/2,(1 1-p)/2,0 0,p,0 0)

No limite como ,n

μRn1 11 1+4p-p2(0 0,0 0,(1 1-p)2,p(5-p),p(1 1-p)).

Assim, as chances relativas dos três estados absorventes (representando Quincy vence, Polly vence, eles empatam) são(T,X),{(H,T),(H,H)},(H,X) .(1 1-p)2:p(5-p):p(1 1-p)

Figura

p

whuber
fonte
11
Exemplo muito elegante, obrigado por isso. Ainda estou trabalhando nos detalhes para vê-los por mim mesmo. Apenas uma pergunta: aqui assumimos que os dois eventos (arremessos de Polly e Quincy) estavam acontecendo simultaneamente, que diferença faria se os tornássemos sequenciais ou até escolhêssemos aleatoriamente cada vez que jogaria o próximo?
precisa saber é o seguinte
11
@ user929304 Você obteria respostas diferentes, possivelmente substancialmente. Por exemplo, suponha que P e Q estejam executando uma cadeia na qual os estados são particionados nos subconjuntos A e B, em que todas as transições de A vão para B e todas de B vão para A. Deixe P e Q começarem nos estados de A. na cadeia de produtos, ambas alternam simultaneamente entre A e B, mas as cadeias seqüencial e de escolha aleatória quebram esse padrão invariável.
whuber