Average Frequency of 1's in an Infinite Binary Sequences Can be Anything Between 0 and 1

The following question came up when me and a friend of mine were discussing some basic things about probability:

Let $p$ be a real number in $[0,1]$.

Does there exist a sequence $(x_1, x_2, x_3, \ldots)$ with each $x_i$ being either $0$ or $1$, such that

$$ \lim_{n\to \infty} \frac{f(n)}{n} =p $$

where $f(n)= x_1+x_2+\cdots+x_n$, that is, $f(n)$ is the number of times $1$ has appeared in the first $n$ slots.

Motivation: Consider a coin which may or may not be fair, and say the probability of "heads" showing up is $p$. Suppose we want to have a machine which simulates this coin. That is, we want to have a machine which shows either "H" or "T" every second ('second' here is a unit of time) on its screen. If the machine properly simulates the coin, then we must have the average frequency of "H" occuring is $p$.

Start with $x_1=0$ and then just let $x_{n+1}=1$ whenever $f(n)/n\leq p$ and $x_{n+1}=0$ whenever $f(n)/n> p$.

It's easy to prove by induction that we will always have $\left|\frac{f(n)}n-p\right|\leq\frac 1n$ and so $f(n)/n\rightarrow p$.

This is always possible. The idea is that we'll build the sequence $x_k$ so that $f(d)/d$ is always the best rational approximation to $p$ with denominator $d$.

Note that, for any irrational number $p$ and fixed denominator $d$, there is a unique best rational approximation to $p$ with denominator $d$, namely the unique $n/d$ satisfying the inequality $$ \left|p-\frac{n}{d}\right|<\frac{1}{2d} $$ (because the fractions with denominator $d$ are equally spaced at a distance of $\frac{1}{d}$, and so every real number except rationals with denominator $2d$ is within $\frac{1}{2d}$ of exactly one of them.)

That inequality can be rewritten as $$ \frac{2n-1}{2d} < p < \frac{2n+1}{2d} $$ which implies that $$ \frac{2n-1}{2(d+1)} < p < \frac{2(n+1)+1}{2(d+1)} $$ (as $\frac{2n-1}{2(d+1)}=\frac{2n-1}{2d+2} < \frac{2n-1}{2d}$, $\frac{2n+1}{2d} \leq \frac{2n+3}{2d+2}=\frac{2(n+1)+1}{2(d+1)}$ for all positive integers $n$ and $d$ with $n \leq d$).

This in turn implies that either $$ \left|p-\frac{n}{d+1}\right| < \frac{1}{2(d+1)} $$ or $$ \left|p-\frac{n+1}{d+1}\right| < \frac{1}{2(d+1)} $$ which is to say that, if $n/d$ is the best rational approximation to $p$ with denominator $d$, then either $n/(d+1)$ or $(n+1)/(d+1)$ is the best rational approximation to $p$ with denominator $d+1$. Assuming inductively that we've already chosen $x_1,\dots,x_d$ so that $f(d)=n$, we then take $x_{d+1}$ to be $0$ if $p$ is well-approximated by $n/(d+1)$, or $1$ if $p$ is well-approximated by $(n+1)/(d+1)$. It follows that $$\left|\frac{f(d)}{d}-p\right| < \frac{1}{2d}$$ for all $d$, and so in particular $\lim_{d \to \infty} \frac{f(d)}{d}=p$.

Note that this procedure actually works for rational numbers as well — and produces the sort of repeating sequence you'd expect — except that you have to make some specific rule for when $n/(d+1)$ and $(n+1)/(d+1)$ are equally good approximations to $p$. It doesn't matter what rule you choose, though...

Let $$x_i=1\iff((i-1)p,\ ip]\cap\mathbb N\ne\emptyset,$$ otherwise $x_i=0.$ Observe that $$\frac{x_1+\cdots+x_n}n=\frac{\lfloor np\rfloor}n,$$ $$p-\frac1n=\frac{np-1}n\lt\frac{\lfloor np\rfloor}n\le\frac{np}n=p,$$ whence $$p-\frac1n\lt\frac{x_1+\cdots+x_n}n\le p.$$

You can construct $x_n$ that will satisfy this requirement by definition:

• If $p=0$, then $\forall{i}:x_i=0$

• If $p=1$, then $\forall{i}:x_i=1$

• If $0<p<1$, then:

  $x_1=\lfloor2p\rfloor$

  $ \forall{i>1}:x_i= \begin{cases} 0 & \Big|{\frac{f(i-1)}{i}-p}\Big|\leq\Big|{\frac{f(i-1)+1}{i}-p}\Big|\\ 1 & \Big|{\frac{f(i-1)}{i}-p}\Big| > \Big|{\frac{f(i-1)+1}{i}-p}\Big|\\ \end{cases} $

Let $p \in [0,1]$.

For each $n \in \mathbb{N}$, define $s_n = \max \{ \frac{k}{n} : k \in \mathbb{Z} \text{ and } \frac{k}{n} \leq p\}$. Also define $s_0=0$. Note that $s_n$ converges to $p$ because $0 \leq p-s_n < \frac{1}{n}$ for all $n$.

For $n \in \mathbb{N}$, define $x_n := ns_n - (n-1)s_{n-1}$. Note that $\frac{f(n)}{n} =\frac{ns_n}{n}= s_n$, which converges to $p$.

Thus, we'll be finished if we can prove that $x_n \in \{ 0, 1 \}$, i.e, if we can prove that $(n-1)s_{n-1} \leq ns_n \leq 1+(n-1)s_{n-1}$ for all $n \in \mathbb{N}$. To prove this, let $n \geq 2$. Note that if $k <n$ and $\frac{k}{n-1} \geq p$, then $\frac{k+1}{n}\geq\frac{k}{n-1} \geq p$, so by applying this to $k=(n-1)s_{n-1}+1$ we get that $ns_n \leq 1+(n-1)s_{n-1}$. On the other hand we know that if $\frac{k}{n-1}<p$, then $\frac{k}{n} < \frac{k}{n-1}<p$, so applying this to $k= (n-1)s_{n-1}$ we get that $ns_n \geq (n-1)s_{n-1}$.

Edit: As an example of this construction, consider the case where $p=\frac{1}{\sqrt{2}}$. Then for the sequence of $s_n$ we get $0, \frac{1}{2}, \frac{2}{3}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{4}{7}, \frac{5}{8}, \frac{2}{3}, \frac{7}{10},\frac{7}{11}, \frac{2}{3} ...$ Then for $ns_n$ we get $0,1,2,2,3,4,4,5,6,7,7,8...$. Thus for the $x_n$ we get $0,1,1,0,1,1,0,1,1,1,0,1...$