Introduction

In a number of problems of recognition and identification of automata [1], the case is considered when the input of the automaton is a sequence of random variables. Recognition or identification of an automaton is carried out by analysis of statistics at the output of an automaton. It is known [2] that if the input of the automaton is a sequence of independent identically distributed random variables, then the distribution of symbols of the output sequence is described by a function on the Markov chain. Such a function can be specified by gluing states of the Markov chain [3]. In [4] the problem of synchronizing of finite automata, the input of which is a Bernoulli sequence, was studied. In [5] the problem of recognizing of the output function for three classes of automata was considered under the conditions when the input of the automaton is a sequence of independent identically distributed random variables. For the case when the automaton is a shift register and the input sequence is Bernoulli [6], an expression is obtained for the probability of a symbol in the output sequence. This probability polynomially depends on the parameter of the Bernoulli scheme, the degree of which does not exceed the size of the register. The coefficients of the polynomial are given by the sums of the values of the output function on some subsets of register states.

Here we study the case when the symbols of the input sequence of the binary shift register are connected into a simple homogeneous stationary Markov chain with two free parameters.

Workshop on information technology and scientific computing in the framework of the X International Conference Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems (ITTMM-2020), Moscow, Russian, April 13-17, 2020

Envelope melnikov@linfotech.ru (S. Yu. Melnikov); samuylov-ke@rudn.ru (K. E. Samouylov) Orcid 0000-0002-6368-9680 (K. E. Samouylov)

93-99

Our goal is to obtain an expression for the probability of a symbol in the output sequence and describe the equivalence relation on the set of output functions that provide the identity of the desired probabilities. We show that the desired probability is a fractional rational function of the parameters of the Markov chain, and the equivalence relation is given by the vectors of sums of the values of the output functions on some subsets of register states.

Definitions and statement of the problem

Let 𝑉 𝑛 be the space of 𝑛-dimensional binary vectors, 𝐹 𝑛 be the set of Boolean functions of 𝑛 arguments, 𝑛 = 1, 2, …. For 𝑓 (𝑥 1 , 𝑥 2 , … , 𝑥 𝑛 ) ∈ 𝐹 𝑛 by 𝐴 𝑓 = (𝑋 = {0, 1}, 𝑉 𝑛 , 𝑌 = {0, 1}, ℎ, 𝑓) we denote the Moore automaton with set of states 𝑉 𝑛 , the transition function ℎ, determined by the rule ℎ ((𝑎 1 , … , 𝑎 𝑛 ), 𝑥) = (𝑎 2 , … , 𝑎 𝑛 , 𝑥), where 𝑥, 𝑎 𝑖 ∈ {0, 1}, 𝑖 = 1, 2, … , 𝑛, and output function 𝑓 (𝑥 1 , 𝑥 2 , … , 𝑥 𝑛 ). The automaton 𝐴 𝑓 is a shift register with a size of 𝑛.

If the Bernoulli sequence of binary random variables 𝑥 (𝑖) , 𝑖 = 1, 2, … with distribution 𝑃 (𝑥 (𝑖) = 1) = 𝑝, 0 < 𝑝 < 1, used as the input of the automaton 𝐴 𝑓 , then the output sequence of random variables 𝑓 (𝑥 (𝑖) , 𝑥 (𝑖+1) , … , 𝑥 (𝑖+𝑛−1) ), 𝑖 = 𝑛 + 1, 𝑛 + 2, … is stationary and the probability 𝑃 {𝑓 (𝑥 (𝑖) , 𝑥 (𝑖+1) , … , 𝑥 (𝑖+𝑛−1) ) = 1} of the symbol "1" in the output sequence is given by the polynomial [6]:

Φ 𝑓 (𝑝) = 𝑛 ∑ 𝑗=0 𝑠 𝑗 𝑝 𝑗 (1 − 𝑝) 𝑛−𝑗 ,(1)

where

𝑠 𝑘 = ∑ (𝑥 1 ,𝑥 2 ,…,𝑥 𝑛 )∶∑ 𝑥 𝑖 =𝑘 𝑓 (𝑥 1 , 𝑥 2 , … , 𝑥 𝑛 ), 𝑘 = 0, 1, … , 𝑛.(2)

Suppose that the automaton 𝐴 𝑓 , 𝑓 ∈ 𝐹 𝑛 , 𝑛 = 1, 2, …, receives a sequence of binary random variables 𝑥 (𝑖) , 𝑖 = 1, 2, …, connected in a simple homogeneous stationary Markov chain with the transition probability matrix

( 1 − 𝜆 𝜆 𝜉 1 − 𝜉 ) , 0 < 𝜆, 𝜉 < 1.(3)

The sequence of random variables 𝑓 (𝑥 (𝑖) , 𝑥 (𝑖+1) , … , 𝑥 (𝑖+𝑛−1) ), 𝑖 = 𝑛 + 1, 𝑛 + 2, … is stationary and it makes sense to talk about the probability 𝑃 {𝑓 (𝑥 (𝑖) , 𝑥 (𝑖+1) , … , 𝑥 (𝑖+𝑛−1) ) = 1} of the symbol "1" in the output sequence.

The function 𝑃 𝑓 (𝜆, 𝜉 ) = 𝑃 {𝑓 (𝑥 (𝑖) , 𝑥 (𝑖+1) , … , 𝑥 (𝑖+𝑛−1) ) = 1} will be called the probabilistic function of the automaton 𝐴 𝑓 with a Markov dependence at the input. Our task is to obtain an expression for 𝑃 𝑓 (𝜆, 𝜉 ) and break 𝐹 𝑛 into classes with the same probabilistic functions.

Calculation of the probability function

We divide the set 𝑉 𝑛 of all 𝑛-dimensional binary vectors, 𝑛 ⩾ 2, into four classes, depending on the values of the first and last coordinates. Let us denote:

93-99 𝑉 00 = {(0, 𝛼 2 , 𝛼 3 , … , 𝛼 𝑛−1 , 0)} , 𝑉 01 = {(0, 𝛼 2 , 𝛼 3 , … , 𝛼 𝑛−1 , 1)} , 𝑉 10 = {(1, 𝛼 2 , 𝛼 3 , … , 𝛼 𝑛−1 , 0)} , 𝑉 11 = {(1, 𝛼 2 , 𝛼 3 , … , 𝛼 𝑛−1 , 1)} ,(4)

where 𝛼 𝑖 = 0, 1, 𝑖 = 2, … , 𝑛 − 1.

To each vector from 𝑉 𝑛 we associate its bigram marking (𝑣 00 , 𝑣 01 , 𝑣 10 , 𝑣 11 ), where 𝑣 𝛼𝛽 is the number of bigrams (𝛼, 𝛽) encountered in it. Let us put

𝑣 𝛼𝛽 = 𝑣 𝛼𝛽 (𝛼 1 , 𝛼 2 , 𝛼 3 , … , 𝛼 𝑛 ) = 𝑛−1 ∑ 𝑘=1 𝛿 ((𝛼𝛽), (𝛼 𝑘 𝛼 𝑘+1 )) , (5)

where 𝛿 is the Kronecker symbol, 𝛼, 𝛽 = 0, 1.

In each of the four classes, we single out the vectors characterized by the same markings (𝑣 00 , 𝑣 01 , 𝑣 10 , 𝑣 11 ). To do this, we introduce the following notation:

Let 𝑆 00 𝑖𝑗 be the set of vectors from 𝑉 00 with markings (𝑣 00 , 𝑣 01 , 𝑣 10 , 𝑣 11 ) = (𝑛 − 𝑗 − 𝑖 − 1, 𝑖, 𝑖, 𝑗 − 𝑖). We denote 𝐼 1 as the set of possible pairs of indices (𝑖, 𝑗). We will describe it.

For 𝑛 = 2𝑙 + 2, 𝑙 = 0, 1, 2, … ,

Let 𝑆 01 𝑖𝑗 be the set of vectors from 𝑉 01 with markings (𝑣 00 , 𝑣 01 , 𝑣 10 , 𝑣 11 ) = (𝑛 − 𝑗 − 𝑖 − 1, 𝑖, 𝑖 − 1, 𝑗 − 𝑖). We denote 𝐼 2 as the set of possible pairs of indices (𝑖, 𝑗). We will describe it.

For 𝑛 = 2𝑙 + 2, 𝑙 = 0, 1, 2, … Let 𝑆 11 𝑖𝑗 be the set of vectors from 𝑉 11 with markings (𝑣 00 , 𝑣 01 , 𝑣 10 , 𝑣 11 ) = (𝑛 − 𝑗 − 𝑖 − 1, 𝑖, 𝑖, 𝑗 − 𝑖 − 1) . The set of possible pairs of indices, which we denote by 𝐼 3 , is obtained from 𝐼 1 by replacing 𝑗 with 𝑛 − 𝑗.

93-99

Note that the index 𝑗 in the whole introduced notation is equal to the weight (sum of ones) of the vectors from the sets under consideration. The following lemma shows that the space of all 𝑛-dimensional binary vectors is represented as a union of the introduced sets, and these sets do not intersect.

Lemma. The following relations hold. Hereinafter, we assume that

( 𝑛 −1 ) = { 1, 𝑛 = −1, 0, 𝑛 ≠ −1.

Proof. The first two points of the lemma follow from the construction of sets 𝑆 𝛼𝛽 𝑖𝑗 . The proof of the third one is based on counting the number of binary vectors of fixed weight with a given number of series of zeros and ones [7].

For 𝐷 ⊂ 𝑉 𝑛 we denote

‖ 𝑓 /𝐷 ‖ = ∑ (𝑥 1 ,𝑥 2 ,…,𝑥 𝑛 )∈𝐷 𝑓 (𝑥 1 , 𝑥 2 , … , 𝑥 𝑛 ). (10)

Theorem 1. Let 𝑥 (𝑖) , 𝑖 = 1, 2, … be a stationary Markov chain with the states {0, 1} and the transition probability matrix

( 1 − 𝜆 𝜆 𝜉 1 − 𝜉 ) .(11)

The probabilistic function 𝑃 𝑓 (𝜆, 𝜉 ) of the automaton 𝐴 𝑓 with a Markov dependence at the input has the form

𝑃 𝑓 (𝜆, 𝜉 ) = 1 𝜆 + 𝜉 {∑ 𝐼 1 (1 − 𝜆) 𝑛−𝑗−𝑖−1 𝜆 𝑖 𝜉 𝑖+1 (1 − 𝜉 ) 𝑗−𝑖 ‖ 𝑓 /𝑆 00 𝑖𝑗 ‖ + + ∑ 𝐼 2 (1 − 𝜆) 𝑛−𝑗−𝑖 𝜆 𝑖 𝜉 𝑖 (1 − 𝜉 ) 𝑗−𝑖 (‖ 𝑓 /𝑆 01 𝑖𝑗 ‖ + ‖ 𝑓 /𝑆 10 𝑖𝑗 ‖) + + ∑ 𝐼 3 (1 − 𝜆) 𝑛−𝑗−𝑖 𝜆 𝑖+1 𝜉 𝑖 (1 − 𝜉 ) 𝑗−𝑖−1 ‖ 𝑓 /𝑆 11 𝑖𝑗 ‖} . (12)

To prove the Theorem 1, we use the lemma, the formulas for the total and conditional probability, and the well-known [8] form of the stationary distribution vector of the input sequence (𝑃 (𝑥 (𝑖) = 0) , 𝑃 (𝑥 (𝑖) = 1)) = ( 𝜉 𝜆 + 𝜉 , 𝜆 𝜆 + 𝜉 ) .

(13)

The relation of statistical equivalence with Markov dependence at the input and its properties

By analogy with how this was done in [5], we introduce the equivalence relation on the set 𝐹 𝑛 . We call the functions 𝑓 and 𝑔 from 𝐹 𝑛 statistically equivalent for a Markov input dependence, having adopted the notation 𝑓 Δ = 𝑔 for this case if the identity 𝑃 𝑓 (𝜆, 𝜉 ) = 𝑃 𝑔 (𝜆, 𝜉 ) for 0 < 𝜆, 𝜉 < 1 holds.

Obviously, the introduced relation is an equivalence relation breaking 𝐹 𝑛 into disjoint classes.

Vector 𝑚(𝑓 ) = (𝑚 (1) (𝑓 ), 𝑚 (2) (𝑓 ), 𝑚 (3) (𝑓 )), where 𝑚 (𝑖) (𝑓 ) = (𝑚 Proof. Let us consider the system of real functions defined on the square 0 < 𝜆, 𝜉 < 1:

(𝑘) 𝑖𝑗 , (𝑖, 𝑗) ∈ 𝐼 𝑘 ), 𝑘 = 1, 2, 3, 𝑚(1)𝑖𝑗 = ‖ 𝑓 /𝑆 00 𝑖𝑗 ‖, (𝑖, 𝑗) ∈ 𝐼 1 , 𝑚(2)𝑖𝑗 = ‖ 𝑓 /𝑆 01 𝑖𝑗 ∪ 𝑆 10 𝑖𝑗 ‖, (𝑖, 𝑗) ∈ 𝐼 2 , 𝑚(3)⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 𝑅(1)

𝑖𝑗 (𝜆, 𝜉 ) =

1 𝜆 + 𝜉 (1 − 𝜆) 𝑛−𝑗−𝑖−1 𝜆 𝑖 𝜉 𝑖+1 (1 − 𝜉 ) 𝑗−𝑖 , (𝑖, 𝑗) ∈ 𝐼 1 𝑅(2)

Denoting 𝑅(𝜆, 𝜉 ) = (𝑅 (1) , 𝑅 (2) , 𝑅 (3) ), where 𝑅 (𝑘) = (𝑅 (𝑘) 𝑖𝑗 (𝜆, 𝜉 ), (𝑖, 𝑗) ∈ 𝐼 𝑘 ), 𝑘 = 1, 2, 3, we rewrite the expression (12) for the probability function in the form 𝑃 𝑓 (𝜆, 𝜉 ) = 𝑅(𝜆, 𝜉 ) (𝑚(𝑓 ))

𝑇 .

(15)

To complete the proof, it remains to note that the system (14) is a linearly independent system of functions on the square 0 < 𝜆, 𝜉 < 1.

The proved theorem allows us to identify the

= | = ∏ (𝑖,𝑗)∈𝐼 1 ⎛ ⎜ ⎜ ⎝ ( 𝑛 − 𝑗 − 1 𝑖 ) ( 𝑗 − 1 𝑖 − 1 ) ‖ 𝑓 /𝑆 00 𝑖𝑗 ‖ ⎞ ⎟ ⎟ ⎠ ∏ (𝑖,𝑗)∈𝐼 2 ⎛ ⎜ ⎜ ⎝ 2 ( 𝑛 − 𝑗 − 1 𝑖 − 1 ) ( 𝑗 − 1 𝑖 − 1 ) ‖ 𝑓 /𝑆 01 𝑖𝑗 ∪ 𝑆 10 𝑖𝑗 ‖ ⎞ ⎟ ⎟ ⎠ ∏ (𝑖,𝑗)∈𝐼 3 ⎛ ⎜ ⎜ ⎝ ( 𝑛 − 𝑗 − 1 𝑖 − 1 ) ( 𝑗 − 1 𝑖 ) ‖ 𝑓 /𝑆 11 𝑖𝑗 ‖ ⎞ ⎟ ⎟ ⎠ .(16)

The number of

Δ = -equivalence classes is | 𝐹 𝑛 / Δ = | = ∏ (𝑖,𝑗)∈𝐼 1 (( 𝑛 − 𝑗 − 1 𝑖 ) ( 𝑗 − 1 𝑖 − 1 ) + 1) ∏ (𝑖,𝑗)∈𝐼 2 (2 ( 𝑛 − 𝑗 − 1 𝑖 − 1 ) ( 𝑗 − 1 𝑖 − 1 ) + 1) ∏ (𝑖,𝑗)∈𝐼 3 (( 𝑛 − 𝑗 − 1 𝑖 − 1 ) ( 𝑗 − 1 𝑖 ) + 1)(17)

For comparison the Table 1 presents the number of all Boolean functions, the number of Δ =-equivalence classes and the number of ≈-equivalence classes (equivalence at the Bernoulli input, see [5]) for 𝑛 = 2, 3, 4, 5. In view of the complexity of the expression for the number of

Conclusion

The expression is obtained for the probabilistic function that describes the probability of a symbol in the output sequence of a binary shift register with a random binary variables connected into a simple homogeneous stationary Markov chain as input. An equivalence relation is described on the set of output functions of binary shift registers that occurs when the corresponding probability functions are identically equal. The results obtained generalize those that were previously known for the case when the input sequence is a sequence of independent random variables.