3.1. Ruin probability for symmetric CRWs

If $p=q$ , then $M_n=(2-2p)S_n+(2p-1)X_n$ . The OST immediately gives us that $0={\mathbb{E}}(M_1)={\mathbb{E}} (M_\tau)=(2-2p){\mathbb{E}}(S_\tau)+(2p-1){\mathbb{E}}(X_\tau)$ . Since $X_{\tau}=1$ on the set $\{S_{\tau}=A\}$ , and $X_{\tau}=-1$ on $\{S_{\tau}=-B\}$ , we have $0=(2-2p)(\alpha A-\beta B)+ (2p-1)(\alpha-\beta)$ . Since we also have $\alpha+\beta=1$ , we immediately get

(2) \begin{equation} \alpha=\frac{B-1+{1}/{(2-2p)}}{A+B-2+{1}/({1-p})}.\end{equation}

Note that we have intuitive answers for special cases:

• • if $A=B$ (symmetry), then $\alpha=\frac12$ ,

• • if $p=1/2$ (i.i.d.), then $\alpha=B/(A+B)$ ,

• • if $p\to 1$ , then $\alpha\to 1/2$ (everything is decided by the first flip),

• • if $B\to\infty$ , then $\alpha\to 1$ .

As previously mentioned, adjusting to an arbitrary initial distribution $(\pi_1,1-\pi_1)$ is straightforward. The only change is the value of ${\mathbb{E}}(M_1)$ . In this case, ${\mathbb{E}}(M_1)=2\pi_1-1$ . Consequently, we have

(3) \begin{equation} \alpha=\frac{B-1+{\pi_1}/({1-p})}{A+B+({2p-1})/({1-p})}.\end{equation}

3.2. Expected waiting time until ruin for symmetric CRWs

The i.i.d. case tells us that we should try to find a quadratic martingale. This suggests the candidate $M_n=S_n^2+aS_nX_n-bn$ . If it is possible to find such values of a and b so $M_n$ forms a martingale, then the OST gives us

\begin{align*}(1+a)-b={\mathbb{E}}(M_1)={\mathbb{E}}(M_\tau)=A^2\alpha+B^2\beta+a(A\alpha+B\beta)-b{\mathbb{E}}(\tau).\end{align*}

Since we already know $\alpha$ and $\beta$ , we have a formula for the expected waiting time:

(4) \begin{equation} {\mathbb{E}}(\tau)=\frac{1}{b}[b-(1+a)+A^2\alpha+B^2\beta+a(A\alpha+B\beta)].\end{equation}

Now, using ${\mathbb{E}}(X_n\mid{\mathcal{F}}_{n-1})=(2p-1)X_{n-1}$ and $X_n^2=1$ we get

\begin{align*} {\mathbb{E}}(M_n\mid{\mathcal{F}}_{n-1}) & = {\mathbb{E}}(S_n^2+aS_nX_n-bn\mid{\mathcal{F}}_{n-1}) \\ & = {\mathbb{E}}((S_{n-1}+X_n)^2+a(S_{n-1}+X_n)X_n-bn\mid{\mathcal{F}}_{n-1}) \\ & = S_{n-1}^2 + [2(2p-1)+a(2p-1)]S_{n-1}X_{n-1} + [1+a-bn].\end{align*}

Therefore, to make it a martingale we need a and b to satisfy the following system of equations:

\begin{align*}\left\{ \begin{array}{l} 2(2p-1) + a(2p-1) = a, \\ 1 + a - bn = -b(n-1). \end{array}\right.\end{align*}

This gives us $a=(2p-1)/(1-p)$ and $b=p/(1-p)$ . Plugging these values into (4), after some algebra we obtain

(5) \begin{equation} {\mathbb{E}}(\tau) = AB\frac{1-p}{p}+(A+B)\frac{2p-1}{2p}.\end{equation}

Here are some special cases:

• • If $p=\frac12$ (i.i.d.), then ${\mathbb{E}}(\tau)=AB$ .

• • If $p=1$ , then ${\mathbb{E}}(\tau)=(A+B)/2$ (going straight to A or $-B$ depending on the initial value $X_1$ ).

• • If $A=B$ , then ${\mathbb{E}}(\tau)=A^2({1-p})/{p} + A({2p-1})/{p}$ .

3.3. Ruin probability for asymmetric CRWs

The i.i.d. case together with our first martingale construction suggests an exponential martingale $M_n=\lambda^{S_n+aX_n}$ , where $\lambda>0$ and $a\in \mathbb{R}$ . Again, let us assume first that we are successful in finding $\lambda>0$ and a that make $M_n$ a martingale. Then, in addition to $\alpha+\beta=1$ , the OST gives another linear equation:

(6) \begin{equation} {\mathbb{E}}(M_1)={\mathbb{E}}(M_\tau)=\lambda^{A+a}\alpha+\lambda^{-B-a}\beta.\end{equation}

So, let us figure out these $\lambda$ and a. First, we have

\begin{align*} {\mathbb{E}}(M_n\mid{\mathcal{F}}_{n-1}) & = {\mathbb{E}}(\lambda^{S_{n-1}+(1+a)X_n+ aX_{n-1}-aX_{n-1}}\mid{\mathcal{F}}_{n-1}) \\ & = M_{n-1}{\mathbb{E}}(\lambda^{(1+a)X_n-aX_{n-1}}\mid{\mathcal{F}}_{n-1}).\end{align*}

Can we make the conditional expectation in the last expression equal to 1? Yes. As before,

\begin{align*} {\mathbb{E}}(\lambda^{(1+a)X_n-aX_{n-1}}\mid{\mathcal{F}}_{n-1}) & = \big[p\lambda^{(1+a)-a}+(1-p)\lambda^{-(1+a)-a}\big]\frac{X_{n-1}+1}{2} \\ & \quad + \big[(1-q)\lambda^{(1+a)+a}+q\lambda^{-(1+a)+a}\big]\frac{1-X_{n-1}}{2} \\ & = \big[p\lambda +(1-p)\lambda^{-1-2a}-(1-q)\lambda^{1+2a}-q\lambda^{-1}\big]\frac{X_{n-1}}{2} \\ & \quad + \big[p\lambda +(1-p)\lambda^{-1-2a}+(1-q)\lambda^{1+2a}+q\lambda^{-1}\big]\frac{1}{2}.\end{align*}

Next, equating the first coefficient to 0 and the second one to 2, we get the following non-linear system of equations for $\lambda$ and a:

\begin{align*}\left\{ \begin{array}{l} p\lambda+(1-p)\lambda^{-1-2a}=1, \\ (1-q)\lambda^{1+2a}+q\lambda^{-1}=1. \end{array}\right.\end{align*}

Because of the i.i.d. martingale $(q/p)^{S_n}$ , it is natural to try $\lambda=q/p$ . And it works: $\lambda=q/p$ and

\begin{align*}a=\frac{1}{2}\bigg[\log_{q/p}\frac{1-p}{1-q}-1\bigg]\end{align*}

is a solution. Note that a itself is not really a part of (6), it enters as

\begin{align*}\left(\frac{q}{p}\right)^a=\sqrt{\frac{(1-p)p}{(1-q)q}},\end{align*}

since our Markov chain starts from the stationary distribution

\begin{align*}{\mathbb{E}}(M_1)=&\left(\frac{q}{p}\right)^{1+a}\frac{1-q}{2-p-q}+\left(\frac{q}{p}\right)^{-1-a}\frac{1-p}{2-p-q} =\frac{\sqrt{(1-q)(1-p)}}{2-p-q}\left[\sqrt{\frac{q}{p}}+\sqrt{\frac{p}{q}}\right].\end{align*}

Finally, plugging it into (6) and solving with respect to $\alpha$ gives

\begin{equation*} \alpha = \left[\sqrt{\frac{q}{p}}+\sqrt{\frac{p}{q}}\right]\frac{({q}/{p})^{-B}\sqrt{({(1-q)q})/({(1-p)p})} - {\sqrt{(1-q)(1-p)}}/({2-p-q})} {({q}/{p})^{-B}\sqrt{({(1-q)q})/({(1-p)p})} - ({q}/{p})^{A}\sqrt{({(1-p)p})/({(1-q)q})}}.\end{equation*}

If $p=1-q$ , $p\neq \frac12$ , then this equation simplifies to a well-known expression for the asymmetric i.i.d. case (see, for example, [Reference Steele19]):

\begin{align*}\alpha=\frac{({q}/{p})^{-B}-1}{({q}/{p})^{-B}-({q}/{p})^{A}}.\end{align*}

3.4. Expected waiting time until ruin for asymmetric CRWs

Everything is ready now. Applying the OST to the martingale (1), we have, for ${\mathbb{E}}(\tau)$ ,

\begin{align*}{\mathbb{E}}(M_1)={\mathbb{E}}(M_\tau)=(2-p-q)(A\alpha-B\beta)+(p+q-1)(\alpha-\beta)-(p-q)({\mathbb{E}}(\tau)-1).\end{align*}

Since we already know $\alpha$ (and $\beta=1-\alpha$ ) and ${\mathbb{E}}(M_1)={\mathbb{E}}(X_1)=(p-q)/(2-p-q)$ , the formula for ${\mathbb{E}}(\tau)$ immediately follows:

\begin{align*}{\mathbb{E}}(\tau)=\frac{2-p-q}{p-q}(A\alpha-B\beta)+\frac{p+q-1}{p-q}(\alpha-\beta)+\frac{1-p-q}{2-p-q}.\end{align*}

4.1. Ruin probability for symmetric CRWs with delays

Consider a three-state Markov chain $\{X_n\}_{n\geq 1}$ with state set $\{1, 0, -1\}$ and transition matrix

\begin{align*}\begin{pmatrix} p &\quad r &\quad 1-p-r \\ (1-q)/2 &\quad q &\quad (1-q)/2\\ 1-p-r &\quad r &\quad p \\\end{pmatrix},\end{align*}

where $0\leq p,q,r<1$ and $0\leq p+r\leq 1$ . We assume that the initial distribution is stationary, i.e. it is given by

\begin{align*}\left(\frac{1-q}{2(1+r-q)},\frac{r}{(1+r-q)},\frac{1-q}{2(1+r-q)}\right).\end{align*}

We will keep the same notation for random walks, ruin probabilities, filtration, and stopping time. We call this random walk symmetric because states 1 and $-1$ enter into the picture in a symmetric way – they are interchangeable. More specifically, for states 1 and $-1$ , the probabilities of staying in the same state and the probabilities of switching to state 0 are the same. Additionally, the probabilities of switching from 0 to 1 and $-1$ are equal, too.

As before, the first step is to figure out the conditional expectation ${\mathbb{E}}(X_{n}\mid{\mathcal{F}}_{n-1})$ . We will use a technique similar to the one employed in the previous section. But note that in this case, $X_n^2$ is still a random variable, and the expressions for indicators of events $\{X_n=k\}$ , $k=1,0,-1$ , now depend on both $X_n$ and $X_n^2$ . More specifically, $\mathbf{1}_{X_n=1} =(X_n^2+X_n)/2$ , $\mathbf{1}_{X_n=0} =1-X_n^2$ , and $\mathbf{1}_{X_n=-1} =(X_n^2-X_n)/2$ . As a consequence, we get

\begin{align*} {\mathbb{E}}(X_n\mid{\mathcal{F}}_{n-1}) & = {\mathbb{E}}(X_n\mid X_{n-1}=1)\mathbf{1}_{X_{n-1}=1} + {\mathbb{E}}(X_n\mid X_{n-1}=0)\mathbf{1}_{X_{n-1}=0} \\ & \quad + {\mathbb{E}}(X_n\mid X_{n-1}=-1)\mathbf{1}_{X_{n-1}=-1} \\ & = [p-(1-p-r)](X_{n-1}^2+X_{n-1})/2 + [(1-q)/2-(1-q)/2](1-X_{n-1}^2) \\ & \quad + [(1-p-r)-p](X_{n-1}^2-X_{n-1})/2 = (2p+r-1)X_{n-1}.\end{align*}

Note that because of the symmetry of the transition matrix, $X_{n-1}^2$ is not a part of the formula.

So, a natural candidate for another useful martingale is $M_n=S_n+aX_n=S_{n-1}+(a+1)X_n$ . Using the expression for the conditional expectation, we immediately get that $(a+1)(2p+r-1)=a$ , or

\begin{align*}a=\frac{2p+r-1}{2-2p-r}.\end{align*}

Let us make two observations about the martingale. First, q is not a part of the formula, because in the symmetric case the delays do not affect the ruin probabilities. Second, note that because of $p+r\leq1$ and $r<1$ , we have $2-2p-r>0$ , so no division by zero. The rest is standard. The OST gives us

\begin{align*}0={\mathbb{E}}(M_1)={\mathbb{E}}(M_\tau)= A\alpha-B\beta+\frac{2p+r-1}{2-2p-r}(\alpha-\beta).\end{align*}

Together with $\alpha+\beta=1$ , this leads us to

\begin{equation*} \alpha=\frac{B-1+{1}/({2-2p-r})}{A+B-2+{2}/({2-2p-r})}.\end{equation*}

As a check, let us take a look at some special cases:

• • If $r=0$ (the state 0 is ignored), then we have (2).

• • If $2p+r=1$ or $p=1-p-r$ (almost the i.i.d. case because of an additional symmetry), then $S_n$ itself a martingale, and $\alpha=B/(A+B)$ .

• • If $A=B$ (symmetry), then $\alpha=\frac12$ .

In fact, because the delays do not really affect the ruin probabilities, the gambler’s ruin problem for a symmetric CRW with delays is equivalent to the gambler’s ruin problem for a two-state symmetric CRW with a probability of staying in a state of $p+r/2$ .

4.2. Expected waiting time until ruin for symmetric CRWs with delays

Finding ${\mathbb{E}}(\tau)$ is more challenging, because the delays play a significant role. At this point, we have some experience in building useful martingales, and this experience suggests the following candidate: $M_n=S_n^2+aS_nX_n+bX_n^2-cn$ . If we are successful in finding the right constants a, b, and c, the OST immediately gives us a formula for the expected waiting time until ruin:

(7) \begin{equation} {\mathbb{E}}(\tau)=\frac{1}{c}\big[A^2\alpha+B^2\beta+a(A\alpha+B\beta)+b-{\mathbb{E}}(M_1)\big].\end{equation}

So, the first step is to figure out the conditional expectation ${\mathbb{E}}(X_n^2\mid{\mathcal{F}}_n)$ . Using the expressions for indicators, we have

\begin{align*} {\mathbb{E}}(X_n^2\mid{\mathcal{F}}_{n-1}) & = [1-r](X_{n-1}^2+X_{n-1})/2 + [1-q](1-X_{n-1}^2) + [1-r](X_{n-1}^2+X_{n-1})/2 \\ & = (1-q) + (q-r)X_{n-1}^2.\end{align*}

Next, we get that

\begin{align*} {\mathbb{E}}(M_n\mid{\mathcal{F}}_{n-1}) & = {\mathbb{E}}((S_{n-1}+X_n)^2+a(S_{n-1}+X_n)X_n+bX_n^2-cn\mid{\mathcal{F}}_{n-1}) \\ & = {\mathbb{E}}(S_{n-1}^2+2S_{n-1}X_n+X_n^2 +aS_{n-1}X_n+aX_n^2+bX_n^2-cn\mid{\mathcal{F}}_{n-1}) \\ & = S_{n-1}^2+(2+a)(2p+r-1)S_{n-1}X_{n-1} +(1+a+b)(q-r)X_{n-1}^2 \\ & \quad +(1+a+b)(1-q)-cn.\end{align*}

To make it a martingale, a, b, and c have to satisfy the following linear system:

\begin{align*}\left\{ \begin{array}{l} (2+a)(2p+r-1)=a, \\ (1+a+b)(q-r)=b, \\ (1+a+b)(1-q)=c. \end{array}\right.\end{align*}

That leads us to

\begin{align*}a=\frac{2(2p+r-1)}{2-2p-r}, \quad\quad b=\frac{(q-r)(2p+r)}{(1+r-q)(2-2p-r)}, \quad\quad c=\frac{(1-q)(2p+r)}{(1+r-q)(2-2p-r)}.\end{align*}

Note that because of the restrictions on p, q, and r, there is no division by zero. The last step is to calculate ${\mathbb{E}}(M_1)$ . Since we start from the stationary distribution, ${\mathbb{E}}(X_1^2)=(1-q)/(1+r-q)$ , and, as a result, we get

\begin{equation*} {\mathbb{E}}(M_1) ={\mathbb{E}}(S_{1}^2+aS_{1}X_1+bX_1^2-c) ={\mathbb{E}}(X_{1}^2+aX_{1}X_1+bX_1^2-c) =(1+a+b)\frac{1-q}{1+r-q}-c.\end{equation*}

Finally, (7) leads us to

\begin{align*} {\mathbb{E}}(\tau)=AB\frac{(1+r-q)(2-2p-r)}{(1-q)(2p+r)} +(A+B)\frac{(2p+r-1)(1+r-q)}{(1-q)(2p+r)}+\frac{(q-r)r}{(1-q)(1+r-q)}.\end{align*}

As always, let us consider special cases:

• • If $r=0$ (the state 0 is ignored), then q will be canceled out and we get (5).

• • If $2p+r=1$ or $p=1-p-r$ (balanced switches between 1 and $-1$ ), then

  \begin{align*}{\mathbb{E}}(\tau)=AB\frac{1+r-q}{1-q}+\frac{(q-r)r}{(1-q)(1+r-q)}.\end{align*}

• • If $2p+r=1$ and $r=q$ (the i.i.d. symmetric random walk with delays), then ${\mathbb{E}}(\tau)=AB/(1-q)$ , a formula from [Reference Gut10].

4.3. Ruin probability for general CRWs with delays

Finding closed-form formulas in a general case might be a challenging task – the transition matrix has six free parameters. However, it is possible to develop a method that will work, at least numerically, for almost any Markov chain.

In this section $\{X_n\}_{n\geq 1}$ is a three-state Markov chain with state set $\{1, 0, -1\}$ and transition matrix

\begin{align*}\begin{pmatrix} p &\quad p_0 &\quad 1-p-p_0 \\ r_1 &\quad r &\quad 1-r-r_1\\ 1-q-q_0 &\quad q_0 &\quad q \\\end{pmatrix},\end{align*}

where $0\leq p,p_0,q,q_0,r,r_1\leq 1$ and $0\leq p+p_0,r+r_1,q+q_0\leq 1$ . We will drop here the assumption that the initial distribution is stationary. The initial distribution is given by $(\pi_1,\pi_0,1-\pi_0-\pi_1)$ , where $0\leq\pi_1,\pi_0\leq 1$ and $0\leq \pi_1+\pi_0\leq 1$ . We will employ the same notation for random walks, ruin probabilities, filtration, and stopping time.

The candidate for a martingale in the general case, as before, takes an exponential form, $M_n=\lambda^{S_n+aX_n^2+bX_n}$ . If we can find $\lambda>0$ , $\lambda\neq 1$ , a, and b that make $M_n$ a martingale, then the OST gives us ${\mathbb{E}} (M_1)={\mathbb{E}} (M_\tau)=\lambda^{A+a+b}\alpha+\lambda^{-B+a-b}(1-\alpha)$ . Therefore, we have

(8) \begin{equation} \alpha=\frac{{\mathbb{E}}(M_1)-\lambda^{-B+a-b}}{\lambda^{A+a+b}-\lambda^{-B+a-b}}.\end{equation}

So, let us try to find such $\lambda$ , a, and b. First, note that

\begin{align*} {\mathbb{E}}(M_n\mid{\mathcal{F}}_{n-1}) & = {\mathbb{E}}\big[\lambda^{S_{n-1}+aX_{n-1}^2+bX_{n-1}+a(X_n^2-X_{n-1}^2)+(b+1)X_n-bX_{n-1}}\mid{\mathcal{F}}_{n-1}\big] \\ & = M_{n-1}{\mathbb{E}}\big[\lambda^{a(X_n^2-X_{n-1}^2)+(b+1)X_n-bX_{n-1}}\mid{\mathcal{F}}_{n-1}\big].\end{align*}

Thus, we need $\lambda$ , a, and b that make the conditional expectation of $Y_n=\lambda^{a(X_n^2-X_{n-1}^2)+(b+1)X_n-bX_{n-1}}$ equal to 1. Now, our usual tricks lead us to

\begin{align*} {\mathbb{E}}(Y_n\mid{\mathcal{F}}_{n-1}) & = {\mathbb{E}}(Y_n\mid X_{n-1}=1)\mathbf{1}_{X_{n-1}=1} + {\mathbb{E}}(Y_n\mid X_{n-1}=-1)\mathbf{1}_{X_{n-1}=-1} \\ & \quad + {\mathbb{E}}(Y_n\mid X_{n-1}=0)\mathbf{1}_{X_{n-1}=0} \\ & = {\mathbb{E}}(Y_n\mid X_{n-1}=1)\frac{X_{n-1}^2+X_{n-1}}{2} + {\mathbb{E}}(Y_n\mid X_{n-1}=-1)\frac{X_{n-1}^2-X_{n-1}}{2} \\ & \quad + {\mathbb{E}}(Y_n\mid X_{n-1}=0)(1-X_{n-1}^2) \\ & = \big[{\mathbb{E}}(Y_n\mid X_{n-1}=1) + {\mathbb{E}}(Y_n\mid X_{n-1}=-1) - 2{\mathbb{E}}(Y_n\mid X_{n-1}=0)\big]\frac{X_{n-1}^2}{2} \\ & \quad + \big[{\mathbb{E}}(Y_n\mid X_{n-1}=1) - {\mathbb{E}}(Y_n\mid X_{n-1}=-1)\big]\frac{X_{n-1}}{2} + [{\mathbb{E}}(Y_n\mid X_{n-1}=0)].\end{align*}

Taking into account that

\begin{align*} {\mathbb{E}}(Y_n\mid X_{n-1}=1) & = p\lambda+p_0\lambda^{-a-b}+(1-p-p_0)\lambda^{-2b-1}, \\ {\mathbb{E}}(Y_n\mid X_{n-1}=0) & = r_1\lambda^{a+b+1}+r+(1-r-r_1)\lambda^{a-b-1}, \\ {\mathbb{E}}(Y_n\mid X_{n-1}=-1) & = (1-q-q_0)\lambda^{2b+1}+q_0\lambda^{-a+b}+q\lambda^{-1},\end{align*}

we finally get the following system of non-linear equations

(9) \begin{equation}\left\{ \begin{array}{l} p\lambda+p_0\lambda^{-a-b}+(1-p-p_0)\lambda^{-2b-1} = 1, \\[3pt] r_1\lambda^{a+b+1}+r+(1-r-r_1)\lambda^{a-b-1} = 1, \\ [3pt] (1-q-q_0)\lambda^{2b+1}+q_0\lambda^{-a+b}+q\lambda^{-1} = 1. \end{array}\right.\end{equation}

Example 1. Consider a three-state Markov chain with state set $\{1, 0, -1\}$ , transition matrix

\begin{align*} \begin{pmatrix} 1/2 &\quad 1/4 &\quad 1/4 \\ 1/3 &\quad 1/3 &\quad 1/3\\ 1/8 &\quad 1/8 &\quad 3/4 \\ \end{pmatrix}, \end{align*}

and the initial distribution (0,1,0). Then we can show that $\lambda=13/10$ , $a=-\log_{13/10}\sqrt{81/65}$ , and $b=\log_{13/10}\sqrt{20/13}$ solve system (9). Also in this case ${\mathbb{E}} (M_1)=1$ . Plugging these values into (8), we get

\begin{align*} \alpha=\frac{(18/13)(13/10)^B-1}{(20/13)(13/10)^{A+B}-1}. \end{align*}

As a simple check, set $A=B=1$ , then obviously $\alpha=0.5$ . The formula gives the same answer.

One practical recommendation is to do a re-parametrization, and use $x=\lambda$ , $y=\lambda^a$ , and $z=\lambda^b$ instead of the original $\lambda$ , a, and b. Then Mathematica easily finds solutions of the system.

This method might not work for some Markov chains, if their transition probability matrix exhibits a certain symmetry. Recall that in the i.i.d. case, $(q/p)^{S_n}$ is useless if $p=q$ . In fact, our two-pattern problem is a case of this nature.

4.4. Expected waiting time until ruin for general CRWs with delays

Using the same technique as before we can show that ${\mathbb{E}}(X_n\mid{\mathcal{F}}_{n-1})=l_2X_{n-1}^2+l_1X_{n-1}+1_0$ , where $l_2=p-q+(p_0-q_0)/2+1-r-2r_1$ , $l_1=p+q+(p_0+q_0)/2-1$ , and $l_0=2r_1+r-1$ , and that ${\mathbb{E}}(X_n^2\mid{\mathcal{F}}_{n-1})=k_2X_{n-1}^2+k_1X_{n-1}+k_0$ , where $k_2=r-(p_0+q_0)/2$ , $k_1=(q_0-p_0)/2$ , and $k_0=1-r$ . Remember that for the asymmetric i.i.d. case a simple martingale $S_n-cn$ works. Therefore, it makes sense to try a linear martingale $M_n=S_n+aX_n^2+bX_n-cn$ . Using our expressions for ${\mathbb{E}}(X_n\mid{\mathcal{F}}_{n-1})$ and ${\mathbb{E}}(X_n^2\mid{\mathcal{F}}_{n-1})$ we can show that if a, b, and c satisfy

(10) \begin{equation} \left\{ \begin{array}{l} ak_2 + (1+b)l_2 = a, \\ [3pt] ak_1 + (1+b)l_1 = b, \\[3pt] ak_0 + (1+b)l_0 = c, \\ \end{array} \right.\end{equation}

then $M_n$ is a martingale. Moreover, if $c\neq 0$ , then we get a formula for the expected time until ruin:

\begin{align*}{\mathbb{E}}(\tau)=\frac{1}{c}\big[(A+a+b)\alpha+(\!-B+a-b)(1-\alpha)-{\mathbb{E}}(M_1)\big],\end{align*}

where ${\mathbb{E}}(M_1)=\pi_1(1+a+b)+(1-\pi_1-\pi_0)(\!-1+a-b)-c$ . If we consider the Markov chain in Example 1, then our method will lead to the martingale

\begin{align*}M_n=S_n-\frac{2}{5}X_n^2+\frac{37}{45}X_n+\frac{4}{15}n.\end{align*}

5.1. HH vs TH gambler’s ruin problem

Let $\{\xi_n\}_{n\geq 1}$ be a sequence of independent Bernoulli random variables with a probability of success $\frac12$ . Then for $n\geq 2$ our payments are given by

\begin{align*}X_n=\left\{\begin{array}{cl} 1&\,\, \mbox{ if } \xi_{n-1}=1, \xi_n=1, \\ 0&\,\, \mbox{ if } \xi_n=0, \\ -1&\,\, \mbox{ if } \xi_{n-1}=0, \xi_n=1. \end{array}\right.\end{align*}

In the general case of two patterns of length 2 (for instance, HH and TT), the associated sequence of payments typically does not form a Markov chain. But for HH and TH, $\{X_n\}_{n\geq 2}$ is a first-order Markov chain with the transition matrix

\begin{align*}\begin{pmatrix} 1/2 &\quad 1/2 &\quad 0 \\ 0 &\quad 1/2 &\quad 1/2\\1/2 &\quad 1/2 &\quad 0 \\\end{pmatrix},\end{align*}

and the initial distribution $\big(\frac14, \frac12, \frac14\big)$ . This Markov chain is not symmetric in the sense of Section 4.1, but it does have a very special structure. As a result, we can easily verify that for this transition matrix there is no solution of system (9) such that $\lambda\neq 1$ .

However, we can construct a linear martingale. Note that here $S_n=X_2+\cdots+X_n$ . Since ${\mathbb{E}}(X_n\mid{\mathcal{F}}_{n-1})=X_{n-1}^2-\frac{1}{2}$ and ${\mathbb{E}}(X_n^2\mid{\mathcal{F}}_{n-1})=\frac{1}{2}$ , using our approach (or by solving the linear system (10)) we can verify that $M_n=S_n+X_n^2$ , $n\geq 2$ , is a martingale. Applying the OST to this martingale gives us

\begin{align*}\alpha=\frac{B-1/2}{A+B}.\end{align*}

A simple check in this case is that when $A=B=1$ , the formula gives $\frac14$ . This makes sense, because the only way to get to 1 is to have HH right away.

Since the linear martingale does not contain an n term, it cannot be used to compute ${\mathbb{E}}(\tau)$ . But then we can try to find a quadratic martingale similar to the one used for the symmetric CRW with delays. Indeed, we can show that $M_n=S_n^2+2S_nX_n^2+2X_n^2-n/2$ is a martingale. Applying the OST to this martingale gives us ${\mathbb{E}}(\tau)=2AB+B-A+1$ .

5.2. Gambler’s ruin probability for an arbitrary two-pattern game

As previously mentioned, for an arbitrary two-pattern game the sequence of payments typically is not a Markov chain. For example, suppose that we play this game with HH and TT. As before, let $\{X_n\}_{n\geq 2}$ be the sequence of payments, where we get 1 for HH, $-1$ for TT, and 0 otherwise. Then, for any $n\geq 2$ , we have

\begin{align*}{\mathbb{P}}(X_{2n+1}=1\mid X_{2n}=0,X_{2n-1}=0, \dots, X_3=0,X_2=1)=\frac{1}{2},\end{align*}

but ${\mathbb{P}}(X_{2n+1}=1\mid X_{2n}=0,X_{2n-1}=0, \dots, X_3=0,X_2=-1)=0$ .

However, we can still find the ruin probability using a CRW. For the rest of the section, let $\{\xi_n\}_{n\geq 1}$ be an i.i.d. sequence of letters from a finite alphabet. A sequence of letters is called a pattern. A pattern that has no letters is called a void pattern. Consider two patterns, $P=a_1a_2\dots a_k$ and $Q=b_1b_2\dots b_m$ , where $k,m\geq 1$ . Assume that P and Q are not connected subsequences of each other. Our game is the same as before: we get $1 for every (overlapping) occurrence of P and we lose a dollar if we see Q.

Let $\{X_n\}_{n\geq 1}$ be the sequence of only 1 or $-1$ payments (i.e. 0s are ignored). Then $\{X_n\}_{n\geq 1}$ is a two-state Markov chain whose initial distribution and transition probabilities can be computed with the help of the theory developed for the occurrence of patterns. More specifically, let

\begin{equation*} P^*=\left\{ \begin{array}{ll} a_2\dots a_k, & k\geq 2, \\ \mbox{void pattern}, &\, k=1; \end{array} \right. \qquad Q^*=\left\{ \begin{array}{ll} b_2\dots b_m, & m\geq 2, \\ \mbox{void pattern}, &\, m=1. \end{array} \right.\end{equation*}

Then the initial probability is $\pi_1={\mathbb{P}}$ (pattern P will occur before Q in $\{\xi_n\}_{n\geq 1}$ ). The transition probability of going from state 1 to state 1 is given by

\begin{align*}p={\mathbb{P}}(\mbox{pattern ${P}$ will occur before ${Q}$ in $\{\xi_n\}_{n\geq 1}$ given that it starts from $P^*$}),\end{align*}

and the transition probability of going from state $-1$ to state $-1$ is given by

\begin{align*}q={\mathbb{P}}(\mbox{pattern ${Q}$ will occur before ${P}$ in $\{\xi_n\}_{n\geq 1}$ given that it starts from $Q^*$}).\end{align*}

All three probabilities can be found using, for example, [Reference Li15, Theorem 3.1]. To find each probability, we need to solve a linear system with three equations. Then, we simply apply the appropriate formula from Section 3.

To close the loop, let us apply this method to the HH vs TH game. As we mentioned in Section 2, in this case $\pi_1=0.25$ . Additionally, here $P^*=Q^*=H$ , and $p=q=\frac12$ . This means that the non-zero payments in the HH vs TH game form a sequence of independent symmetric random variables, primarily because the coin is fair. Plugging these values into (3) leads us again to

\begin{align*}\alpha=\frac{B-1/2}{A+B}.\end{align*}