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.

  • 1
    $\begingroup$ If $k=2n+1$ then $P(B_k = 1) < P(B_k = 0)$. Isn't that sufficient, informally? $\endgroup$ – OJFord Jun 10 '14 at 18:34
  • $\begingroup$ maybe a related question $\endgroup$ – Nikos M. Jun 10 '14 at 19:05
  • $\begingroup$ 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)? $\endgroup$ – Nikos M. Jun 10 '14 at 19:08
  • $\begingroup$ 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). $\endgroup$ – Nikos M. Jun 10 '14 at 19:11
  • 1
    $\begingroup$ @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. $\endgroup$ – 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.

  • $\begingroup$ All right! That makes perfect sense. Thanks. Do you have any reasoning as to why the first sequence is random? $\endgroup$ – Newb Jun 11 '14 at 0:54
  • 1
    $\begingroup$ 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$. $\endgroup$ – gardenhead Jun 11 '14 at 1:18
  • $\begingroup$ 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)? $\endgroup$ – Nikos M. Jun 12 '14 at 8:15
  • $\begingroup$ In fact i am posting a question (soon?) addresing the relaton between probabilistic and algorithmic randomness (per the other question i linked in the comments) $\endgroup$ – Nikos M. Jun 12 '14 at 8:21
  • $\begingroup$ I think you're right, while both are random in a sense, algorithmically random is not the same as probabilistically random. As I am not an expert on algorithmic randomness, that's really I can say. I would be interested for an elaboration of these points as well. $\endgroup$ – gardenhead Jun 17 '14 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.