HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
randomtheseandonetwowhichnotsequences

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#27572, answer score: 3

Revisions (0)

No revisions yet.