7
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ All right! That makes perfect sense. Thanks. Do you have any reasoning as to why the first sequence is random? $\endgroup$
    – Newb
    Commented Jun 11, 2014 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
    Commented Jun 11, 2014 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.
    Commented Jun 12, 2014 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.
    Commented Jun 12, 2014 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
    Commented Jun 17, 2014 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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