Proof of an Infinite Binary Sequence 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!
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$]}
&amp;\le\frac1{2^{2k}}\#\left\{w\in\{0,1\}^{2k}\mid w\text{ can be extended to an element in } S_k\right\}\\
&amp;\le\frac1{2^{2k}}\#\left\{w\in\{0,1\}^{2k}\mid w=vv \text{ for some } k \text{ binary digits } v\right\}\\
&amp;=\frac1{2^{2k}}\#\left\{v\in\{0,1\}^{k}\right\}\\
&amp;=\frac1{2^{2k}}2^{k}\\
&amp;=\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]} 
&amp;\le\sum_{k=i}^\infty\text{Prob[$S_k$]}\\
&amp;\le\sum_{k=i}^\infty\frac1{2^{k}}\\
&amp;=\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.