Competing Patterns in Bernoulli Sequence of Trials

Paul Vrbik¹, Jan Vrbik²

¹ITEE, Queensland University, Brisbane, Australia.
²Department of Mathematics and Statistics, Brock University, St. Catharines, Canada.

DOI: 10.4236/am.2023.145019                

Abstract

Consider performing a sequence of Bernoulli trials (each resulting in either a success, denoted S, or a failure F, with a probability of p and q := 1 - p respectively) until one of m specific strings (or patterns) of consecutive outcomes is generated. This can be seen as a game where m players select one such pattern each and the one whose pattern occurs first wins. We present symbolic formulas for the m probabilities of winning, and for the mean number of trials and the corresponding standard deviation to complete this game. Several numerical examples are presented, including a search for optimal strategy.

Keywords

Competing Patterns, Bernoulli Sequence of Trials, Game Theory

1. Introduction

The problem of pattern generation was first investigated by [1] and then extended by [2] and [3] . The idea of playing patterns against each other was then explored by [4] , who considered only the case of $p=\frac{1}{2}$ and all m patterns

being of the same length, and generalized by [5] to any admissible value of p and patterns being of arbitrary lengths. This article is summarizing and streamlining these results, pointing out that the existing formulas fail when m becomes large (as symbolic inversion of matrices is no longer feasible) and resolving this problem by deriving (with the help of Sherman-Morrison identity) formulas which require numerical evaluation only.

The main mathematical tool of this article is a skillful application of generating functions; a generating function of a sequence, say $a_0\mathrm{,}{a}_1\mathrm{,}{a}_2\mathrm{,}{a}_3\mathrm{,}\cdots$ is defined as $A\left(z\right):={\displaystyle {\sum }_{j=0}^{\infty }}{a}_j{z}^j$ . It is easy to see that a product of two such generating functions, say $A\left(z\right)\cdot B\left(z\right)$ , corresponds to a new sequence (called a convolution of the two sequences) with terms $a_0{b}_0$ , $a_0{b}_1+a_1{b}_0$ , $a_0{b}_2+a_1{b}_1+a_2{b}_0$ , $a_0{b}_3+a_1{b}_2+a_2{b}_1+a_3{b}_0$ , $\cdots$ .

When a sequence $p_0\mathrm{,}{p}_1\mathrm{,}{p}_2\mathrm{,}{p}_3\mathrm{,}\cdots$ is defined by $p_j=\mathrm{Pr}\left(Z=j\right)$ , where Z is an integer-valued random variable, the corresponding generating function, say $P\left(z\right)$ , is called probability generating function (PGF); to find the expected value of Z, denoted $\mathbb{E}\left(Z\right)$ or ${\mu }_z$ , one needs to evaluate $P^{\prime }\left(z\right)=p_1+2p_{2}z+3p_3{z}^2+4p_4{z}^3+\cdots$ at $z=1$ . Similarly, $P^{″}\left(z=1\right)$ yields the second factorial moment of Z, namely $\mathbb{E}\left(Z^2\right)-\mathbb{E}\left(Z\right)$ , which can be easily converted into the variance of Z, thus equal to $P^{″}\left(1\right)+P^{\prime }\left(1\right)-P^{\prime }{\left(1\right)}^2$ .

2. Generating Patterns

We first review the technique for constructing a probability generating function (PGF) of the number of trials to generate one such pattern (of specific consecutive outcomes, such as FFSF) for the first time. This requires introducing the following notation: for any pattern $\mathcal{T}$ , let ${\mathcal{T}}_k$ be the first k symbols of $\mathcal{T}$ and ${\mathcal{T}}^k$ be its last k symbols, while $\mathrm{Pr}\left(\mathcal{T}\right)$ is the probability of generating $\mathcal{T}$ in $\mathcal{l}$ trials, where $\mathcal{l}$ is the length of $\mathcal{T}$ , e.g. $\mathrm{Pr}\left(\text{FFSFSSS}\right)=p^4{q}^3$ .

For any two patterns, say $\mathcal{T}$ and $\mathcal{W}$ , $\mathcal{W}⊲\mathcal{T}$ is a set of all positive integers k such that ${\mathcal{T}}^k\equiv {\mathcal{W}}_k$ where $\equiv$ indicates a perfect match of the corresponding strings; note that this set may be empty. Let $K$ be the largest of these integers (equal to 0 when the set is empty; also: $K$ cannot be bigger than the length of either pattern), and $\mathcal{W}◀\mathcal{T}$ be the corresponding ${\mathcal{T}}^K$ (a string of zero length when $K=0$ ). Thus, for example, when $\mathcal{T}\mathrm{<mo>\; :\; </mo>}=\text{FFFSFFF}$ and $\mathcal{W}\mathrm{<mo>\; :\; </mo>}=\text{FFSFFFFSF}$ , we get $\mathcal{W}⊲\mathcal{T}=\left\{\mathrm{1,2,6}\right\}$ and $\mathcal{W}◀\mathcal{T}=\text{FFSFFF}$ , and $\mathcal{T}⊲\mathcal{W}=\left\{\mathrm{1,5}\right\}$ and $\mathcal{T}◀\mathcal{W}=\text{FFFSF}$ . Furthermore, $\mathcal{T}⊲\mathcal{T}=\left\{\mathrm{1,2,3,7}\right\}$ and $\mathcal{W}⊲\mathcal{W}=\left\{\mathrm{1,4,9}\right\}$ , implying that $\mathcal{T}◀\mathcal{T}=\mathcal{T}$ for any pattern. The $◀$ operation is easily performed by the following Mathematica code

$\begin{array}{l}H\mathrm{<mo\; stretchy="false">\; [\; </mo>}a\mathrm{<mo>\; \_\; </mo>\; ,}b\mathrm{<mo>\; \_\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; :\; </mo>}=Module\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>\; <mo>\; \{\; </mo>}n=Min\mathrm{<mo\; stretchy="false">\; [\; </mo>}Length\mathrm{<mo\; stretchy="false">\; [\; </mo>}a\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; ,}Length\mathrm{<mo\; stretchy="false">\; [\; </mo>}b\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>\; <mo\; stretchy="false">\; ]\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>\; <mo>\; \}\; </mo>\; ,}\\ While\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>}Take\mathrm{<mo\; stretchy="false">\; [\; </mo>}a\mathrm{,}n\mathrm{<mo\; stretchy="false">\; ]\; </mo>}=\mathrm{<mo>\; !\; </mo>}=Take\mathrm{<mo\; stretchy="false">\; [\; </mo>}b\mathrm{,}-n\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; ,}n=n-\mathrm{1\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; ;\; </mo>}Take\mathrm{<mo\; stretchy="false">\; [\; </mo>}a\mathrm{,}n\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>\; <mo\; stretchy="false">\; ]\; </mo>}\end{array}$ (1)

where each pattern needs to be represented by a list of zeros (for every F) and ones (for every S); to find $\mathcal{W}◀\mathcal{T}$ thus requires typing

$H\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mo>\; \{\; </mo>\; 0,0,1,0,0,0,0,1,0\; <mo>\; \}\; </mo>\; ,\; <mo>\; \{\; </mo>\; 0,0,0,1,0,0,0\; <mo>\; \}\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>}$ (2)

to obtain {0, 0, 1, 0, 0, 0}, which represents FFSFFF.

Consider generating an infinite (in principle) sequence of Bernoulli trials with repeated occurrences of a specific pattern, say $\mathcal{T}$ . Note that it is assumed that consecutive occurrences are not allowed to overlap, i.e. upon a completion of the pattern, none of its symbols can be used to help generate its next occurrence (which needs to be built from scratch—yet another way of putting it).

Let $f_n$ be the probability that the first occurrence of $\mathcal{T}$ is completed at Trial n, while $u_n$ is the probability that $\mathcal{T}$ is completed (from scratch—no help from a potential previous occurrence, but not necessarily for the first time) at Trial n. Using the total-probability formula (TPF), we can partition $u_n$ based on where the first occurrence of $\mathcal{T}$ has happened, thus getting

$u_n=f_0{u}_n+f_1{u}_{n-1}+f_2{u}_{n-2}+\cdots +f_{n-1}{u}_1+f_n{u}_0$ (3)

Note that this identity is correct for all positive integers n (not when $n=0$ ), with the understanding that $f_0=0$ and $u_0=1$ (assumed from now on).

Multiplying each side of (3) by $z^n$ and summing over n from 1 to $\infty$ yields

$U\left(z\right)-1=F\left(z\right)\cdot U\left(z\right)$ (4)

where $F\left(z\right)$ is the probability generating function (PDF) of the $f_0\mathrm{,}{f}_1\mathrm{,}{f}_2\mathrm{,}\cdots$ sequence while $U\left(z\right)$ is the generating function of the $u_0\mathrm{,}{u}_1\mathrm{,}{u}_2\mathrm{,}\cdots$ sequence. This follows from the fact that the RHS of (3) represents the n^th term of a convolution of the two sequences; note that the summation missed the $u_0=1$ term on the LHS but (since $f_0{u}_0=0$ ) no term on the RHS; subtracting 1 form $U\left(z\right)$ on the LHS of (4) is correcting for this discrepancy.

The last equation implies that

$F\left(z\right)={\left(1+\frac{1}{U\left(z\right)-1}\right)}^{-1}$ (5)

The importance of this formula rests in a relatively simple way (described shortly) of finding $U\left(z\right)$ ; (5) then easily converts it into (otherwise inaccessible) $F(\; z\; )$

To find $U\left(z\right)$ , we apply the TPF to the probability of the consecutive outcomes which define $\mathcal{T}$ being completed at Trial n (due to the non-overlapping rule, this may not constitute a legitimate occurrence of Pattern $\mathcal{T}$ ). Partitioning this (trivial) probability according to where a legitimate occurrence of $\mathcal{T}$ may have been completed yields

$\mathrm{Pr}\left(\mathcal{T}\right)={\displaystyle \underset{k\in \mathcal{T}⊲\mathcal{T}}{\sum }}{u}_{n-\mathcal{l}+k}\mathrm{Pr}\left({\mathcal{T}}^{\mathcal{l}-k}\right)$ (6)

where $\mathcal{l}$ is the length of $\mathcal{T}$ and $n\ge \mathcal{l}$ , with the understanding that $\mathrm{Pr}\left({\mathcal{T}}^0\right)=1$ . Multiplying each side of the last equation by $z^n$ and summing over n, from $\mathcal{l}$ to $\infty$ . results in

$\mathrm{Pr}\left(\mathcal{T}\right)\cdot \frac{z^{\mathcal{l}}}{1-z}=\left(U\left(z\right)-1\right)\cdot {\displaystyle \underset{k\in \mathcal{T}⊲\mathcal{T}}{\sum }}{z}^{\mathcal{l}-k}\mathrm{Pr}\left({\mathcal{T}}^{\mathcal{l}-k}\right)$ (7)

since $u_1=u_2=\cdots =u_{\mathcal{l}-1}=0$ and $u_0=1$ .

Based on (5), this further implies that

$\begin{array}{c}F\left(z\right)={\left(1+\frac{\left(1-z\right){\displaystyle \underset{k\in \mathcal{T}⊲\mathcal{T}}{\sum }}{z}^{\mathcal{l}-k}\mathrm{Pr}\left({\mathcal{T}}^{\mathcal{l}-k}\right)}{\mathrm{Pr}\left(\mathcal{T}\right)z^{\mathcal{l}}}\right)}^{-1}\mathrm{<mo>\; :\; </mo>}=\frac{1}{1+\left(1-z\right)Q\left(z\right)}\\ \simeq 1+Q\left(1\right)\cdot \left(z-1\right)+\left(Q^{\prime }\left(1\right)+Q{\left(1\right)}^2\right)\cdot {\left(z-1\right)}^2+\cdots \end{array}$ (8)

The last line represents the corresponding Taylor expansion of $F\left(z\right)$ at $z=1$ . The expected number of trials to generate $\mathcal{T}$ for the first time is given by $F^{\prime }\left(1\right)$ or equivalently (and more easily) by the linear coefficient of this expansion, namely ${\mu }_{\mathcal{T}}=Q\left(1\right)$ ; similarly, the second factorial moment equals to the quadratic coefficient further multiplied by 2; this yields

$2Q^{\prime }\left(1\right)+{\mu }_{\mathcal{T}}+{\mu }_{\mathcal{T}}^2$ (9)

for the corresponding variance.

Example 1: When $\mathcal{T}\mathrm{<mo>\; :\; </mo>}=\text{FFFSFFF}$ ,

$\begin{array}{c}Q\left(z\right)=\frac{1+\mathrm{Pr}\left(\text{SFFF}\right)z^4+\mathrm{Pr}\left(\text{FSFFF}\right)z^5+\mathrm{Pr}\left(\text{FFSFFF}\right)z^6}{\mathrm{Pr}\left(\text{FFFSFFF}\right)z^7}\\ =\frac{1+p{q}^3{z}^4+p{q}^4{z}^5+p{q}^5{z}^6}{p{q}^6{z}^7}\end{array}$ (10)

since, when observing $\text{<mover accent="true"> <mi> F </mi> <mo> ˙ </mo> </mover> <mover accent="true"> <mi> F </mi> <mo> ˙ </mo> </mover> <mover accent="true"> <mi> F </mi> <mo> ˙ </mo> </mover> SFF <mover accent="true"> <mi> F </mi> <mo> ˙ </mo> </mover>}$ at the last $\mathcal{l}$ trials, the actual pattern may have been completed at any one of the trials indicated by a dot. This then yields ${\mu }_{\mathcal{T}}=Q\left(1\right)=\frac{1+p{q}^3+p{q}^4+p{q}^5}{p{q}^6}$ and $Q^{\prime }\left(1\right)=-\frac{7}{p{q}^6}-\frac{3}{q^3}-\frac{2}{q^2}-\frac{1}{q}$ , easily converted into a variance formula. $■$

Finding $Q\left(z\right)$ for any specific pattern is made routine by the following Mathematica function

$\begin{array}{l}Q\mathrm{<mo\; stretchy="false">\; [\; </mo>}x\mathrm{<mo>\; \_\; </mo>}\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mo>\; :\; </mo>}=Module\mathrm{<mo\; stretchy="false">\; [\; </mo>}\mathrm{<mo>\; \{\; </mo>}h=\mathrm{0,}n=Length\mathrm{<mo\; stretchy="false">\; [\; </mo>}x\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>\; <mo>\; \}\; </mo>\; ,}\\ Do\mathrm{<mo\; stretchy="false">\; [\; </mo>}h=h+If\mathrm{<mo\; stretchy="false">\; [\; </mo>}Take\mathrm{<mo\; stretchy="false">\; [\; </mo>}x\mathrm{,}k\mathrm{<mo\; stretchy="false">\; ]\; </mo>}==Take\mathrm{<mo\; stretchy="false">\; [\; </mo>}x\mathrm{,}-k\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; ,}\\ \mathrm{<mo\; stretchy="false">\; (\; </mo>}pz\mathrm{<mo\; stretchy="false">\; )\; </mo>}^Total\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>}Drop\mathrm{<mo\; stretchy="false">\; [\; </mo>}x\mathrm{,}k\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}qz\mathrm{<mo\; stretchy="false">\; )\; </mo>}^Total\mathrm{<mo\; stretchy="false">\; [\; </mo>\; 1}-Drop\mathrm{<mo\; stretchy="false">\; [\; </mo>}x\mathrm{,}k\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>\; <mo\; stretchy="false">\; ]\; </mo>\; ,0\; <mo\; stretchy="false">\; ]\; </mo>\; ,\; <mtext>\; \hspace{0.17em}\; </mtext>\; <mo>\; \{\; </mo>}k\mathrm{,}n\mathrm{<mo>\; \}\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; ;\; </mo>}\\ h\mathrm{<mo>\; /\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}pz\mathrm{<mo\; stretchy="false">\; )\; </mo>}^Total\mathrm{<mo\; stretchy="false">\; [\; </mo>}x\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mo>\; /\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}qz\mathrm{<mo\; stretchy="false">\; )\; </mo>}^Total\mathrm{<mo\; stretchy="false">\; [\; </mo>\; 1}-x\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>\; <mo\; stretchy="false">\; ]\; </mo>}\end{array}$ (11)

Thus, using the same $\mathcal{T}$ as our example, typing Q[{0, 0, 0, 1, 0, 0, 0}] results in the last line of (10); the expected number of trials to complete $\mathcal{T}$ and the corresponding variance can be easily found by evaluating this expression and its z derivative at $z=1$ , as already indicated.

Subsequently, we will also need the PGF of a number of extra trials to generate the next occurrence of a pattern $\mathcal{T}$ , given that pattern $\mathcal{W}$ has just been completed and $\mathcal{T}$ is allowed to utilize any of its symbols (i.e. $\mathcal{T}$ may overlap with $\mathcal{W}$ whenever possible, up to and including $\mathcal{T}◀\mathcal{W}$ ). This PGF, denoted $F_{\mathcal{T}\mathrm{<mo>\; |\; </mo>}\mathcal{W}}\left(z\right)$ and called conditional, is found by realizing that, to generate the first occurrence of $\mathcal{T}$ from scratch, $\mathcal{T}◀\mathcal{W}$ must be generated first, while the remaining (independent) trials to complete $\mathcal{T}$ are those of $\mathcal{T}\mathrm{<mo>\; |\; </mo>}\mathcal{W}$ . This implies that

$F_{\mathcal{T}}\left(z\right)=F_{\mathcal{T}◀\mathcal{W}}\left(z\right)\cdot F_{\mathcal{T}\mathrm{<mo>\; |\; </mo>}\mathcal{W}}\left(z\right)$ (12)

where $F_{\mathcal{T}}\left(z\right)$ is just a new notation for $F\left(z\right)$ of $\mathcal{T}$ , $F_{\mathcal{T}◀\mathcal{W}}\left(z\right)$ is a similarly constructed $F\left(z\right)$ of $\mathcal{T}◀\mathcal{W}$ , and the conditional $F_{\mathcal{T}\mathrm{<mo>\; |\; </mo>}\mathcal{W}}\left(z\right)$ is a simple solution of (12).

3. Competing Patterns

Let us now consider m such patterns with individual PGFs denoted $F_i\left(z\right)$ , where $i=\mathrm{1,2},\cdots ,m$ , and the corresponding $z^n$ coefficients are $f_{i\mathrm{,}n}$ . Similarly, the conditional PGFs for the number of trials to generate Pattern $i$ with the help of Pattern $j$ are denoted $F_{i\mathrm{<mo>\; |\; </mo>}j}\left(z\right)$ when $i\ne j$ , and their coefficients are $f_{i\mathrm{<mo>\; |\; </mo>}j\mathrm{,}n}$ (where $f_{i\mathrm{<mo>\; |\; </mo>}j\mathrm{,0}}=0$ ). The probability that Pattern $i$ is generated, for the first time (and thus winning the game) before any of the other pattern occurs, at Trial n is denoted $x_{i\mathrm{,}n}$ (with $x_{i\mathrm{,0}}=0$ ); the corresponding generating function is $X_i\left(z\right)$ . We assume that none of these patterns is a sub-string of any of the others (which would either prevent it from winning the game, or allow it to be completed at the same time as the other pattern).

We assume that n trials have been completed, and we use TPF to partition $f_{i\mathrm{,}n}$ (the probability that Pattern $i$ has been completed, for the first time, at Trial n) according to which of the other patterns may have won the game at Trial k (for $k=\mathrm{1,2,}\cdots \mathrm{,}n$ ). This yields, for any non-negative n,

$f_{i\mathrm{,}n}={\displaystyle \underset{j\ne i}{\overset{m}{\sum }}}{\displaystyle \underset{k=1}{\overset{n}{\sum }}}{x}_{j\mathrm{,}k}\cdot f_{i\mathrm{<mo>\; |\; </mo>}j\mathrm{,}n-k}+x_{i\mathrm{,}n}$ (13)

Multiplying by $z^n$ and summing over n from 0 to $\infty$ converts these equations into

$F_i\left(z\right)={\displaystyle \underset{j\ne i}{\overset{m}{\sum }}}{X}_j\left(z\right)\cdot F_{i\mathrm{<mo>\; |\; </mo>}j}\left(z\right)+X_i\left(z\right)={\displaystyle \underset{j=1}{\overset{m}{\sum }}}{X}_j\left(z\right)\cdot F_{i\mathrm{<mo>\; |\; </mo>}j}\left(z\right)$ (14)

by setting $F_{i\mathrm{<mo>\; |\; </mo>}i}\left(z\right)=1$ , in agreement with (12). Dividing by $F_i\left(z\right)$ and switching sides makes these m linear equations for $X_j\left(z\right)$ into

$F_{i◀j}{\left(z\right)}^{-1}\cdot X_j\left(z\right)=1$ (15)

which has a simple matrix-algebra solution, namely

$X\left(z\right)=\mathbb{G}{\left(z\right)}^{-1}\circ 1$ (16)

where $X\left(z\right)$ is a vector whose components are the $X_j\left(z\right)$ generating functions, $\mathbb{G}\left(z\right)$ is a matrix whose ${\left(i\mathrm{,}j\right)}^{\text{th}}$ element is equal to $F_{i◀j}{\left(z\right)}^{-1}$ , $1$ is a column vector with all m components equal to 1, and the small circle implies matrix multiplication.

The probability of Pattern $j$ winning the game is then given by the value of $X_j\left(z\right)$ at $z=1$ ; since $\mathbb{G}\left(1\right)$ is a highly singular matrix of rank 1, this value can be found only by taking the $z\to 1$ limit of the RHS of (16). But the RHS itself is increasingly more difficult to compute as m increases, since inverting large matrices symbolically (note that $F_{i◀j}{\left(z\right)}^{-1}$ are all functions of z) is practically impossible.

We can bypass this problem by expanding each $F_{i◀j}{\left(z\right)}^{-1}$ at $z=1$ , which yields $1-{\mu }_{i◀j}\cdot \left(z-1\right)+\cdots$ , where ${\mu }_{i◀j}={F^{\prime }}_{i◀j}\left(1\right)=Q_{i◀j}\left(1\right)$ , i.e. the expected number of trials to generate $i◀j$ . This further implies that, to the $O\left({\left(z-1\right)}^2\right)$ accuracy,

$\mathbb{G}\left(z\right)\simeq 1\circ 1^{\text{T}}+\mathbb{K}\cdot \left(1-z\right)+\cdots$ (17)

where $\mathbb{K}$ is a matrix of the $Q_{i◀j}\left(1\right)$ values. Using Sherman-Morrison formula, we get, to the same accuracy

${\left(1\circ 1^{\text{T}}+\mathbb{K}\cdot \left(1-z\right)\right)}^{-1}\simeq \frac{{\mathbb{K}}^{-1}}{1-z}-\frac{{\mathbb{K}}^{-1}}{1-z}\circ \left(\frac{1\circ 1^{\text{T}}\circ {\mathbb{K}}^{-1}}{1-z+1^{\text{T}}\circ {\mathbb{K}}^{-1}\circ 1}\right)$ (18)

Post-multiplying by $1$ then enables us to approximate $X\left(z\right)$ by

$\frac{{\mathbb{K}}^{-1}}{1-z}\circ \left(1-\frac{1\circ 1^{\text{T}}\circ {\mathbb{K}}^{-1}\circ 1}{1-z+1^{\text{T}}\circ {\mathbb{K}}^{-1}\circ 1}\right)=\frac{{\mathbb{K}}^{-1}\circ 1}{z-1+1^{\text{T}}\circ {\mathbb{K}}^{-1}\circ 1}$ (19)

resulting in

$\underset{z\to 1}{lim}X\left(z\right)=\frac{{\mathbb{K}}^{-1}\circ 1}{1^{\text{T}}\circ {\mathbb{K}}^{-1}\circ 1}$ (20)

Example 2: When playing patterns FFFSF, SFSSS, FFFSS and SSSFS against each other while $p=q=\frac{1}{2}$ (tossing a fair coin), the four probabilities of winning are computed by the following Mathematica code

$\begin{array}{l}T=\mathrm{<mo>\; \{\; </mo>\; <mo>\; \{\; </mo>\; 0,0,0,1,0\; <mo>\; \}\; </mo>\; ,\; <mo>\; \{\; </mo>\; 1,0,1,1,1\; <mo>\; \}\; </mo>\; ,\; <mo>\; \{\; </mo>\; 0,0,0,1,1\; <mo>\; \}\; </mo>\; ,\; <mo>\; \{\; </mo>\; 1,1,1,0,1\; <mo>\; \}\; </mo>\; <mo>\; \}\; </mo>\; <mo>\; ;\; </mo>}\\ p=q=\mathrm{0.5\; <mo>\; ;\; </mo>}Kinv=Inverse\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}L=Map\mathrm{<mo\; stretchy="false">\; [\; </mo>}Q\mathrm{,}Outer\mathrm{<mo\; stretchy="false">\; [\; </mo>}H\mathrm{,}T\mathrm{,}T\mathrm{,1\; <mo\; stretchy="false">\; ]\; </mo>\; ,\; <mo>\; \{\; </mo>\; 2\; <mo>\; \}\; </mo>}\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>\; .}z->\mathrm{1\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; ;\; </mo>}\\ \mathrm{<mo\; stretchy="false">\; (\; </mo>}Kinv\mathrm{.}Table\mathrm{<mo\; stretchy="false">\; [\; </mo>\; 1,}Lenth\mathrm{<mo\; stretchy="false">\; [\; </mo>}T\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}M=\mathrm{1\; <mo>\; /\; </mo>}Total\mathrm{<mo\; stretchy="false">\; [\; </mo>}Kinv\mathrm{,2\; <mo\; stretchy="false">\; ]\; </mo>}\mathrm{<mo\; stretchy="false">\; )\; </mo>\; <mo>\; /\; </mo>\; <mo>\; /\; </mo>}Simplify\end{array}$ (21)

resulting in 0.3113, 0.2058, 0.3113 and 0.1716 respectively (these are huge differences by gambling standards). Note that now (after p has been assigned a specific value) the computation of the matrix inverse is purely numerical, posing no problem even when hundreds of patterns are involved. $■$

4 Game’s Duration

The PGF of the number of trials to complete any such game is given by

${\displaystyle \underset{j=1}{\overset{m}{\sum }}}{X}_j\left(z\right)=1^{\text{T}}\circ \mathbb{G}{\left(z\right)}^{-1}\circ 1\simeq \frac{1^{\text{T}}\circ {\mathbb{K}}^{-1}\circ 1}{1-z+1^{\text{T}}\circ {\mathbb{K}}^{-1}\circ 1}$ (22)

where the last approximation no longer lets us compute individual probabilities of the distribution, but it is sufficient to find the corresponding expected value; all we need to do is to differentiate the expression with respect to z and substitute $z=1$ , resulting in

$M\mathrm{<mo>\; :\; </mo>}=\frac{1}{1^{\text{T}}\circ {\mathbb{K}}^{-1}\circ 1}$ (23)

An alternate way of deriving both (20) and the last formula is based on an elegant probabilistic argument expounded in [5] .

To derive a similar formula for the corresponding variance (which, unlike M, necessitates using the novel approach of this article), we need to extend the expansion of $F_{i◀j}{\left(z\right)}^{-1}$ to reach an $O\left({\left(z-1\right)}^3\right)$ accuracy, thus getting

$1-{\mu }_{i◀j}\cdot \left(z-1\right)-{Q^{\prime }}_{i◀j}\left(1\right)\cdot {\left(z-1\right)}^2+\cdots$ (24)

This further implies that, to the same accuracy,

$\mathbb{G}\left(z\right)\simeq 1\circ 1^{\text{T}}+\mathbb{K}\cdot \left(1-z\right)-\mathbb{L}\cdot {\left(1-z\right)}^2+\cdots$ (25)

where $\mathbb{L}$ is the matrix of the ${Q^{\prime }}_{i◀j}\left(1\right)$ values. To correspondingly extend the accuracy of the RHS of (22), we only need to replace ${\mathbb{K}}^{-1}$ by

${\left(\mathbb{K}-\mathbb{L}\cdot \left(1-z\right)\right)}^{-1}\simeq {\mathbb{K}}^{-1}+\left(1-z\right)\cdot {\mathbb{K}}^{-1}\circ \mathbb{L}\circ {\mathbb{K}}^{-1}$ (26)

therein. The second derivative of the resulting expression, evaluated at $z=1$ , yields the corresponding second factorial moment, namely

$2M^2\cdot \left(1+1^{\text{T}}\circ {\mathbb{K}}^{-1}\circ \mathbb{L}\circ {\mathbb{K}}^{-1}\circ 1\right)$ (27)

Adding M and subtracting $M^2$ then yields a formula for the variance of the number of trials to complete the game, namely

$M^2\cdot \left(1+2\cdot 1^{\text{T}}\circ {\mathbb{K}}^{-1}\circ \mathbb{L}\circ {\mathbb{K}}^{-1}\circ 1\right)+M$ (28)

Continuing Example 2: Extending the previous Mathematica program (where $M\mathrm{<mo>\; =\; </mo>\; 10.58}$ has already been computed) by

$M^\mathrm{2\; <mo\; stretchy="false">\; (\; </mo>\; 1}+2Total\mathrm{<mo\; stretchy="false">\; [\; </mo>}Kinv\mathrm{.\; <mo\; stretchy="false">\; (\; </mo>}D\mathrm{<mo\; stretchy="false">\; [\; </mo>}L\mathrm{,}z\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mo>\; /\; </mo>\; .}z->\mathrm{1\; <mo\; stretchy="false">\; )\; </mo>\; .}Kinv\mathrm{,2\; <mo\; stretchy="false">\; ]\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>\; <mo\; stretchy="false">\; )\; </mo>}+M$ (29)

results in 31.96 for this variance, and 5.65 for the corresponding standard deviation. $■$

Monte-Carlo Verification

We have randomly generated about hundred thousand rounds of the game of Example 2, using the following Mathematica code

$\begin{array}{l}T=\mathrm{<mo>\; \{\; </mo>\; <mo>\; \{\; </mo>\; 0,0,0,1,0\; <mo>\; \}\; </mo>\; ,\; <mo>\; \{\; </mo>\; 1,0,1,1,1\; <mo>\; \}\; </mo>\; ,\; <mo>\; \{\; </mo>\; 0,0,0,1,1\; <mo>\; \}\; </mo>\; ,\; <mo>\; \{\; </mo>\; 1,1,1,0,1\; <mo>\; \}\; </mo>\; <mo>\; \}\; </mo>\; <mo>\; ;\; </mo>}p=q=\mathrm{0.5\; <mo>\; ;\; </mo>}\\ r=\mathrm{<mo>\; \{\; </mo>\; <mo>\; \}\; </mo>\; <mo>\; ;\; </mo>}Do\mathrm{<mo\; stretchy="false">\; [\; </mo>}X=RandomInteger\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>\; <mo>\; \{\; </mo>\; 0,1\; <mo>\; \}\; </mo>\; ,10}^\mathrm{4\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; ;\; </mo>}While\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mtext>\; \hspace{0.17em}\; </mtext>}Length\mathrm{<mo\; stretchy="false">\; [\; </mo>}X\mathrm{<mo\; stretchy="false">\; ]\; </mo>}>\mathrm{40,}j=\mathrm{5\; <mo>\; ;\; </mo>}\\ While\mathrm{<mo\; stretchy="false">\; [\; </mo>}Length\mathrm{<mo\; stretchy="false">\; [\; </mo>}a=Position\mathrm{<mo\; stretchy="false">\; [\; </mo>}Map\mathrm{<mo\; stretchy="false">\; [\; </mo>}Take\mathrm{<mo\; stretchy="false">\; [\; </mo>}X\mathrm{,5\; <mo\; stretchy="false">\; ]\; </mo>}==\mathrm{<mo>\; \#\; </mo>\; <mo>\; \&\; </mo>\; ,}T\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; ,}True\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>}==\mathrm{0,}j=j+\mathrm{1\; <mo>\; ;\; </mo>}\\ X=Drop\mathrm{<mo\; stretchy="false">\; [\; </mo>}X\mathrm{,1\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; ;\; </mo>}X=Drop\mathrm{<mo\; stretchy="false">\; [\; </mo>}X\mathrm{,5\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; ;\; </mo>}r=Append\mathrm{<mo\; stretchy="false">\; [\; </mo>}r\mathrm{,\; <mo>\; \{\; </mo>}a\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mo\; stretchy="false">\; [\; </mo>\; 1,1\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; ,}j\mathrm{<mo>\; \}\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; ,106\; <mo\; stretchy="false">\; ]\; </mo>}\\ BitCounts\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mo\; stretchy="false">\; (\; </mo>}a=Transpose\mathrm{<mo\; stretchy="false">\; [\; </mo>}r\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; [\; </mo>\; <mo\; stretchy="false">\; [\; </mo>\; 1\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; ,\; <mo>\; \{\; </mo>\; 1,5,1\; <mo>\; \}\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; /\; </mo>}Length\mathrm{<mo\; stretchy="false">\; [\; </mo>}r\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mo>\; /\; </mo>\; <mo>\; /\; </mo>}N\end{array}$ (30)

This produces a set of relative frequencies (one for each pattern) of winning the game; in our case, we obtained 0.310, 0.205, 0.313 and 0.171, in excellent agreement with the earlier computed theoretical probabilities. Similarly, the following extra line

$\mathrm{<mo>\; \{\; </mo>}Mean\mathrm{<mo\; stretchy="false">\; [\; </mo>}a\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mo\; stretchy="false">\; [\; </mo>\; 2\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; ,}StandardDeviation\mathrm{<mo\; stretchy="false">\; [\; </mo>}a\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mo\; stretchy="false">\; [\; </mo>\; 2\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; \}\; </mo>\; <mo>\; /\; </mo>\; <mo>\; /\; </mo>}N$ (31)

yields the average number of trials per game and the corresponding (sample) standard deviation; in our case these are 10.52 and 5.60 respectively (again, in good agreement with the theoretical values of Example 2).

5. More Examples

Example 3: To demonstrate that the algorithm (and the corresponding Mathematica code) can easily accommodate patterns of different lengths, we now play SSS, SFFFFFFFFFFFS, and twenty-one F’s followed by a single S against each other, where S represents getting a six and F stands for any other value when rolling a die.

This requires changing the definition of $\mathcal{T}$ in (21) to

$T=\mathrm{<mo>\; \{\; </mo>\; <mo>\; \{\; </mo>\; 1,1,1\; <mo>\; \}\; </mo>\; ,}Flatten\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mo>\; \{\; </mo>\; 1,}Table\mathrm{<mo\; stretchy="false">\; [\; </mo>\; 0,11\; <mo\; stretchy="false">\; ]\; </mo>\; ,1\; <mo>\; \}\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; ,}Append\mathrm{<mo\; stretchy="false">\; [\; </mo>}Table\mathrm{<mo\; stretchy="false">\; [\; </mo>\; 0,21\; <mo\; stretchy="false">\; ]\; </mo>\; ,1\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; \}\; </mo>}$ (32)

and replacing p = q = 0.5; by p = 1/6.; q = 5/6., thus getting 0.343, 0.323 and 0.335 respectively for the probabilities of winning, and 92.35 and 79.99 for the expected number of rolls and the corresponding standard deviation.

Example 4: Here we investigate how changing the p value affects the winning probabilities when all six patterns of length four with exactly two S’s each are played against each other. This now requires the following changes in (21)

$Clear\mathrm{<mo\; stretchy="false">\; [\; </mo>}p\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mo>\; ;\; </mo>}q=1-p\mathrm{<mo>\; ;\; </mo>}T=Permutations\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mo>\; \{\; </mo>\; 0,0,1,1\; <mo>\; \}\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; ;\; </mo>}$ (33)

After executing the program, the following extra line

$Plot\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mi>\; \%\; </mi>\; ,\; <mo>\; \{\; </mo>}p\mathrm{,0,1\; <mo>\; \}\; </mo>\; ,}PlotStyle->\mathrm{<mo>\; \{\; </mo>}Red\mathrm{,}Blue\mathrm{,}Yellow\mathrm{,}Green\mathrm{,}Brown\mathrm{,}Black\mathrm{<mo>\; \}\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>}$ (34)

results in six graphs of Figure 1, indicating that FFSS (red) has always a better chance of winning than FSFS (blue) which in turn has higher probability than SFFS (green); for the remaining three patterns, it is the corresponding complement. Also, the former group of patterns has a substantial advantage over the latter group when p is small, and the opposite happens when p is large.

To find the value of p which maximizes the probability of FFSS winning, we have to add another line of code, namely

$p\mathrm{<mo>\; /\; </mo>\; .}NSolve\mathrm{<mo\; stretchy="false">\; [\; </mo>}D\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mi>\; \%\; </mi>\; <mi>\; \%\; </mi>\; <mo\; stretchy="false">\; [\; </mo>\; <mo\; stretchy="false">\; [\; </mo>\; 1\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; ,}p\mathrm{<mo\; stretchy="false">\; ]\; </mo>}==\mathrm{0,}p\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; [\; </mo>\; <mo\; stretchy="false">\; [\; </mo>\; 6\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>}$ (35)

to get 0.1039 (similarly, SSFF would have its best chance of winning at $p=0.8961$ ).

Example 5: Finally, assuming that each of our opponents has selected his pattern already, and we are then allowed to choose ours, the question is how do we do that to maximize our chances of winning. The following program indicates (using a specific situation) how to get the answer by simply trying all permissible possibilities.

Using $p=0.5$ and SSFSFF, SSFFFF, FFSFFF, SFFSFS for the opponents’ choices (when all patterns must be of length six), the following few lines of code

$\begin{array}{l}p=q=\mathrm{0.5\; <mo>\; ;\; </mo>}T=\mathrm{<mo>\; \{\; </mo>\; <mo>\; \{\; </mo>\; 1,1,0,1,0,0\; <mo>\; \}\; </mo>\; ,\; <mo>\; \{\; </mo>\; 1,1,0,0,0,0\; <mo>\; \}\; </mo>\; ,\; <mo>\; \{\; </mo>\; 0,0,1,0,0,0\; <mo>\; \}\; </mo>\; ,\; <mo>\; \{\; </mo>\; 1,0,0,1,0,1\; <mo>\; \}\; </mo>\; <mo>\; \}\; </mo>\; <mo>\; ;\; </mo>}\\ W=Complement\mathrm{<mo\; stretchy="false">\; [\; </mo>}Flatten\mathrm{<mo\; stretchy="false">\; [\; </mo>}Apply\mathrm{<mo\; stretchy="false">\; [\; </mo>}Outer\mathrm{<mo\; stretchy="false">\; [\; </mo>}List\mathrm{,\; <mo>\; \#\; </mo>\; <mo>\; \#\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; \&\; </mo>\; ,}Table\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mo>\; \{\; </mo>\; 0,1\; <mo>\; \}\; </mo>\; ,6\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; ,5\; <mo\; stretchy="false">\; ]\; </mo>\; ,}T\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mo>\; ;\; </mo>}\\ r=\mathrm{<mo>\; \{\; </mo>\; <mo>\; \}\; </mo>\; <mo>\; ;\; </mo>}Do\mathrm{<mo\; stretchy="false">\; [\; </mo>}WT=Prepend\mathrm{<mo\; stretchy="false">\; [\; </mo>}T\mathrm{,}W\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mo\; stretchy="false">\; [\; </mo>}i\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; ;\; </mo>}\\ Kinv=Inverse\mathrm{<mo\; stretchy="false">\; [\; </mo>}Map\mathrm{<mo\; stretchy="false">\; [\; </mo>}Q\mathrm{,}Outer\mathrm{<mo\; stretchy="false">\; [\; </mo>}H\mathrm{,}WT\mathrm{,}WT\mathrm{,1\; <mo\; stretchy="false">\; ]\; </mo>\; ,\; <mo>\; \{\; </mo>\; 2\; <mo>\; \}\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; /\; </mo>\; .}z->\mathrm{1\; <mo>\; ;\; </mo>}\\ r=Append\mathrm{<mo\; stretchy="false">\; [\; </mo>}r\mathrm{,\; <mo\; stretchy="false">\; (\; </mo>}Kinv\mathrm{.}Table\mathrm{<mo\; stretchy="false">\; [\; </mo>\; 1,5\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; )\; </mo>\; <mo\; stretchy="false">\; [\; </mo>\; <mo\; stretchy="false">\; [\; </mo>\; 1\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; /\; </mo>}Total\mathrm{<mo\; stretchy="false">\; [\; </mo>}Kinv\mathrm{,2\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; ,\; <mo>\; \{\; </mo>}i\mathrm{,60\; <mo>\; \}\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>}\\ \mathrm{<mo>\; \{\; </mo>}a=Max\mathrm{<mo\; stretchy="false">\; [\; </mo>}r\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; ,}W\mathrm{<mo\; stretchy="false">\; [\; </mo>\; <mo\; stretchy="false">\; [\; </mo>}Position\mathrm{<mo\; stretchy="false">\; [\; </mo>}r\mathrm{,}a\mathrm{<mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; [\; </mo>\; <mo\; stretchy="false">\; [\; </mo>\; 1,1\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo\; stretchy="false">\; ]\; </mo>\; <mo>\; \}\; </mo>}\end{array}$ (36)

yield (practically instantaneously) the best winnig chance of 0.2627 if we select SSFFSF. Note that FFFFFF would be the worst possible choice, reducing our probability of winning to 0.0403 only.

6. Conclusions

We have summarized and extended the existing theory of pattern generation with the aim of making it accessible to wide audience; the only prerequisites to understanding our derivation of key formulas is a rudimentary knowledge of matrices and generating functions. We have deliberately tried to make our exposition as brief as possible, not to obstruct fundamental issues with less important

Figure 1. Probabilities of winning.

details. In this closing section we will only indicate the directions in which the study of pattern competition can be extended, in most cases rather routinely.

The first modification assumes that, instead of having two possibilities for an outcome (our S and F), there may be three or more (e.g. rolling a die can result in showing one of six numbers); on closer reflection one can see that the formulas presented in this article remain practically unchanged (only the p and q probabilities need to be replaced by $p_1\mathrm{,}{p}_2\mathrm{,}{p}_3\mathrm{,}\cdots$ ).

Secondly, it is also possible to employ generating functions to investigate the distribution of number of occurrences of a specific pattern, or the number of games (playing several patterns against each other), to be completed in a fixed number of trials.

Finally, one can modify the game in such a way that a pattern can win only after completing a specific number of its occurrences (before any of the other patterns can do the same); here, there are several possibilities in terms of which occurrences (e.g. of like patterns only, dissimilar patterns only, all patterns, etc.) may be allowed to overlap and thus help generate the next one. We leave these for our readers to explore.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Feller, W. (1968) An Introduction to Probability Theory and Its Applications, Vol. 1. 3rd Edition, John Wiley & Sons, New York.
[2]	Li, S.R. (1980) A Martingale Approach to the Study of Occurrences of Sequence Patters in Repeated Experiments. Annals of Probability, 8, 1171-1176. https://doi.org/10.1214/aop/1176994578
[3]	Guibas, L.J. and Odlyzko, A.M. (1981) String Overlaps, Pattern Matching and Nontransitive Games. Journal of Combinatorial Theory A, 30, 183-208. https://doi.org/10.1016/0097-3165(81)90005-4
[4]	Blom, G. and Thornburn, D. (1982) How Many Random Digits Are Required Until Given Sequences Are Obtained? Journal of Applied Probability, 19, 518-531. https://doi.org/10.2307/3213511
[5]	Vrbik, J. and Vrbik, P. (2015) Playing Several Patterns against One Another. arXiv:1507.01322