두 개의 흡수 마르코프 체인이 주어지면, 하나가 다른 것보다 먼저 종결 될 확률은 얼마입니까? 확률 엔nn 단계는 피엔나는 jPijnP^n_{ij} 어디 나는ii

나는 하나의 흡수 상태와 알려진 시작 위치를 가진 두 개의 다른 Markov 체인을 가지고 있습니다. 체인 1이 체인 2보다 적은 단계로 흡수 상태에 도달 할 확률을 결정하고 싶습니다.

나는 n 단계 후에 특정 체인에서 흡수 상태에 도달 할 확률을 계산할 수 있다고 생각합니다.

P

이후 흡수 될 확률

n

단계는

Pijn

어디

i

시작 상태이며

j

흡수 상태입니다.

그래도 여기서 어디로 가야할지 모르겠습니다. 필자가 본 유사한 문제는 주사위 (예를 들어, 합이 8의 합보다 7의 합을 구는 것)와 관련이 있지만, 특정 합을 구르는 확률은 일정하고 지금까지 취한 단계 수와 무관하기 때문에 해결하기가 더 쉽습니다.



답변

체인을 병렬로 실행하십시오. 결과 제품 체인에서 3 가지 흡수 상태를 정의하십시오.

  1. 첫 번째 사슬은 흡수 상태에 도달하지만 두 번째 사슬은 흡수되지 않습니다.

  2. 두 번째 체인은 흡수 상태에 도달하지만 첫 번째 체인은 흡수되지 않습니다.

  3. 두 체인 모두 동시에 흡수 상태에 도달합니다.

제품 체인에서이 세 가지 상태의 제한 확률은 관심의 기회를 제공합니다.


이 솔루션에는 일부 간단한 구조가 포함됩니다. 질문에서와 같이

P=Pij,1i,jn

체인의 전이 행렬

P

. 체인이 상태 일 때

i

,

Pij

상태로의 전환 확률을 제공

j

. 흡수 상태 확률로 그 자체로 전환 할

1

.

  1. 어떤 주
    i

    줄을 대체 할 때 흡수 될 수 있습니다

    Pi=(Pij,j=1,2,,n)

    지표 벡터에 의한 것

    (0,0,,0,1,0,,0)

    1

    위치에

    i

    .

  2. 어떤 세트

    A

    새로운 사슬을 만들어 흡수 상태의 합병

    P/A

    누구의 주가

    {i|iA}{A}

    . 전이 행렬은

    (P/A)ij={PijiA,jAkAPikiA,j=A0i=A,jA1i=j=A.

    이것은 열을 합산하는 것입니다.

    P

    에 해당하는

    A

    행을 교체하면

    A

    자체로 전환하는 단일 행으로.

  3. 두 체인 의 제품

    P

    주에서

    SP

    Q

    주에서

    SQ

    전이 행렬과 함께

    P

    Q

    각각 국가의 마르코프 체인입니다

    SP×SQ={(p,q)|pSP,qSQ}

    전이 행렬로

    (PQ)(i,j),(k,l)=PikQjl.

    실제로, 제품 체인은 두 체인을 병렬로 실행하여 각각의 위치를 ​​개별적으로 추적하고 독립적으로 전환합니다.


간단한 예가 이러한 구성을 명확히 할 수 있습니다. 폴리가 기회를 가지고 동전을 뒤집고 있다고 가정하자

p

착륙장 그녀는 머리를 관찰 할 때까지 그렇게 할 계획입니다. 동전 뒤집기 과정의 상태는

SP={T,H}

가장 최근 플립 결과를 나타냅니다.

T

꼬리를 위해

H

머리를 위해. 폴리 (Poly)는 선두에 서서 계획함으로써 첫 번째 시공을

H

흡수 상태. 결과 전이 행렬은

P=(1pp01).

그것은 임의의 상태에서 시작

(1p,p)

첫 번째 던지기에 의해 주어진.

폴리와 함께, 퀸시는 공정한 동전을 던질 것입니다. 그는 두 개의 머리를 연속으로보고 난 후에 멈출 계획이다. 따라서 Markov 체인은 현재 결과뿐만 아니라 이전 결과를 추적해야합니다. 두 개의 머리와 두 개의 꼬리의 네 가지 조합이 있습니다.

TH

예를 들어 첫 번째 문자는 이전 결과이고 두 번째 문자는 현재 결과입니다. Quincy는 건설 (1)을 적용하여

HH

흡수 상태. 그렇게 한 후, 그는 실제로 네 가지 상태가 필요하지 않다는 것을 알고 있습니다. 그는 체인을 세 가지 상태로 단순화 할 수 있습니다.

T

현재 결과가 꼬리임을 의미합니다.

H

현재 결과가 머리임을 의미하며

X

마지막 두 결과는 두 가지 모두를 의미합니다. 이것은 흡수 상태입니다. 전이 행렬은

Q=(1212012012001).

제품 체인은 6 가지 상태에서 실행됩니다.

(T,T),(T,H),(T,X);(H,T),(H,H),(H,X)

. 전이 매트릭스 A는 텐서 생성물

P

Q

쉽게 계산됩니다. 예를 들어

(PQ)(T,T),(T,H)

폴리가

T

T

그리고 동시에 (그리고 독립적으로) Quincy는

T

H

. 전자는 기회가

1p

후자는

1/2

. 체인이 독립적으로 실행되기 때문에 그 가능성은 배가되어

(1p)/2

. 전체 전이 행렬은

PQ=(1p21p20p2p201p201p2p20p2001p00p0001212000012012000001).

두 번째 행렬에 해당하는 블록이있는 블록 행렬 형식입니다.

Q

:

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

폴리와 퀸시는 누가 먼저 목표를 달성 할 수 있는지 경쟁합니다. 승자가 처음으로 전환 될 때마다 승자가 폴리가됩니다.

(H,*)

어디

*

아니다

X

; 승자가 처음 전환 될 때마다 우승자가 Quincy가됩니다.

(T,X)

; 그 중 하나가 발생하기 전에 전환이 이루어지면

(H,X)

결과는 추첨이됩니다. 추적하기 위해, 우리는 상태를 만들 것입니다

(H,T)

(H,H)

(건설 (1)을 통해) 흡수 한 다음 (건설 (2)를 통해) 병합하십시오. 상태별로 정렬 된 결과 전이 행렬

(T,T),(T,H),(T,X),{(H,T),(H,H)},(H,X)

이다

R=(1p21p20p01p201p2p2p2001000001000001).

폴리와 퀸시의 동시 첫 투구 결과는 주가 될 것이다

(T,T),(T,H),(T,X),{(H,T),(H,H)},(H,X)

확률로

μ=((1p)/2,(1p)/2,0,p,0)

, 각각 : 체인을 시작하는 초기 상태입니다.

한도에서

n

,

μRn11+4pp2(0,0,(1p)2,p(5p),p(1p)).

따라서 세 가지 흡수 상태의 상대 확률

(T,X),{(H,T),(H,H)},(H,X)

(퀸시 승리, 폴리 승리, 대표)

(1p)2:p(5p):p(1p)

.

그림

의 기능으로

p

(폴리의 던지기 중 하나가 머리가 될 확률), 빨간색 곡선은 폴리의 우승 확률을 나타내고, 파란색 곡선은 퀸시의 우승 확률을 나타내며, 금색 곡선은 무승부 확률을 나타냅니다.


답변