patternMinor
Which one of these two sequences is random, and which one is not?
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.
$$
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.
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.