A Number of look-back runs until a stopping time for higher order Markov chain

Let {X_j:j≥-m+1} be a homogeneous Markov chain of order m taking values in {0,1}. For j=0,-1,…,-l+1, we will set R_j=0 and we define R_j=∏_(i=j-1)^(j-l) (1- ├ R_i ) ∏_(i=j)^(j+k-1) X_i. Now R_j=1 implies that an l-look-back run of length k has occured starting at j. Here R_j is defined inductively as a run of 1 's starting at j, provided that no l-look-back run of length k occurs, starting at time j-1,j-2,…,j-l respectively. We study the conditional distribution of the number of l_1-look-back runs of length k_1 until the stopping time i.e. the r-th occurrence of the l-look-back run of length k where k_1≤k and obtain it's probability generating function. The number of l_1-look-back runs of length k_1 until the stopping time has been expressed as the sum of r independent random variables with the first random variable having a slightly different distribution under certain conditions.

Illustrations explain the paper; they do not show study data.

AI-generated illustration

↗ Enlarge

Study overviewClose ×

AI-generated conceptual illustration (A sequence of interconnected colored spheres representing states in a stochastic process). It explains the idea and does not show study data.

Open full-size image ↗

Introduction

The theory of distributions of runs has been studied extensively since Feller [1968] [8] introduced runs as an example of a renewal event. This field has received a lot of interest among researchers. Various new techniques such as Markov embedding technique (refer Fu and Koutras [1994]) [9] , method of conditional probability generating functions (refer Ebneshahrashoob & Sobel [1990]) [7] etc. have been developed to study interesting features of the distributions of runs of different type. We consider an 𝑚-th order homogeneous {0,1}-valued Markov chain. Further, we assume that the initial condition {𝑋 0 = 𝑥 0 , 𝑋 -1 = 𝑥 1 , … , 𝑋 -𝑚+1 = 𝑥 𝑚-1 } is given to us. The state 1 is associated with success in an experiment while state 0 for failure. A run of length 𝑘 is a consecutive occurrence of 𝑘 successes. The l-look-back counting scheme for runs was introduced by Anuradha [2022𝑎]. In this scheme, if a run has been counted starting at time i, i.e., {𝑋 i = 𝑋 i+1 = ⋯ = 𝑋 i+k-1 = 1}, then no runs can be counted till the time point 𝑖 + 𝑙 and the next counting of runs can start only from the time point 𝑖 + 𝑙 + 1. This scheme is repeated every time a run is counted. In other words, if a run is counted starting at time i, there are k consecutive successes from the time point i and no runs of length k can be counted which start at the time points 𝑖 -1, 𝑖 -2, … , 𝑖 -𝑙. The look-back counting scheme generalizes the concept of run counting and encompasses both the definitions of overlapping counting as well as the non-overlapping counting and also gives rise to new objects for further study. Clearly, if 𝑙 = 0, this counting scheme of run matches exactly with the counting of overlapping runs of length k, whereas if we consider 𝑙 = 𝑘 -1, then this counting scheme results in the counting of non-overlapping runs of length k. Under the set-up of m-th order homogeneous Markov chain, Anuradha [2022a] [3] proved that the waiting time distribution of the n-th occurrence of the l-look-back run of length k converges to an extended Poisson distribution when the system exhibits strong propensity towards success. Under the same set up, central limit theorem was established for the number of l-look-back runs of length k till the n-th trial. Anuradha [2022b] [4] obtained the conditional distribution of the number of runs of a fixed length or more till the r-th occurrence of l-look-back run of length k when the underlying random variables follow an m-th order Markov chain and identified the form of conditional distribution.

In order to understand the practical use of the 𝑙-look-back counting scheme for runs of length 𝑘 with 𝑙 < 𝑘, we consider the following example. Suppose an experiment is conducted to study the efficiency of a particular drug to control the symptom of illness. Here observations are taken every hour for the presence (success) or absence (failure) of a particular symptom, say, fever exceeding a specific temperature. If we observe the presence of the symptom for 𝑘 successive hours, a drug has to be administered; however, as is the case with most drugs, once the drug is administered, we have to wait for 𝑙 hours for the next administration of the drug with 𝑙 < 𝑘. But the process of the observation for the presence or absence of the symptom is continued as ever. In this experiment, the number of administrations of the drug until the time point 𝑛, is the number of 𝑙-look-back runs of length 𝑘 up to time 𝑛. Aki and Hirano [1994] [1] studied the marginal distributions of failures, successes and success-runs of length less than 𝑘 until the first occurrence of consecutive 𝑘 successes where the underlying random variables are either i.i.d. or homogeneous Markov chain or binary sequence of order . Aki and Hirano [1995] [5] derived the joint distributions of failures, successes and success-runs for the same set-up. Hirano et al. [1997] [10] obtained the distributions of number of success-runs of length 𝑙 for various counting schemes like runs of length 𝑘 1 , overlapping runs of length 𝑘 1 , non-overlapping of length 𝑘 1 etc. until the first occurrence of the success-run of length 𝑘 for a 𝑚-th order homogeneous Markov chain where 𝑚 ≤ 𝑙 < 𝑘. Uchida [1998] [11] studied the joint distributions of the waiting time and the number of outcomes such as failures, successes and success-runs of length less than 𝑘 for various counting schemes of runs for an 𝑚-th order homogeneous Markov chain. Chadjiconstantindis and Koutras [2001] [6] also obtained the distribution of failures and successes in a waiting time problem. In this paper, we obtain the distribution of 𝑙 1 -lookback runs of length 𝑘 1 , until a specified stopping time, namely the 𝑟-th occurrence of the 𝑙-look-back run of length 𝑘 where 𝑘 1 ≤ 𝑘. The study of distributions of runs until a stopping time brings out many salient features of runs statistics and establishes new connection between various discrete distributions. Next section outlines the definitions and the main result. Section 3 formalizes the underlying set up for deriving the results. Section 4 is devoted to establishing the main theorem. The main tool that we use is the method of p.g.f.s, where we translate the problem in terms of a first order homogeneous Markov chain taking values in a finite set and use the strong Markov property for deriving the basic recurrence relation involving the probabilities of the number of 𝑙 1 -look-back runs of length 𝑘 1 .

Definitions and Statement of Results

Let 𝑋 -𝑚+1 , 𝑋 -𝑚+2 , … , 𝑋 0 , 𝑋 1 , … be a sequence of stationary 𝑚-order {0,1} valued Markov chain. It is assumed that the states of 𝑋 -𝑚+1 , 𝑋 -𝑚+2 , … , 𝑋 0 are known, i.e., we are given the initial condition {𝑋 0 = 𝑥 0 , 𝑋 -1 = 𝑥 1 , … , 𝑋 -𝑚+1 = 𝑥 𝑚-1 }. To make things formal, for any 𝑖 ≥ 0, define 𝑁 𝑖 = {0,1, … , 2 𝑖 -1}. It is clear that 𝑁 𝑖 and {0,1} 𝑖 can be identified easily by the mapping 𝑥 = (𝑥 0 , 𝑥 1 , … , 𝑥 𝑖-1 ) ⟶ ∑ 𝑗=0 𝑖-1 2 𝑗 𝑥 𝑗 . Since, {𝑋 𝑛 : 𝑛 ≥ -𝑚 + 1} is 𝑚 th order Markov chain, we have, for any 𝑛 ≥ 0,

where 𝑥 = ∑ 𝑗=0 𝑚-1 2 𝑗 𝑥 𝑗 ∈ 𝑁 𝑚 . Consequently, we have 𝑞 𝑥 = ℙ(𝑋 𝑛+1 = 0 | 𝑋 𝑛 = 𝑥 0 , 𝑋 𝑛-1 = 𝑥 1 , … , 𝑋 𝑛-𝑚+1 = 𝑥 𝑚-1 ) = 1 -𝑝 𝑥 . We assume that 0 < 𝑝 𝑥 < 1 for all 𝑥 ∈ 𝑁 𝑚 . Fix two integers 𝑘 ≥ 1 and 𝑙 ≤ 𝑘 -1. We set 𝑅 𝑖 (𝑘, 𝑙) = 0 for 𝑖 = 0, -1, … , -𝑙 + 1 and for any 𝑖 ≥ 1, define inductively,

If 𝑅 𝑖 (𝑘, 𝑙) = 1, we say that a l-look-back run of length 𝑘 has been recorded which started at time 𝑖. Define a sequence of stopping times {𝜏 𝑟 (𝑘, 𝑙): 𝑟 ≥ 1} as follows

It should be noted that this is indeed the stopping time for the completion of 𝑡ℎ𝑒 r-th l-look-back run of length 𝑘.

Fix any constant 𝑘 1 ≤ 𝑘. The counting of the runs of length 𝑘 1 can also be performed using the look-back counting scheme. For 𝑙 1 < 𝑘 1 , we define 𝑁 𝑟 (𝑘 1 , 𝑙 1 ) as the number of 𝑙 1 -look-back runs of length 𝑘 1 up to the stopping time 𝜏 𝑟 (𝑘, 𝑙). In other words,

For some special cases, we will obtain the exact distribution of 𝑁 𝑟 (𝑘 1 , 𝑙 1 ). We denote the probability generating function of 𝑁 𝑟 (𝑘 1 , 𝑙 1 ) by 𝜁 𝑟 (𝑠; 𝑘 1 , 𝑙 1 ). Before we proceed, we present an example to facilitate understanding. Consider the following sequence of 's and 1 's of length 20

11010111011111011101.

For 𝑘 = 4 and 𝑙 = 2, it should be noted that stopping times will be given by 𝜏 1 (4,2) = 9, 𝜏 2 (4,2) = 15, 𝜏 3 (4,2) = 18, 𝜏 4 (4,2) = 24, 𝜏 5 (4,2) = 27 and 𝜏 6 (4,2) = 33. Now let us consider 𝑘 1 = 2 and 𝑙 1 = 1, then the number of 𝑙 1 -look-back runs of length 𝑘 1 till the stopping times are given by 𝑁 1 (2,1) = 3, 𝑁 2 (2,1) = 5, 𝑁 3 (2,1) = 6, 𝑁 4 (2,1) = 9, 𝑁 5 (2,1) = 10 and 𝑁 6 (2,1) = 12.

Now we introduce two discrete distributions which will be useful for identifying the results. Anuradha [2022c] introduced the generalized Binomial type distribution. The probability generating function 𝜒 (𝑝,𝑛,𝑡) of the generalized Binomial type distribution is given by 𝜒 (𝑝,𝑛,𝑡) (𝑠) = (𝑞 + 𝑞𝑝𝑠 + ⋯ + 𝑞𝑝 𝑡-1 𝑠 𝑡-1 + 𝑝 𝑡 𝑠 𝑡 ) 𝑛 .

When we take 𝑛 = 1, the random variable is called the generalized Bernoulli type and is denoted by 𝐺Ber (𝑝, 𝑡). Thus, the pgf of 𝐺Ber (𝑝, 𝑡) is given by

Another discrete distribution will be important for our results. Aki (1985) had defined an extended negative binomial distribution of order 𝑡 with parameters 𝑛 and (𝑝 1 , 𝑝 2 , … , 𝑝 𝑡 ) and gave the probability generating function as

We will consider the case when 𝑝 1 = 𝑝 2 = ⋯ = 𝑝 𝑡 = 𝑝. Indeed, when 𝑡 = 1, this is the usual negative binomial distribution with parameters 0 < 𝑝 < 1 and 𝑛 ≥ 1. When 𝑛 = 1 and 𝑝 1 = 𝑝 2 = ⋯ = 𝑝 𝑡 = 𝑝, we will call this distribution as extended geometric distribution of order 𝑡 with parameter 𝑝. Now we state our main results which we have proved in the subsequent sections. We consider the 𝑙 1 -look-back runs of length 𝑘 1 .

Theorem 1 For any initial condition 𝑥 ∈ 𝑁 𝑚 , if both 𝑘 2 and (𝑙 + 1) are multiples of (𝑙 1 + 1), the probability generating function of 𝑁 𝑟 (𝑘 1 , 𝑙 1 ) is given by,

, 𝑘 3 = 𝑘 2 /(𝑙 1 + 1) and 𝑙 2 = (𝑙 + 1)/(𝑙 1 + 1). The result of Theorem 1 provides a powerful representation of 𝑁 𝑟 (𝑘 1 , 𝑙 1 ) through the extended geometric random variables and generalized Bernoulli type distribution. Let us define the indicator function as follows:

Corollary 1 Suppose that {𝐺 𝑖 (𝐸) : 𝑖 = 1, … , 𝑟} and {𝐵 𝑖 (𝐺) : 𝑖 = 1, … , 𝑟} are independent families of i.i.d. random variables where each 𝐺 𝑖 (𝐸) is having an extended geometric distribution of order 𝑘 3 with parameter 𝑝 2 𝑚 -1 ′ and each 𝐵 𝑖 (𝐺) is a generalized Bernoulli type random variable GBer (𝑝 2 𝑚 -1 ′ , 𝑙 2 ). Then, under the conditions of Theorem 1, we have

Indeed, we have that the generating function of any 𝐺 𝑖 (𝐸) given above. Also, the generating function of

Thus, using the independence of the random variables, we now conclude that the generating functions of the random variables of both sides of the Corollary 1 are same. This proves the corollary.

Unfortunately, when the above conditions do not hold, the distributions become more complicated and hence difficult to identify. However, we will show, through an example, how we may proceed and obtain the generating functions in this case. We discuss these results in the section 4.

Set-up

Now we outline the underlying set up which will be used in the subsequent section to establish the results. Let us define two functions 𝑓 0 , 𝑓 1 : 𝑆 𝑘 1 → 𝑆 𝑘 1 by 𝑓 1 (𝑥) = 2𝑥 + 1 (mod2 𝑘 1 ) and 𝑓 0 (𝑥) = 2𝑥 (mod2 𝑘 1 ).

Further define a projection 𝜃 𝑚 : 𝑆 𝑘 1 → 𝑆 𝑚 by 𝜃 𝑚 (𝑥) = 𝑥(mod2 𝑚 ). Now, set 𝑋 -𝑚 = 𝑋 -𝑚-1 = ⋯ = 𝑋 -𝑘 1 +1 = 0. Define a sequence of random variables {𝑌 𝑛 : 𝑛 ≥ 0} as follows:

Since 𝑋 𝑖 ∈ {𝟎, 𝟏} for all 𝑖, 𝑌 𝑛 assumes values in the set 𝑆 𝑘 1 . The random variables 𝑋 𝑛 's are stationary and forms an 𝑚 th order Markov chain, hence we have that {𝑌 𝑛 : 𝑛 ≥ 0} is a homogeneous Markov chain with transition matrix given by

Note that 𝑌 𝑛 is even if and only if 𝑋 𝑛 = 0. This motivates us to define the function 𝜅: 𝑆 𝑘 1 → {0,1} by

Therefore, 𝜅(𝑌 𝑛 ) = 1 if and only if 𝑋 𝑛 = 1. Hence, the definition of 𝑙-look-back run can be described in terms of 𝑌 𝑛 's as

Let us fix any initial condition 𝑥 ∈ 𝑆 𝑚 . We denote the probability measure governing the distribution of {𝑌 𝑛 : 𝑛 ≥ 1} with 𝑌 0 = 𝑥 ∈ 𝑆 𝑘 by ℙ 𝑥 . Since we have set 𝑋 -𝑚 = 𝑋 -𝑚-1 = ⋯ = 𝑋 -𝑘+1 = 0, we have 𝑌 0 = 𝑥. In order to obtain the recurrence relation for the probabilities, we will condition the process after the first occurrence of the run of length 𝑘 1 . Therefore, we consider the stopping time 𝑇 when the first occurrence of a run of length 𝑘 1 ends, i.e., when we observe 𝑘 1 successes consecutively for the first time. More precisely, define

We would like to translate the above definition to 𝑌 𝑖 's. It must be the case that when 𝑇 occurs, last 𝑘 1 trials have resulted in success, which may be described by 𝜅(𝑌 𝑗 ) = 1 for 𝑗 = 𝑖 -𝑘 1 + 1 to 𝑖. Therefore, 𝑌 𝑇 must equal 2 𝑘 1 -1. Since this is the first occurrence, this has not happened earlier. So, 𝑇 can be better described as 𝑇 = inf{𝑖 ≥ 𝑘 1 : 𝑌 𝑖 = 2 𝑘 1 -1}, i.e., the first visit of the chain to the state 2 𝑘 1 -1 after time 𝑘 1 -1. Now, we note that {𝑌 𝑛 : 𝑛 ≥ 0} is a Markov chain with finite state space. Further, since 0 < 𝑝 𝑢 < 1 for 𝑢 ∈ 𝑆 𝑚 , this is an irreducible chain; hence, it is positive recurrent. So we must have ℙ 𝑥 (𝑇 < ∞) = 1. We observe that when the first occurrence of 𝑘 consecutive successes happen, we must have the occurrence of 𝑘 1 successes previously since 𝑘 1 ≤ 𝑘. Therefore, we have ℙ 𝑥 (𝑇 ≤ 𝜏 1 (𝑘, 𝑙)) = 1.

Look-back runs of length 𝒌 𝟏

In this section, we study the distribution of the number of 𝑙 1 -look-back runs of length 𝑘 1 up to stopping time 𝜏 𝑟 (𝑘, 𝑙). We will employ the method of generating functions to derive these results. We obtain a recurrence relation between the probabilities in order to derive the generating functions.

Let us define the probability, for 𝑥 ∈ 𝑆 𝑚 , 𝑛 ∈ ℤ, 𝑔 𝑟 (𝑥) (𝑛; 𝑘 1 , 𝑙 1 ) = ℙ 𝑥 (𝑁 𝑟 (𝑘 1 , 𝑙 1 ) = 𝑛).

Also, let us define 𝜁 𝑟 (𝑠; 𝑘 1 , 𝑙 1 ) as the probability generating function of 𝑁 𝑟 (𝑘 1 , 𝑙 1 ), i.e., 𝜁 𝑟 (𝑠; 𝑘 1 , 𝑙 1 ) = ∑ ∞ 𝑛=0 𝑔 𝑟 (𝑥) (𝑛; 𝑘 1 , 𝑙 1 )𝑠 𝑛 .

4.1 When (𝒍 + 𝟏) and 𝒌 𝟐 are both multiples of (𝒍 𝟏 + 𝟏)

We will show that these probabilities 𝑔 𝑟 (𝑥) (𝑛; 𝑘 1 , 𝑙 1 ) is actually independent of the initial condition 𝑥. First we consider the case when 𝑟 = 1 and obtain the basic recurrence relation. If 𝑟 = 1 and 𝑘 2 = 𝑘 -𝑘 1 = 0, i.e, 𝑘 = 𝑘 1 , we have that 𝑁 1 = 1 and hence

where 𝕀 {𝑢} (𝑣) is the indicator function defined above. Clearly, we have 𝑔 1 (𝑥) (𝑛; 𝑘 1 , 𝑙 1 ) is independent of 𝑥.

Now, we concentrate on the case when 𝑘 2 = 𝑘 -𝑘 1 > 0 with 𝑘 2 = 𝑘 3 (𝑙 1 + 1). We note that 𝑁 1 ≥ (𝑘 3 + 1) and hence ℙ 𝑥 (𝑁 1 = 𝑛) = 𝑔 1 (𝑥) (𝑛; 𝑘 1 , 𝑙 1 ) = 0 for 𝑛 ≤ 𝑘 3 .

Theorem 2 For any initial condition 𝑥 ∈ 𝑁 𝑚 , if both 𝑘 2 and (𝑙 + 1) are multiples of (𝑙 1 + 1), we have

where ⌊𝑢⌋ is the largest integer smaller than or equal to 𝑢 ∈ ℝ.

Proof: When 𝑘 2 = 𝑘 -𝑘 1 > 0 and 𝑟 = 1, using the fact that 𝑌 𝑇 = 2 𝑘 1 -1 with probability 1, we have

We look at the terms in the summation first. For any 0 ≤ 𝑡 ≤ 𝑘 2 -1, we have,

The second term in the above expression can be written as

Now, 𝑇 + 𝑗 -1 is also a stopping time for any 1 ≤ 𝑗 ≤ 𝑡. Using strong Markov property, we can write

A similar argument shows that

For the first term, we note that 𝑌 𝑇 = 𝑌 𝑇+1 = ⋯ = 𝑌 𝑇+𝑡 = 2 𝑘 1 -1 and 𝑌 𝑇+𝑡+1 = 2 𝑘 1 -2. This implies that 𝑋 𝑇-𝑘 1 = 0 and 𝑋 𝑇-𝑘 1 +𝑗 = 1 for 𝑗 = 0,1, … , 𝑘 1 + 𝑡 -1. Therefore, we have a sequence of 𝟏 ′ s of length 𝑘 1 + 𝑡 with 𝑡 ≥ 0 which contributes to 1 + ⌊𝑡/(𝑙 1 + 1)⌋ many 𝑙 1 -look-back runs of length 𝑘 1 . Since there are no runs of length 𝑘 1 before 𝑇, by the very definition of 𝑇, we have that the number of 𝑙 1 -look-back runs of length 𝑘 1 up to time 𝑇 + 𝑡 + 1 is 1 + ⌊𝑡/(𝑙 1 + 1)⌋. Thus, the process after time 𝑇 + 𝑡 + 1 will have to contribute rest 𝑛 -1 -⌊𝑡/(𝑙 1 + 1)⌋ many 𝑙 1 -look-back runs of length 𝑘 1 . Using the strong Markov property, the process after 𝑇 + 𝑡 + 1, is a homogeneous Markov chain with same transition matrix with initial condition 2 𝑘 1 -2. Thus, we have

(2 𝑚 -2) (𝑛 -1 -⌊𝑡/(𝑙 1 + 1)⌋; 𝑘 1 , 𝑙 1 ). .

Combining the terms, we now get the required result. Hence the Theorem is proved. Further note that the right-hand side of the expression in the theorem does not involve the initial condition 𝑥 ∈ 𝑆 𝑚 . Therefore 𝑔 1 (𝑥) (𝑛; 𝑘 1 , 𝑙 1 ) must be independent of 𝑥. So, we will drop 𝑥 and denote the above probability by 𝑔 1 (𝑛; 𝑘 1 , 𝑙 1 ). Thus, on simplifying the right hand side of this equation, we have the following corollary from Theorem 2

Corollary 2 For 𝑛 ≥ 𝑘 3 + 1 and 𝑘 2 > 0, we have

, 𝑘 3 = 𝑘 2 /(𝑙 1 + 1). For the case 𝑟 > 1, we get the similar result by following the similar arguments as of Theorem 2 and Corollary 2. Hence we get the following theorem: Theorem 3 For any initial condition 𝑥 ∈ 𝑁 𝑚 , if both 𝑘 2 and (𝑙 + 1) are multiples of (𝑙 1 + 1), we have

) 𝑗 1 𝑙 2 +𝑗 2 +𝑘 3 𝑔 𝑟-1-𝑗 1 (𝑛 -1 -(𝑘 3 + 𝑗 2 + 𝑗 1 𝑙 2 )); 𝑘 1 , 𝑙 1 ) +(𝑝 2 𝑚 -1 ′ ) 𝑘 3 +(𝑟-1)𝑙 2 𝕀 {𝑛} (1 + 𝑘 3 + (𝑟 -1)𝑙 2 ).

Proof of Theorem 1:

We observe that the same set of recurrence relations were obtained in Anuradha [2022b]. Therefore, rest of the argument can easily be carried out to yield the following expression for the probability generating function:

𝟒. 𝟐 (𝒌 𝟐 = 𝟎 ) and (l + 1) is not a multiple of (𝒍 𝟏 + 𝟏)

In this subsection, we briefly describe how our method can be modified to handle the cases when (𝑙 + 1 )is not a multiple of (𝑙 1 + 1). Although, we concentrate only on the case 𝑙 1 = 1 and 𝑙 = 2, the method for treating the general case is similar but complicated. We define the generating functions Ξ odd (𝑧; 𝑘, 1) = ∑ 𝑟=0 ∞ 𝜁 2𝑟+1 (𝑠; 𝑘 1 , 𝑙 1 )𝑧 2𝑟+1 and Ξ even (𝑧; 𝑘, 1) = ∑ 𝑟=1 ∞ 𝜁 2𝑟 (𝑠; 𝑘 1 , 𝑙 1 )𝑧 2𝑟 . We derive two linear equations involving Ξ odd (𝑧; 𝑘, 1) and Ξ even (𝑧; 𝑘, 1) which can be solved to yield the formula for Ξ odd (𝑧; 𝑘, 1) and Ξ even (𝑧; 𝑘, 1).

For odd values of 𝑟, the recurrence relation can be written as

Hence, the generating function 𝜁 2𝑟+1 (𝑠; 𝑘, 1) of the sequence {𝑔 2𝑟+1 (𝑛; 𝑘, 1): 𝑛 ≥ 0} is given by 𝜁 2𝑟+1 (𝑠; 𝑘, 1) = ∑ 𝑟-1 𝑗=0 𝑞 2 𝑚 -1 (𝑝 2 𝑚 -1 ) 6𝑗 𝑠 𝑗 [(1 + 𝑝 2 𝑚 -1 + (𝑝 2 𝑚 -1 ) 2 𝑠)𝜁 2𝑟-2𝑗 (𝑠; 𝑘, 1) +(𝑝 2 𝑚 -1 ) 3 (1 + 𝑝 2 𝑚 -1 𝑠 + (𝑝 2 𝑚 -1 ) 2 𝑠)𝜁 2𝑟-2𝑗-1 (𝑠; 𝑘, 1)] + (𝑝 2 𝑚 -1 ) 6𝑟 𝑠 𝑟 .

The above equation can be simplified to yield

(1 -𝑧 2 (𝑝 2 𝑚 -1 ) 3 (𝑞 2 𝑚 -1 + 𝑝 2 𝑚 -1 𝑠))Ξ odd (𝑧; 𝑘, 1) = 𝑧 + 𝑞 2 𝑚 -1 (1 + 𝑝 2 𝑚 -1 + (𝑝 2 𝑚 -1 ) 2 𝑠)𝑧Ξ even (𝑧; 𝑘, 1).

Similar calculations may be carried out to obtain the other equation as

(1 -𝑧 2 (𝑝 2 𝑚 -1 ) 3 (𝑞 2 𝑚 -1 + 𝑝 2 𝑚 -1 𝑠))Ξ even (𝑧; 𝑘, 1) = (𝑝 2 𝑚 -1 ) 3 𝑧 2 + 𝑞 2 𝑚 -1 (1 + 𝑝 2 𝑚 -1 + (𝑝 2 𝑚 -1 ) 2 𝑠)𝑧Ξ odd (𝑧; 𝑘, 1).

On solving the above two linear equations we get the following expressions of Ξ odd (𝑧; 𝑘, 1) and Ξ even (𝑧; 𝑘, 1).

Ξ odd (𝑧; 𝑘, 1) = [ 𝑧-𝑧 3 (𝑝 2 𝑚 -1) 4 (𝑝 2 𝑚 -1 -𝑠(1 -𝑝 2 𝑚 -1 𝑞 2 𝑚 -1 ))][[1 -𝑧 2 (𝑞 2 𝑚 -1 (𝑝 2 𝑚 -1 ) 3 +(𝑝 2 𝑚 -1 ) 4 𝑠)] 2 -𝑧 2 (𝑞 2 𝑚 -1 + 𝑞 2 𝑚 -1 𝑝 2 𝑚 -1 + 𝑞 2 𝑚 -1 (𝑝 2 𝑚 -1 ) 2 𝑠) 2 ] -1 .

And Ξ even (𝑧; 𝑘, 1) = [𝑧 2 (𝑞 2 𝑚 -1 + 𝑞 2 𝑚 -1 𝑝 2 𝑚 -1 + 𝑞 2 𝑚 -1 (𝑝 2 𝑚 -1 ) 2 𝑠 + (𝑝 2 𝑚 -1 ) 3 ) -𝑧 4 (𝑝 2 𝑚 -1 ) 6 (𝑞 2 𝑚 -1 + 𝑝 2 𝑚 -1 𝑠)][[1 -𝑧 2 (𝑞 2 𝑚 -1 (𝑝 2 𝑚 -1 ) 3 + (𝑝 2 𝑚 -1 ) 4 𝑠)] 2 -𝑧 2 (𝑞 2 𝑚 -1 + 𝑞 2 𝑚 -1 𝑝 2 𝑚 -1 + 𝑞 2 𝑚 -1 (𝑝 2 𝑚 -1 ) 2 𝑠) 2 ] -1 .

The expressions for 𝜁 𝑟 (𝑠; 𝑘, 1) can be obtained from the above expressions. But their form becomes complicated and the underlying distributions are difficult to identify. Finally, this method can be employed for the general case, where we can obtain a system of linear equations which can be solved to obtain the expressions for 𝜁 𝑟 (𝑠; 𝑘, 1).

1. Fu JC, Koutras MV. Distribution theory of runs: a Markov chain approach, Journal of the American Statistical Association. 1994;89(427):1050-1058.
2. Uchida M. On number of occurrences of success runs of specified length in a higher order two-state Markov chain, Annals of the Institute of Statistical Mathematics. 1998;50(3):587-601.