=Paper=
{{Paper
|id=Vol-2639/paper-08
|storemode=property
|title=
Probabilistic functions and statistical equivalence of binary shift registers with random Markov input
|pdfUrl=https://ceur-ws.org/Vol-2639/paper-08.pdf
|volume=Vol-2639
|authors=Sergey Yu. Melnikov,Konstantin E. Samouylov
|dblpUrl=https://dblp.org/rec/conf/ittmm/MelnikovS20
}}
==
Probabilistic functions and statistical equivalence of binary shift registers with random Markov input
==
https://ceur-ws.org/Vol-2639/paper-08.pdf
Probabilistic functions and statistical equivalence
of binary shift registers with random Markov input
Sergey Yu. Melnikov, Konstantin E. Samouylov
Peoplesβ Friendship University of Russia (RUDN University), 6, Miklukho-Maklaya St., Moscow, 117198, Russia
Abstract
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.
Keywords
shift register, automata with random input, probability function
1. 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-Open melnikov@linfotech.ru (S. Yu. Melnikov); samuylov-ke@rudn.ru (K. E. Samouylov)
Orcid 0000-0002-6368-9680 (K. E. Samouylov)
Β© 2020 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
93
Sergey Yu. Melnikov et al. CEUR Workshop Proceedings 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.
2. 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 se-
quence 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]:
π
Ξ¦π (π) = β π π π π (1 β π)πβπ , (1)
π=0
where
π π = β π (π₯1 , π₯2 , β¦ , π₯π ), π = 0, 1, β¦ , π. (2)
(π₯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βπ π
( ), 0 < π, π < 1. (3)
π 1βπ
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 func-
tion 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.
3. 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:
94
Sergey Yu. Melnikov et al. CEUR Workshop Proceedings 93β99
π 00 = {(0, πΌ2 , πΌ3 , β¦ , πΌπβ1 , 0)} , π 01 = {(0, πΌ2 , πΌ3 , β¦ , πΌπβ1 , 1)} ,
(4)
π 10 = {(1, πΌ2 , πΌ3 , β¦ , πΌπβ1 , 0)} , π 11 = {(1, πΌ2 , πΌ3 , β¦ , πΌπβ1 , 1)} ,
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
π£πΌπ½ = π£πΌπ½ (πΌ1 , πΌ2 , πΌ3 , β¦ , πΌπ ) = β πΏ ((πΌπ½), (πΌπ πΌπ+1 )) , (5)
π=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:
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, β¦ ,
(0, 0);
β§
πΌ1 = {(π, π)} = π = 1, β¦ , π; π = 1, β¦ , π; (6)
β¨
β©π = π + 1, β¦ , 2π; π = 1, β¦ , 2π β π + 1;
for π = 2π + 1, π = 0, 1, 2, β¦ ,
(0, 0);
β§
πΌ1 = {(π, π)} = π = 1, β¦ , π; π = 1, β¦ , π; (7)
β¨
β©π = π + 1, β¦ , 2π; π = 1, β¦ , 2π β π + 1.
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, β¦
π = 1, β¦ , π + 1; π = 1, β¦ , π;
πΌ2 = {(π, π)} = { (8)
π = π + 2, β¦ , 2π + 1; π = 1, β¦ , 2π β π + 2;
for π = 2π + 1, π = 0, 1, 2, β¦
π = 1, β¦ , π; π = 1, β¦ , π;
πΌ2 = {(π, π)} = { (9)
π = π + 1, β¦ , 2π; π = 1, β¦ , 2π β π + 1.
Let πππ10 be the set of vectors from π 10 with markings (π£00 , π£01 , π£10 , π£11 ) =
(π β π β π β 1, π β 1, π, π β π) . The set of possible pairs of indices (π, π) is the same as πΌ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 π β π.
95
Sergey Yu. Melnikov et al. CEUR Workshop Proceedings 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.
πΌπ½ πΎπΏ
1. πππ β© πππ β β
if and only if πΌ = πΎ, π½ = πΏ, π = π, π = π.
πΌπ½
2. π πΌπ½ = β(ππ) πππ , πΌ, π½ = 0, 1, depending on the value (πΌ, π½) the union is taken from among
the sets πΌ1 , πΌ2 , πΌ3 .
πβπβ1 πβ1
3. |πππ00 | = ( )( ) , (π, π) β πΌ1 ;
π πβ1
πβπβ1 πβ1
|πππ01 | = |πππ10 | = ( )( ) , (π, π) β πΌ2 ;
πβ1 πβ1
πβπβ1 πβ1
|πππ11 | = ( )( ) , (π, π) β πΌ3 .
πβ1 π
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 , β¦ , π₯π ). (10)
(π₯1 ,π₯2 ,β¦,π₯π )βπ·
Theorem 1. Let π₯ (π) , π = 1, 2, β¦ be a stationary Markov chain with the states {0, 1} and the
transition probability matrix
1βπ π
( ). (11)
π 1βπ
The probabilistic function ππ (π, π ) of the automaton π΄π with a Markov dependence at the
input has the form
1
ππ (π, π ) = {β(1 β π)πβπβπβ1 ππ π π+1 (1 β π )πβπ βπ/π 00 β +
π+π πΌ ππ
1
+ β(1 β π)πβπβπ ππ π π (1 β π )πβπ (βπ/π 01 β + βπ/π 10 β) +
ππ ππ
πΌ2
+ β(1 β π)πβπβπ ππ+1 π π (1 β π )πβπβ1 βπ/π 11 β} . (12)
ππ
πΌ3
96
Sergey Yu. Melnikov et al. CEUR Workshop Proceedings 93β99
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)
π+π π+π
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 π(π ) = (π(1) (π ), π(2) (π ), π(3) (π )), where π(π) (π ) = (πππ , (π, π) β πΌπ ), π = 1, 2, 3,
(1) (2) (3)
πππ = βπ/π 00 β, (π, π) β πΌ1 , πππ = βπ/π 01 βͺ π 10 β, (π, π) β πΌ2 , πππ = βπ/π 11 β, (π, π) β πΌ3 , and the order
ππ ππ ππ ππ
of enumeration of the sets πΌ1 , πΌ2 , πΌ3 is fixed, for example, lexicographical, letβs call the Markov
weight structure of the Boolean function π.
Ξ
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 β π )πβπ , (π, π) β πΌ
β§π
ππ (π, π ) = π + π (1 β π) 1
βͺ
βͺ (2) 1
π
ππ (π, π ) = (1 β π)πβπβπ ππ π π (1 β π )πβπ , (π, π) β πΌ2 . (14)
β¨ π + π
βͺ (3)
βͺπ
(π, π ) = 1 (1 β π)πβπβπ ππ+1 π π (1 β π )πβπβ1 , (π, π) β πΌ
3
β© ππ π+π
(π)
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 = - equivalence class [π] Ξ with the vector π(π )
=
of the Markov weight structure.
Since the coordinates of the vector π(π ) are non-negative integers, it is not difficult 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
97
Sergey Yu. Melnikov et al. CEUR Workshop Proceedings 93β99
πβπβ1 πβ1 πβπβ1 πβ1 πβπβ1 πβ1
β( )( )β β2 ( )( )β β( )( )β
|[π] Ξ | = β β π π β 1 β β β π β 1 π β 1 β β β πβ1 π β.
= β β β β β β
(π,π)βπΌ1
β βπ/π 00 β β
(π,π)βπΌ2
β βπ/π 01 βͺ π 10 β β
(π,π)βπΌ3
β βπ/π 11 β β
ππ ππ ππ ππ
(16)
Ξ
The number of = - equivalence classes is
Ξ | = β ((π β π β 1) (π β 1) + 1) β (2 (π β π β 1) (π β 1) + 1)
|πΉπ /=
π πβ1 πβ1 πβ1
(π,π)βπΌ1 (π,π)βπΌ2
πβπβ1 πβ1
β (( )( ) + 1) (17)
πβ1 π
(π,π)βπΌ3
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.
Table 1
The numbers of equivalence classes
n 2 3 4 5
|πΉπ | 16 256 65536 4294967296
|πΉπ /=Ξ| 12 144 11664 8622400
πΉ
| π /β| 12 64 700 17424
Ξ
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 π + π(π3 )) .
|πΉπ /= (18)
4
5. 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.
98
Sergey Yu. Melnikov et al. CEUR Workshop Proceedings 93β99
Acknowledgments
The publication has been prepared with the support of the βRUDN University Program 5-
100β. The reported study was funded by RFBR, project numbers 18-00-01555 (18-00-01685),
19-07-00933.
References
[1] S. Frenkel, Probabilistic model of control-flow altering based malicious attacks, in: O. Strich-
man, R. Tzoref-Brill (Eds.), Hardware and Software: Verification and Testing, Springer
International Publishing, Cham, 2017, pp. 249β252.
[2] A. S. Davis, Markov chains as random input automata, The American Mathematical
Monthly 68 (1961) 264β267.
[3] V. M. Zakharov, B. F. Eminov, S. V. Shalagin, Representation of markovβs chains func-
tions over finite field based on stochastic matrix lumpability, in: 2016 2nd International
Conference on Industrial Engineering, Applications and Manufacturing (ICIEAM), 2016.
doi:1 0 . 1 1 0 9 / I C I E A M . 2 0 1 6 . 7 9 1 1 6 6 2 .
[4] V. V. Gusev, Synchronizing automata with random inputs, in: A. M. Shur, M. V. Volkov
(Eds.), Developments in Language Theory, volume 8633, Springer International Publishing,
Cham, 2014, pp. 68β75. doi:1 0 . 1 0 0 7 / 9 7 8 - 3 - 3 1 9 - 0 9 6 9 8 - 8 _ 7 .
[5] S. Y. Melnikov, K. E. Samouylov, The recognition of the output function of a finite automaton
with random input, in: V. M. Vishnevskiy, D. V. Kozyrev (Eds.), Distributed Computer and
Communication Networks, volume 919, Springer International Publishing, Cham, 2018, pp.
525β531. doi:1 0 . 1 0 0 7 / 9 7 8 - 3 - 3 1 9 - 9 9 4 4 7 - 5 _ 4 5 .
[6] B. A. Sevastyanov, The conditional distribution of the output of an automaton without
memory for given characteristics of the input, Discrete Mathematics and Applications 4
(1994) 1β6. doi:1 0 . 1 5 1 5 / d m a . 1 9 9 4 . 4 . 1 . 1 .
[7] V. N. Sachkov, Combinatorial Methods in Discrete Mathematics, Encyclopedia of Mathe-
matics and its Applications, Cambridge University Press, 1996.
[8] J. G. Kemeny, J. Snell, Finite Markov Chains, Springer-Verlag, 1976.
99