A version of Maurer's conjecture for stationary -mixing processes
Miguel Natalio Abadi, Antonio Galves · Nonlinearity · 2004
For a stationary source with finite alphabet, let be the number of non-overlapping n -blocks of symbols, occurring before the initial n -block reappears. When the source is ψ-mixing, we prove that the difference between the expectation of and the entropy of n -blocks converges to the constant of Euler divided by −ln(2). This can be considered the correct version of a conjecture presented in Maurer (1992 J. Cryptol . 5 89–105). Our theorem generalizes recent results presented in Coron and Naccache (1999 Lecture Notes in Computer Science vol 1556, pp 51–71), Choe and Kim (2000 Coll. Math . 84 159–71) and Wegenkittl (2001 IEEE Trans. Inform. Theory 47 2480–9), in the context of Markov chains. We also prove that the difference between the variance of and the variance of the probability of n -blocks converges to an explicit constant as n diverges. The basic ingredient of the proofs is an upper-bound for the exponential approximation of the distribution of the number of non-overlapping n -blocks until a fixed but otherwise arbitrary n -block reappears. This is a new result that is interesting by itself.