나는 하나의 흡수 상태와 알려진 시작 위치를 가진 두 개의 다른 Markov 체인을 가지고 있습니다. 체인 1이 체인 2보다 적은 단계로 흡수 상태에 도달 할 확률을 결정하고 싶습니다.
나는 n 단계 후에 특정 체인에서 흡수 상태에 도달 할 확률을 계산할 수 있다고 생각합니다.
이후 흡수 될 확률
단계는
어디
시작 상태이며
흡수 상태입니다.
그래도 여기서 어디로 가야할지 모르겠습니다. 필자가 본 유사한 문제는 주사위 (예를 들어, 합이 8의 합보다 7의 합을 구는 것)와 관련이 있지만, 특정 합을 구르는 확률은 일정하고 지금까지 취한 단계 수와 무관하기 때문에 해결하기가 더 쉽습니다.
답변
체인을 병렬로 실행하십시오. 결과 제품 체인에서 3 가지 흡수 상태를 정의하십시오.
-
첫 번째 사슬은 흡수 상태에 도달하지만 두 번째 사슬은 흡수되지 않습니다.
-
두 번째 체인은 흡수 상태에 도달하지만 첫 번째 체인은 흡수되지 않습니다.
-
두 체인 모두 동시에 흡수 상태에 도달합니다.
제품 체인에서이 세 가지 상태의 제한 확률은 관심의 기회를 제공합니다.
이 솔루션에는 일부 간단한 구조가 포함됩니다. 질문에서와 같이
체인의 전이 행렬
. 체인이 상태 일 때
,
상태로의 전환 확률을 제공
. 흡수 상태 확률로 그 자체로 전환 할
.
- 어떤 주
줄을 대체 할 때 흡수 될 수 있습니다 지표 벡터에 의한 것 와 위치에 . -
어떤 세트
새로운 사슬을 만들어 흡수 상태의 합병
누구의 주가
. 전이 행렬은
이것은 열을 합산하는 것입니다.
에 해당하는
행을 교체하면
자체로 전환하는 단일 행으로.
-
두 체인 의 제품
주에서
과
주에서
전이 행렬과 함께
과
각각 국가의 마르코프 체인입니다
전이 행렬로
실제로, 제품 체인은 두 체인을 병렬로 실행하여 각각의 위치를 개별적으로 추적하고 독립적으로 전환합니다.
간단한 예가 이러한 구성을 명확히 할 수 있습니다. 폴리가 기회를 가지고 동전을 뒤집고 있다고 가정하자
착륙장 그녀는 머리를 관찰 할 때까지 그렇게 할 계획입니다. 동전 뒤집기 과정의 상태는
가장 최근 플립 결과를 나타냅니다.
꼬리를 위해
머리를 위해. 폴리 (Poly)는 선두에 서서 계획함으로써 첫 번째 시공을
흡수 상태. 결과 전이 행렬은
그것은 임의의 상태에서 시작
첫 번째 던지기에 의해 주어진.
폴리와 함께, 퀸시는 공정한 동전을 던질 것입니다. 그는 두 개의 머리를 연속으로보고 난 후에 멈출 계획이다. 따라서 Markov 체인은 현재 결과뿐만 아니라 이전 결과를 추적해야합니다. 두 개의 머리와 두 개의 꼬리의 네 가지 조합이 있습니다.
예를 들어 첫 번째 문자는 이전 결과이고 두 번째 문자는 현재 결과입니다. Quincy는 건설 (1)을 적용하여
흡수 상태. 그렇게 한 후, 그는 실제로 네 가지 상태가 필요하지 않다는 것을 알고 있습니다. 그는 체인을 세 가지 상태로 단순화 할 수 있습니다.
현재 결과가 꼬리임을 의미합니다.
현재 결과가 머리임을 의미하며
마지막 두 결과는 두 가지 모두를 의미합니다. 이것은 흡수 상태입니다. 전이 행렬은
제품 체인은 6 가지 상태에서 실행됩니다.
. 전이 매트릭스 A는 텐서 생성물 의
과
쉽게 계산됩니다. 예를 들어
폴리가
에
그리고 동시에 (그리고 독립적으로) Quincy는
에
. 전자는 기회가
후자는
. 체인이 독립적으로 실행되기 때문에 그 가능성은 배가되어
. 전체 전이 행렬은
두 번째 행렬에 해당하는 블록이있는 블록 행렬 형식입니다.
:
폴리와 퀸시는 누가 먼저 목표를 달성 할 수 있는지 경쟁합니다. 승자가 처음으로 전환 될 때마다 승자가 폴리가됩니다.
어디
아니다
; 승자가 처음 전환 될 때마다 우승자가 Quincy가됩니다.
; 그 중 하나가 발생하기 전에 전환이 이루어지면
결과는 추첨이됩니다. 추적하기 위해, 우리는 상태를 만들 것입니다
과
(건설 (1)을 통해) 흡수 한 다음 (건설 (2)를 통해) 병합하십시오. 상태별로 정렬 된 결과 전이 행렬
이다
폴리와 퀸시의 동시 첫 투구 결과는 주가 될 것이다
확률로
, 각각 : 체인을 시작하는 초기 상태입니다.
한도에서
,
따라서 세 가지 흡수 상태의 상대 확률
(퀸시 승리, 폴리 승리, 대표)
.
의 기능으로
(폴리의 던지기 중 하나가 머리가 될 확률), 빨간색 곡선은 폴리의 우승 확률을 나타내고, 파란색 곡선은 퀸시의 우승 확률을 나타내며, 금색 곡선은 무승부 확률을 나타냅니다.