# Which one of these two sequences is random, and which one is not?

We let $\alpha = \alpha_1\alpha_2\alpha_3\ldots$ be an infinite random sequence (under the uniform measure) where $\alpha_i$ may be $1$ or $0$, and then define the boolean function $B_k$:

$$B_k(\alpha_1\ldots\alpha_k) = \begin{cases} 1 \text{ if at least } \lceil k/2 \rceil \text{ of its inputs are } 1 \\ 0 \text{ otherwise} \end{cases}$$

Then we define two sequences:

$$B_3(\alpha_1\alpha_2\alpha_3)B_3(\alpha_4\alpha_5\alpha_6)B_3(\alpha_7\alpha_8\alpha_9)\ldots$$ $$B_4(\alpha_1\alpha_2\alpha_3\alpha_4)B_4(\alpha_5\alpha_6\alpha_7\alpha_8)B_4(\alpha_9\alpha_{10}\alpha_{11}\alpha_{12})\ldots$$

Which one of these two sequences is (algorithmically) random, and why? I should note that apparently there is an obvious measure-theoretic fact that gives away which one is not random.

• If $k=2n+1$ then $P(B_k = 1) < P(B_k = 0)$. Isn't that sufficient, informally? – OJFord Jun 10 '14 at 18:34
• maybe a related question – Nikos M. Jun 10 '14 at 19:05
• Isnt each $B_k$ sequence the same as the partial sum sequence of $a_i$'s (or more correctly the difference of 2 partial sum sequences)? – Nikos M. Jun 10 '14 at 19:08
• i can also give another type of answer in sigal procesing terms. Each $B_k$ sequence acts as lowpass filter (filtering away high frequencies) as a result because random noise has especially high frequencies, each $B_k$ should be progresively less random (eventually equal a sequence of 1's). – Nikos M. Jun 10 '14 at 19:11
• @Newb According to the Wikipedia article you link, there are multiple possibilities and the default is a convention of the field. You should be careful using such conventions here without clarification -- not every reader is a domain expert. – Raphael Jun 11 '14 at 9:04

The second sequence is not random. Let $\alpha_1,\alpha_2,\alpha_3,\alpha_4$ be random, iid Bernoulli $1/2$ random variables. Let $\beta = B_4(\alpha_1 \alpha_2 \alpha_3 \alpha_4)$.
What is the distribution of the random variable $\beta$? Answer: $\beta=1$ if at least two of the $\alpha$'s are $1$, so $\Pr[\beta=1] = 11/16$.
In other words, $\beta$ is biased towards $1$. It follows that the second sequence is not algorithmically random: it is a set of independent Bernoulli random variables with $p=11/16$, i.e., the outcome of an infinite sequence of tosses of a biased coin.
• By contrast, it would be because $B_3$ is "fair": there are 4 3-bit sequences that $B_3$ maps to 1 and 4 3-bit sequences that it maps to 0, so assuming the original sequence is random, $Pr[B=1] = Pr[B=0] = \frac12$. – gardenhead Jun 11 '14 at 1:18
• i dont agree with this, it just states that the random variable $\beta$ does not have equal p1 and p2 probabilties. Why a random variable with P1 = 1/3 and P0 = 2/3, not be considered random? Why r.v's with a different distribution are not random (a gaussian rv is not random, it is biased towards the mean)? – Nikos M. Jun 12 '14 at 8:15