We consider a binary non-autonomous shift register with a sequence of random variables connected into a simple homogeneous stationary Markov chain at the input. The expression is obtained for the probability function in the output sequence in the form of a fractional rational function, the arguments of which are the transition probabilities of the Markov chain. An equivalence relation arising in the case of the identical equality of the probability functions of the registers is described. The results known earlier for the case when the input sequence is a sequence of independent random variables are generalized. shift register, automata with random input, probability function 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 coeficients of the polynomial are given by the sums of the values of the output function on some subsets of register states.
CEUR
CEUR Workshop Proceedings (CEUR-WS.org) 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.
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]: where =0 Φ () =
∑ (1 − ) − , =
∑ ( 1, 2,…, )∶∑ =
( 1, 2, … , ), = 0, 1, … , .
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 ( 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.
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: number of bigrams ( , )
encountered in it. Let us put To each vector from we associate its bigram marking ( 00, 01, 10, 11), where is the = ( 1, 2, 3, … , ) = ∑ (( ), ( +1 )), −1 =1 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: We denote 1 as the set of possible pairs of indices (, ) . We will describe it.
Let
00 be the set of vectors from 00 with markings ( 00, 01, 10, 11) = ( − − − 1, , , − For = 2 + 2 , = 0, 1, 2, … , for = 2 + 1 , = 0, 1, 2, … , ⎧ ⎨ ⎧ ⎨ (0, 0); (0, 0); 1 = {(, ) } = = 1, … , ; = 1, … , ;
⎩ = + 1, … , 2; = 1, … , 2 − + 1;
1 = {(, ) } = = 1, … , ; = 1, … , ;
⎩ = + 1, … , 2; = 1, … , 2 − + 1.
(
).
(
Let 01 be the set of vectors from 01 with markings ( 00, 01, 10, 11) = ( − − − 1, , − 1, − ).
For = 2 + 2 , = 0, 1, 2, … for = 2 + 1 , = 0, 1, 2, … 2 = {(, ) } = { = 1, … , + 1; = 1, … , ; = + 2, … , 2 + 1; = 1, … , 2 − + 2; 2 = {(, ) } = { = 1, … , ; = 1, … , ; = + 1, … , 2; = 1, … , 2 − + 1. ( − − − 1, , , − − 1 from 1 by replacing with − .
Let 10 be the set of vectors from 10 with markings ( 00, 01, 10, 11) = Let 11 be the set of vectors from 11 with markings ( − − − 1, − 1, , − ). The set of possible pairs of indices (, ) is the same as 2. ( 00, 01, 10, 11) = ). The set of possible pairs of indices, which we denote by 3, is obtained
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.
∩ ≠ ∅ if and only if = , = , = , = .
, , = 0, 1 , depending on the value (, ) the union is taken from among 1. 2. 3. | 00| = (
= ⋃() the sets 1, 2, 3. number of series of zeros and ones [7].
For ⊂
we denote transition probability matrix input has the form (, ) =
1 Theorem 1. Let () , = 1, 2, … be a stationary Markov chain with the states {0, 1} and the The probabilistic function (, ) of the automaton with a Markov dependence at the ‖ / ‖ =
∑ ( 1, 2,…, )∈
( 1, 2, … , ). ( {∑(1 − ) −−−1 +1 (1 − )− ‖ / 00‖ + + ∑(1 − ) −− (1 − )− (‖ / 01‖ + ‖ / 10‖) + (10) (11) 3
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)) = (
, 4. 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 ( ) =
( (
Theorem 2. Two Boolean functions are =Δ-equivalent if and only if their Markov weight structures coincide.
Proof. Let us consider the system of real functions defined on the square 0 < , < 1 :
(
⎨
⎪⎪ (
1
.
(1 − ) −− +1 (1 − )−−1 ,
(, ) ∈ 3
Denoting (, ) =
( (
To complete the proof, it remains to note that the system (14) is a linearly independent system of functions on the square 0 < , < 1 . of the Markov weight structure.
The proved theorem allows us to identify the = - equivalence class [ ]=Δ with the vector ( ) Since the coordinates of the vector ( ) are non-negative integers, it is not dificult to obtain the following description of the structure of the relation = - equivalence.
Theorem 3. The number of functions that are =Δ - equivalent to a function is determined by Δ the expression Δ 93–99 (13) (14) (15) |[ ]=Δ| = ∏ ⎜ (,)∈ 1 ⎝ ⎛( ⎜ The number of =Δ - equivalence classes is | /=Δ| = ∏ (( (,)∈ 1 =Δ-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 =Δ-equivalence classes, it is of interest to estimate its growth at large . Using the Stirling and Euler-Maclaurin formulas, we can obtain the following result.
Theorem 4. If → ∞ , the relation | /=Δ| = exp (5 3 ln + ( 4 3)) .
(18)
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.
The publication has been prepared with the support of the “RUDN University Program 5100”. The reported study was funded by RFBR, project numbers 18-00-01555 (18-00-01685), 19-07-00933.