\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{Frog jump}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 145}
\maketitle

\section*{Problem}
There is a hidden infinite binary string $a_1a_2a_3\dots \in \{0,1\}^\infty$
such that $\{t \in \NN : a_t = 1\}$ has upper density zero.
The digits $a_t$ are revealed in order.
For each $t \ge 1$, before $a_t$ is revealed,
a frog decides to wait or cross the road.
Then $a_t$ is revealed.
If the frog crossed the road and $a_t = 1$, then the frog is squashed.
If the frog crossed the road and $a_t = 0$ then the frog has safely crossed the road.
Otherwise the process repeats with $a_{t+1}$.

Determine whether one can find a strategy such that,
regardless of which string $a_1 a_2 a_3 \dots$ is chosen,
the frog successfully crosses the road with probability at least $99\%$.

\section*{Video}
\href{https://www.youtube.com/watch?v=W2chl6FnsPg&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/W2chl6FnsPg}}

\section*{External Link}
\url{https://aops.com/community/p27344416}

\newpage

\section*{Solution}
Answer: yes.

Fix absolute constants $\delta, \eps > 0$.

Let's say an index $\ell \in \ZZ_{\ge 0}$ is \emph{bad}
if the density of $1$'s in $a_{2^\ell} \dots a_{2^{\ell+1}-1}$ is more than $\delta$;
we also say the interval $[2^\ell, 2^{\ell+1}-1]$ is bad.

\begin{claim*}
  There are only finitely many bad indices.
\end{claim*}
\begin{proof}
  If $\ell$ is a bad index,
  then the density of $1$'s in $\{a_1, \dots, a_{2^{\ell+1}-1}\}$ is at least $\delta/2$.
\end{proof}

The frog then employs the following strategy:
\begin{itemize}
  \ii Initialize $p = \eps$, $\ell = 0$, $t = 2^0$,
  just before $a_1$ is revealed.

  \ii With probability $p$, commit to jumping
  at a uniform random index in the set $\{2^\ell, \dots, 2^{\ell+1}-1\}$
  (ignoring any future data).

  \ii Otherwise, commit to not jumping for $t = 2^\ell, \dots, 2^{\ell+1}-1$.
  In that case, if the interval $[2^\ell, 2^{\ell+1}-1]$ turned out to be bad,
  halve the value of $p$.
\end{itemize}

Let $L = \{\ell_0, \dots, \ell_r\}$ be the finite set of bad indices.
The probability that the frog jumps in
the bad interval $[2^{\ell_i}, 2^{\ell_i+1}-1]$
is at most $\frac{\eps_0}{2^i}$ by the way the algorithm is set.
Consequently, the total probability of a jump inside any bad interval is at most
\[ \sum_{i \ge 0} \frac{\eps}{2^i} = 2\eps. \]
On the other hand, the probability of death when jumping inside a good interval
is also at most $\delta$.
And the frog jumps at some point with probability $1$.

Hence, the probability of success is at least $1 - (2\eps + \delta)$.
Therefore, picking e.g.\ $\eps = \delta = \frac{1}{300}$ solves the problem.

\end{document}
