Explicit transient probabilities of Markov chains having mainly transition step sizes of 0 or ±𝑡

<p>In this article, explicit formulas for the transient behavior of two different types of finite Markov Chains are developed. These expressions provide a unifying theoretic alternative to numerically taking powers of one-step transition matrices.</p> <p> The first type of finite Markov Chain discussed in this article is a Gambler’s Ruin Markov Chain on the linearly ordered state space <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet 0 comma 1 comma ellipsis comma upper H comma upper H plus 1 EndSet"> <mml:semantics> <mml:mrow> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mo> … </mml:mo> <mml:mo>,</mml:mo> <mml:mi>H</mml:mi> <mml:mo>,</mml:mo> <mml:mi>H</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\{0,1,\dots ,H,H+1\}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and mainly has one-step transitions of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="plus-or-minus t"> <mml:semantics> <mml:mrow> <mml:mo> ± </mml:mo> <mml:mi>t</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\pm t</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="t greater-than-or-equal-to 2"> <mml:semantics> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo> ≥ </mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">t \geq 2</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H greater-than-or-equal-to t plus 1"> <mml:semantics> <mml:mrow> <mml:mi>H</mml:mi> <mml:mo> ≥ </mml:mo> <mml:mi>t</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">H \geq t+1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . For the transient states, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="monospace upper T"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="monospace">T</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathtt {T}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , a step of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="plus t"> <mml:semantics> <mml:mrow> <mml:mo>+</mml:mo> <mml:mi>t</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">+t</mml:annotation> </mml:semantics> </mml:math> </inline-formula> can happen with non-zero probability <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p"> <mml:semantics> <mml:mi>p</mml:mi> <mml:annotation encoding="application/x-tex">p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> or a step of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="negative t"> <mml:semantics> <mml:mrow> <mml:mo> − </mml:mo> <mml:mi>t</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">-t</mml:annotation> </mml:semantics> </mml:math> </inline-formula> can happen with non-zero probability <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="q"> <mml:semantics> <mml:mi>q</mml:mi> <mml:annotation encoding="application/x-tex">q</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . If a transition requires a step-size less than <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="t"> <mml:semantics> <mml:mi>t</mml:mi> <mml:annotation encoding="application/x-tex">t</mml:annotation> </mml:semantics> </mml:math> </inline-formula> to reach <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="0"> <mml:semantics> <mml:mn>0</mml:mn> <mml:annotation encoding="application/x-tex">0</mml:annotation> </mml:semantics> </mml:math> </inline-formula> or <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H plus 1"> <mml:semantics> <mml:mrow> <mml:mi>H</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">H+1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> then the transition probability is still <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="q"> <mml:semantics> <mml:mi>q</mml:mi> <mml:annotation encoding="application/x-tex">q</mml:annotation> </mml:semantics> </mml:math> </inline-formula> or <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p"> <mml:semantics> <mml:mi>p</mml:mi> <mml:annotation encoding="application/x-tex">p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , respectively. There may also be catastrophe transitions to state 0 with probability <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="c"> <mml:semantics> <mml:mi>c</mml:mi> <mml:annotation encoding="application/x-tex">c</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , windfall transitions to state <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H plus 1"> <mml:semantics> <mml:mrow> <mml:mi>H</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">H+1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with probability <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="w"> <mml:semantics> <mml:mi>w</mml:mi> <mml:annotation encoding="application/x-tex">w</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , or return transitions with probability <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r"> <mml:semantics> <mml:mi>r</mml:mi> <mml:annotation encoding="application/x-tex">r</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . It is assumed that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p plus q plus r plus c plus w equals 1 comma 0 greater-than p comma q greater-than 1"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>+</mml:mo> <mml:mi>q</mml:mi> <mml:mo>+</mml:mo> <mml:mi>r</mml:mi> <mml:mo>+</mml:mo> <mml:mi>c</mml:mi> <mml:mo>+</mml:mo> <mml:mi>w</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>0</mml:mn> <mml:mo>&gt;</mml:mo> <mml:mi>p</mml:mi> <mml:mo>,</mml:mo> <mml:mi>q</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">p + q + r + c + w =1, 0 &gt; p,q &gt; 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="0 less-than-or-equal-to r comma w comma c greater-than 1"> <mml:semantics> <mml:mrow> <mml:mn>0</mml:mn> <mml:mo> ≤ </mml:mo> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mi>w</mml:mi> <mml:mo>,</mml:mo> <mml:mi>c</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">0 \leq r,w,c &gt; 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . In this case, the values of these transition probabilities are constant for each transient state. More generally, for transient states <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="s identical-to m left-parenthesis mod t right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>s</mml:mi> <mml:mo> ≡ </mml:mo> <mml:mi>m</mml:mi> <mml:mspace width="0.667em"/> <mml:mo stretchy="false">(</mml:mo> <mml:mi>mod</mml:mi> <mml:mspace width="0.333em"/> <mml:mi>t</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">s \equiv m \pmod t</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m equals 1 comma 2 comma ellipsis comma t"> <mml:semantics> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>2</mml:mn> <mml:mo>,</mml:mo> <mml:mo> … </mml:mo> <mml:mo>,</mml:mo> <mml:mi>t</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">m=1,2,\dots ,t</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , there can be transition probabilities, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p Subscript m Baseline comma q Subscript m Baseline comma r Subscript m Baseline comma c Subscript m Baseline"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>q</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>r</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>c</mml:mi> <mml:mi>m</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">p_m, q_m, r_m, c_m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="w Subscript m"> <mml:semantics> <mml:msub> <mml:mi>w</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">w_m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p Subscript m Baseline plus q Subscript m Baseline plus r Subscript m Baseline plus c Subscript m Baseline plus w Subscript m Baseline equals 1 comma 0 greater-than p Subscript m Baseline comma q Subscript m Baseline greater-than 1"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>q</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>r</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>c</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>w</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>0</mml:mn> <mml:mo>&gt;</mml:mo> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>q</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mo>&gt;</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">p_m + q_m + r_m + c_m + w_m =1, 0 &gt; p_m,q_m &gt; 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="0 less-than-or-equal-to r Subscript m Baseline comma w Subscript m Baseline comma c Subscript m Baseline greater-than 1"> <mml:semantics> <mml:mrow> <mml:mn>0</mml:mn> <mml:mo> ≤ </mml:mo> <mml:msub> <mml:mi>r</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>w</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>c</mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:mo>&gt;</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">0 \leq r_m,w_m,c_m &gt; 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . This allows up to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="t"> <mml:semantics> <mml:mi>t</mml:mi> <mml:annotation encoding="application/x-tex">t</mml:annotation> </mml:semantics> </mml:math> </inline-formula> distinct sets of these transition probabilities. The explicit <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -th step transient probabilities of this Gambler’s Ruin Markov Chain are found using permutation matrices, block matrix multiplication, previously known eigenvalues and eigenvectors of Toeplitz tridiagonal matrices and Sylvester’s Eigenvalue Expansion. </p> <p> The one-step transitions of the second Markov Chain have the same pattern as that of the first type of Markov Chain. However, the transition probabilities are the same <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p comma q comma r comma c"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>,</mml:mo> <mml:mi>q</mml:mi> <mml:mo>,</mml:mo> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mi>c</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">p,q,r,c</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="w"> <mml:semantics> <mml:mi>w</mml:mi> <mml:annotation encoding="application/x-tex">w</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for each non-end state, and the end-states communicate with each other. Additionally, this Markov Chain always has a steady-state distribution, an example is described in the text. Finding the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -th step transient probabilities has the same approach of using permutation matrices, block matrix multiplication, previously known eigenvalues and eigenvectors of Toeplitz tridiagonal matrices and Sylvester’s Eigenvalue Expansion. In contrast to the Gambler’s Ruin problem, Siegmund Duality is applied to complete the argument. </p>