Generating non-Markov random sources with high Shannon entropy

We study the properties of a sequence of dependent random variables generated with the following scheme. A sequence of independent identically distributed random variables α arrives at the input of a k-register; the random variables take values 0 and 1 with probabilities not equal to 1/2. The sequence η of random variables generated by the k-register for k⩾2 is a stationary random sequence with dependent components. The sequence η is taken as the input to a memoryless binary symmetrical channel with input-independent noise, i.e. η is added coordinatewise modulo 2 to a sequence β of independent identically distributed random variables that also take the values 0 and 1 with probabilities not equal to 1/2 and are independent with the sequence α. In this paper we derive upper and lower estimates for the entropy of the stationary non-Markov random source identified with the channel output. The upper estimate is based on the well-known subadditivity property of the entropy of a finite-dimensional distribution. The main result is the proof of nontrivial lower estimate of the entropy for two particular k-registers: k=2 and k=3. If the probabilities of 0 and 1 in the sequences α and β are close to 1/2, this estimate shows that the entropy of the source increases when k grows from 1 to 3. Pre-transformation of α by the k-register, k>1, yields the increase of the entropy of the additive source α+β over the case k=1. This property of increase of the entropy is significant for constructing a strong random source from several “weak” ones