Relative Randomness as Infinite Binary Sequences

Given infinite binary sequences $α,β : ℕ → \{0,1\}$, define $$δ_n = \dfrac{\sum_{i=1}^n {γ_i}}{n}$$ where $γ_i$ is the comparison of $α$ and $β$, i.e. $γ_i=1$ if $α(i)=β(i)$ and $γ_i=0$ otherwise. If $δ_n→z$ for some $z∈[0,1]$, then we write $δ(α,β)=z$. If $z=\dfrac{1}{2}$ in this case, we say $β$ is random relative to $α$ (or obviously vice versa). If $A$ is a set of infinite binary sequences, then we say $β$ is random relative to $A$ if $δ(α,β)=\dfrac{1}{2}$ for all $α∈A$.

Theorem 1 (Existence of Coins): If $X=(x_i)_{i∈ℕ}$ is a countable set of infinite binary sequences, then there exists an infinite binary sequence relatively random to $X$.

Proof: Choose any decreasing real sequence $ε_n→0$. We shall construct an infinite binary sequence $α$ such that for some sequence $N_n$ we have $|δ_i(α,x_j)-\dfrac{1}{2}| < ε_n$ for all $i ≥ N_n$ and $j ≤ n$. Hence as $i→∞$ we shall have $δ_i(α,x_j)→\dfrac{1}{2}$ for arbitrary $j$, implying $δ(α,x_j)=\dfrac{1}{2}$.

We shall attain this by constructing a sequence of finite binary sequences $α_{N_m} : \{1,...,N_m\}→\{0,1\}$ that are pairwise extensions of one another, and such that $|δ_i(α_{N_m}^*,x_j)-\dfrac{1}{2}| < ε_j$ for all free variables subject to $j≤m$ and $N_m+2^{m+1}≥i≥N_j$, and for all $α_{N_m}^* : \{1,...,N_m+2^{m+1}\}→\{0,1\}$ extending $α_{N_m}$. Then the sequence $α$ defined by $α(n) = α_{N_m}(n)$ for any $N_m≥n$ will satisfy the hypothesis above.

This shall be obtained by induction on $m$. (The base case will become superfluous, but is useful for comprehension) For $m=1$, let $β_1(k)=Φ_1(k)$ where $Φ_1(k)≡|\{j~|~j < k, x_1(j)=x_1(k)\}| \mod 2$, and then since we see $δ(β_1,x_1) = \dfrac{1}{2}$, choose $N_1$ large enough so that $$|\dfrac{(\sum_{j=1}^i γ_j)+4}{i+4} - \dfrac{1}{2}| < ε_1$$ $$|\dfrac{\sum_{j=1}^i γ_j}{i+4} - \dfrac{1}{2}| < ε_1$$ for $i ≥ N_1$, where $γ_i$ is the comparison between $β_1$ and $x_1$. Then the restriction $α_{N_1}$ of $β_1$ onto the set $\{1,...,N_1\}$ satisfies the hypothesis for $m=1$.

Now suppose appropriate $α_{N_m}$ has been constructed. Define $β_{m+1}$ by $β_{m+1}(k)=α_{N_m}(k)$ for $k≤N_m$, and otherwise, $β_{m+1}(k)=Φ_{m+1}(k)$ where $$Φ_{m+1}(k)≡|\{j~|~j < k, θ(j)=θ(k)\}| \mod 2$$ $$θ(n)=[x_i(n)]_{1≤i≤m+1}$$ Notice, then, that for any $1≤i≤m+1$ and any $(m+1)×1$ binary vector $v$, the proportion of $k > N_m$ such that $θ(k)=v$ satisfying $x_i(k)=β_{m+1}(k)$ as opposed to $x_i(k)≠β_{m+1}(k)$ approaches $\dfrac{1}{2}$, with at most $1$ extra nonsatisfying $k$ given any of the limit populations observed. Since for each $k > N_m$ there is one such vector $v$ for which $θ(k)=v$, and since there are $2^{m+1}$ vectors overall, for all $1≤i≤m+1$ we observe the proportion of such $k > N_m$ for which $x_i(k)=β_i(k)$ as opposed to $x_i(k)≠β_i(k)$ approaches $\dfrac{1}{2}$, with at most $2^{m+1}$ extra nonsatisfying $k$ given any of the limit populations observed. Therefore, there is sufficiently large $N_{m+1}$ for which $|δ_i(β_{m+1},x_j)-\dfrac{1}{2}| < ε_{m+1}$ for all free variables subject to $j≤m+1$ and $i≥N_j$; all that is missing is the $α_{N_{m+1}}^*$, and the variable index of $ε$. To fix the first, we rechoose $N_{m+1}$ to satisfy $$|\dfrac{(\sum_{j=1}^i γ_j)+2^{m+2}}{i+2^{m+2}} - \dfrac{1}{2}| < ε_{m+1}$$ $$|\dfrac{\sum_{j=1}^i γ_j}{i+2^{m+2}} - \dfrac{1}{2}| < {m+1}$$ for all $i≥m$ where $γ_j$ ranges being relative over $α_{N_1},...,α_{N_{m+1}}$ toward $β_{m+1}$, and then let $α_{m+1}$ be the restriction of $β_{m+1}$ onto $\{1,...,N_{m+1}\}$. Now, observing the upper bound of $2^{m+2}$ on the lag of the previously mentioned proportions of the limit populations in conjunction with the conditions just now qualified to $N_{m+1}$, we may finally conclude $|δ_i(α_{N_{m+1}}^*,x_j)-\dfrac{1}{2}| < ε_j$ for all free variables subject to $j≤m+1$ and $N_{m+1}+2^{m+2}≥i≥N_j$, and for all $α_{N_{m+1}}^* : \{1,...,N_{m+1}+2^{m+2}\}→\{0,1\}$ extending $α_{N_{m+1}}$. This completes the induction, and the proof.$~\square$

With some further complication of the frequency by which we choose $1$ or $0$ given a finite binary pattern vector (i.e. changing $Φ$ so that it isn't merely alternating), the above proof should generalize to show the existence of arbitrarily weighted coins, yielding heads at any given probability in the unit interval.

~~~~~

Given an infinite binary sequence $β$ and $α : ℕ→[0,1]$, define $$δ_n = \dfrac{\sum_{i=1}^n {γ_i}}{n}$$ where $γ_i$ is the comparison of $α$ and $β$, i.e. $γ_i=1-α(i)$ if $β(i)=0$ and $γ_i=α(i)$ otherwise. If $δ_n→z$ for some $z∈[0,1]$, then we write $δ(α,β)=z$. If $z=\dfrac{1}{2}$ in this case, we say $β$ is random relative to $α$. If $A$ is a set of infinite binary sequences, then we say $β$ is random relative to $A$ if $δ(α,β)=\dfrac{1}{2}$ for all $α∈A$.

Theorem 2: If $X$ is a countable set of functions $x_i : ℕ→[0,1]$, then there exists an infinite binary sequence relatively random to $X$.

Proof (sketch): If we define $δ_n'=δ_n-\dfrac{1}{2}=\dfrac{\sum_{i=1}^n {(γ_i-\dfrac{1}{2})}}{n}$ and $δ'=\lim_{n→∞} δ_n'$, then an equivalent reformulation of the problem for the case when $A$ is of finite order $m$ becomes: "Given a sequence $(v_i)$ of vectors of the form $(w_1,...,w_m)$ where $w_i∈[-1,1]$, does there exist a sequence $β=(b_i)$ where $b_i = \pm 1$ such that when $σ_j = \sum^j b_i·v_i$, we observe $\lim_{n→∞} \dfrac{σ_n}{n} = 0$?" As well, having solved this finite case, the countably infinite case will follow in a cumbersome manner as above and will thus be omitted.

Choose a decreasing real sequence $ε_n→0$. For each $n$, let $B_n$ be a partition of $[-1,1]^m$ into finitely many regions (say $\omega_n$) of diameter less than $2ε_n$. We shall inductively construct $β$ so that for sufficiently large indices $n > N_k$, we shall have $σ_n < ε_k·n$. As such, starting with $ε_i$, follow this procedure for as long as it takes for $σ_n$ to be able to incur $\omega_{i+1}$ consecutive "errors" and still be less than $ε_i·n$: At the start, all regions of $B_i$ are "inactive." Given the choice to set $b_j = \pm 1$, if $v_j$ is located in a region of $[-1,1]^m$ that is active, then set $b_j = -1$ and deactivate that region. Otherwise, activate the region and set $b_j=1$. Move on to $v_{j+1},b_{j+1}$. This process is seen to cancel vectors in partial sums with a per-step error factor approaching less than $\dfrac{1}{2}2ε_i=ε_i$ in magnitude.$~\square$

As with the first theorem, with some complication of the region that is to be finitely partitioned, the proof should generalize to show the existence of arbitrarily weighted coins.

~~~~~

Fix an infinite binary sequence $θ$. For infinite binary sequences $α$ and $β$, define $P(α)=δ(α,θ)$ and $P(α~|~β)=δ(γ,θ)$ where $γ(n)=α(b_n)$, if $b_n$ is the $n^\text{th}$ smallest integer to satisfy $β(b_n)=θ(b_n)$.

Theorem 3 (Bayes' Theorem): Suppose $P(α)$ and $P(β)$ exist and are nonzero. Then $$P(α~|~β)·P(β) = P(β~|~α)·P(α)$$ where if one side is undefined, then so is the other.

Proof: Suppose without loss that $P(β~|~α)$ is well defined. Let $γ_α$ denote its helper function, so that $δ_m(γ_α,θ)$ is the fraction of values $a_n ≤ m$ such that $β(a_n)=θ(a_n)$. This latter observation leads us to the identity $$δ_n(γ_α,θ)·(n·δ_n(α,θ))=δ_n(γ_β,θ)·(n·δ_n(β,θ))$$ when $γ_β$ is the associated helper function for $P(α~|~β)$. Therefore we derive $$P(α~|~β)·P(β) = \lim_{n→∞} δ_n(γ_β,θ) · \lim_{n→∞} δ_n(β,θ) = \lim_{n→∞} δ_n(γ_β,θ) · δ_n(β,θ) =$$ $$\lim_{n→∞} \dfrac{(n·δ_n(γ_β,θ)) · δ_n(β,θ)}{n} = \lim_{n→∞} \dfrac{(n·δ_n(γ_α,θ)) · δ_n(α,θ)}{n} =$$ $$\lim_{n→∞} δ_n(γ_α,θ) · \lim_{n→∞} δ_n(α,θ) = P(β~|~α)·P(α)~~\square$$