1
$\begingroup$

I have a problem where given an infinite binary sequence S ∈ {0, 1}∞ to be "prefix-repetitive" if there are infinitely many strings w ∈ {0, 1}* such that ww is a prefix of S.

I need to prove that if the bits of a sequence S ∈ {0, 1}∞ are chosen by independent tosses of a fair coin, then Prob[S is prefix-repetitive] = 0

My first instinct to tackling this problem was that the probability was 0, because of Cantor's diagonal argument, because we can construct an sequence s0 that is not in the set S. This would mean that S is countably infinite and the set of "all" possible infinite binary sequences is uncountable.

Any help or suggestions to see if I'm on the right track to proving this problem would be great!

$\endgroup$
  • $\begingroup$ Could you add the definition of the probability distribution of the infinite binary sequences in your question? That definition might not be obvious to lots of readers. It will help you solve the problem as well if you can look at the definition again and again. $\endgroup$ – Apass.Jack Feb 4 at 22:29
  • 1
    $\begingroup$ Borell-Cantelli. $\endgroup$ – Yuval Filmus Feb 5 at 2:32
1
$\begingroup$

Here is a formal or informal proof, depending on how the probability distribution is defined.

Let $S_k=\left\{vvs\in\{0,1\}^\infty\mid v\in\{0,1\}^k,\ s\in\{0,1\}^\infty \right\}$, the sequences of infinite binary digits that repeat their initial $k$ binary digits immediately once (or more), where $k\ge1$.

$$\begin{align} \text{Prob[$S_k$]} &\le\frac1{2^{2k}}\#\left\{w\in\{0,1\}^{2k}\mid w\text{ can be extended to an element in } S_k\right\}\\ &\le\frac1{2^{2k}}\#\left\{w\in\{0,1\}^{2k}\mid w=vv \text{ for some } k \text{ binary digits } v\right\}\\ &=\frac1{2^{2k}}\#\left\{v\in\{0,1\}^{k}\right\}\\ &=\frac1{2^{2k}}2^{k}\\ &=\frac1{2^k}\,. \end{align}$$

Given an integer $i\ge1$ and a prefix-repetitive toss $S$, we know $S$ must be contained in $S_k$ for some $k\ge i$ since there infinitely many initial segments $v$ such that $vv$ is a prefix of S. Hence, $$\begin{align} \text{Prob[$S$ is prefix-repetitive]} &\le\sum_{k=i}^\infty\text{Prob[$S_k$]}\\ &\le\sum_{k=i}^\infty\frac1{2^{k}}\\ &=\frac1{2^{i-1}}\,.\\ \end{align}$$

Let $i$ go to infinity, we see that $$\text{Prob[$S$ is prefix-repetitive]} = 0\,.$$


Here are three related exercises.

Exercise 1. Show that the number of all prefix-repetitive tosses are more than countably infinite. Hence the approach mentioned in the question is unlikely to succeed.

Exercise 2. Show that if the bits of a sequence $S \in \{0, 1\}^\infty$ are chosen by independent tosses of an unfair coin, then Prob[S is prefix-repetitive] = 0.

Exercise 3. An infinite binary sequence $S \in \{0, 1\}^\infty$ is prefix-palindrome if there are infinitely many strings $v \in \{0, 1\}^*$ such that $vv^R$ is a prefix of $S$, where $v^R$ is the reverse of $v$. Show that if the bits of a sequence $S \in \{0, 1\}^\infty$ are chosen by independent tosses of a coin, then Prob[S is prefix-palindrome] = 0.

$\endgroup$

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.