I'm unsure if the notation used by the author is common, so I will define some terms before stating the problem.
{$0, 1$}$^\infty$ is the set of all functions $f:\mathbb{N} \rightarrow ${$0, 1$}.
{$0, 1$}$^n$ is the set of all functions $f:$ {$1, ..., n$}$ \rightarrow ${$0, 1$}.
{$0, 1$}$^*$ = $\cup_{i=1}^\infty${$0,1$}$^i$.
Simply put {$0, 1$}$^\infty$ is the set of all infinite binary sequences, and {$0, 1$}$^n$ is the set of all binary sequences of length $n$, while {$0, 1$}$^*$ is the set of all finite binary sequences.
For any binary strings $X, Z$ we write $X \preceq Z$ if $X$ is a prefix of $Z$, that is, if $\exists Y$ such that $XY = Z$.
The problem:
Define an (infinite) binary sequence $S \in$ {$0, 1$}$^ \infty$ to be prefix-repetitive if there are infinitely many strings $w \in ${$0, 1$}$^*$ such that $ww \preceq S$
Prove: If the bits of the sequence $S \in ${$0, 1$}$^\infty$ are chosen by independent tosses of a fair coin, then
$Prob[S$ is prefix-repetitive$] =0$
My attempt.
Firstly, if $S$ is prefix-repetitive then $ \forall N \in\mathbb{N}, \exists n>N$ such that $aa \preceq S$ for some $a \in $ {$0, 1$}$^n$. We shall call this statement Lemma $1$.
Proof: choose $N \in \mathbb{N}$. Let $B$ be the set of all strings $b \in ${$0, 1$}$^*$ such that $bb \preceq S$. By the definition of prefix-repetitive $|B| = \infty$. Suppose there does not exist a string $a \in B$ such that $a \in $ {$0, 1$}$^n$ for some $n>N$. Then $B \subseteq \cup_{i=1} ^N$ {$0,1$}$^i$. However $|\cup_{i=1} ^N$ {$0,1$}$^i|$ is finite. A contradiction.
Secondly, let $M\in \mathbb{N}$, then
$Prob[\exists a \in ${$0, 1$}$^{m}$ such that $aa \preceq S$ for some $m>M] =$
$\sum_{i=M+1} ^\infty Prob[\exists a \in ${$0, 1$}$^{i}$ such that $aa \preceq S] = $
$\sum_{i=M+1} ^\infty \frac{1}{2^i} = \frac {1}{2^{M}}$
We shall call this result lemma $2$.
Lastly, we prove the main statement. Let $N\in \mathbb{N}$. By succesive use of lemma $1$ $\exists n_1, n_2, ...$ such that $N<n_1<n_2<...$ and $a_ka_k \preceq S$ for some $a_k \in ${$0,1$}$^{n_k}$. By lemma $2$ $Prob[a_k$ exists$] = \frac{1}{2^{n_k}}$, and $Prob[a_k$ exists $\forall k] = \frac{1}{2^{n_1}} \frac{1}{2^{n_2}} ... = 0$.
I'm not familiar with this area of mathematics and was wondering if my proof was valid. If not, how could I prove main statement?
I would really appreciate any help/thoughts!
Let $R_n$ be the event that the second block of $n$ bits matches the first block of $n$ bits, that is, the event that $ww\prec S$ for some $w\in\{0,1\}^n$, and let $N=N(S)=\sum_{n\ge1}\mathbb 1_{R_n}(S)$ be the number of $n$ such that $S\in R_n$, that is, the number of $n$ such that $ww\prec S$ for $w$ of length $n$. It might be finite or it might be infinite. If $N(S)<\infty$ then $S$ is not prefix repetitive, but if $N(S)=\infty$ then $S$ is prefix repetitive. Now note that $P(R_n)=2^{-n}$, so $EN = EN(S) = \sum_{n\ge1} 2^{-n} < \infty$. Hence $P(N(S)<\infty) = 1$. (By the Borel-Cantelli lemma, or the fact that random variables with finite expectations are finite with probability 1.) So with probability 1, $S$ is not prefix repetitive.
Where does this come up? What are you reading?