Let $(X\_n)\_{n \geq 0}$ be an i.i.d. sequence of $\{0,1\}$-valued random variables $X\_n \sim \mathrm{Bernoulli}(\frac{1}{2})$, i.e. a sequence of independent tosses of a fair coin.



> 
> Does there exist a (non-random) Borel-measurable function $h \colon \{0,1\}^{\mathbb{Z}\_{\geq 0}} \to \mathbb{Z}\_{\geq 0}$ such that
> $$ \mathbb{P}(\exists\,\text{infinitely many } k \geq 0 \text{ s.t. }h((X\_{k+n})\_{n \geq 0})=k ) = 1 \, \text{?} $$
> 
> 
> 



Does a sequence of coin-tosses a.s. have a subsequence on which the remainder of the sequence can be identified with the position in the sequence?
Such a function $h$ does not exist.


Indeed, given a Borel-measurable function $h \colon \{0,1\}^{\mathbb{Z}\_{\geq 0}} \to \mathbb{Z}\_{\geq 0},$ define for each $k \ge 0$ the events
$$A\_k=\Bigl\{h \Bigl((X\_{n})\_{n \geq 0}\Bigr)=k \Bigr\}$$
and
$$B\_k=\Bigl\{h \Bigl((X\_{k+n})\_{n \geq 0}\Bigr)=k \Bigr\} \,.$$
Clearly,
$$\mathbb{P}(A\_k)=\mathbb{P}(B\_k) \;\; \mbox{for every} \; k \ge 0.
$$
The $A\_k$ are disjoint events that partition the probabiility space, so
$$ 1=\sum\_{k \ge 0} \mathbb{P}(A\_k)=\sum\_{k \ge 0}\mathbb{P}(B\_k) \,.
$$
Therefore, by the (first) Borel-Cantelli lemma,
$$ \mathbb{P}(\exists\,\text{infinitely many } k \geq 0 \text{ s.t. }h((X\_{k+n})\_{n \geq 0})=k ) = 0 \,.
$$


<https://en.wikipedia.org/wiki/Borel%E2%80%93Cantelli_lemma>


