Theoretical Foundations of Applied Discrete Mathematics

A criterion for checking the hypothesis about the existence of embeddings into a binary Markov chain

A. V. Volgin

Moscow State Technical University of Radioengineering, Electronics and Automation, Moscow

Abstract: A condition on the mutual asymptotic ratio of the length of a sequence and the volume of bit embeddings in it guaranteeing the existence of embeddings is given.

Keywords: Markov chains, embeddings into pseudorandom sequences, statistical criteria to distinguish hypotheses.

UDC: 519.651

DOI: 10.17223/2226308X/9/2