New coins from old: Computing with unknown bias (Q2368597)

For a word \(w\) over \(\{0,1\}\) and for a real \(p\in (0,1)\), let \(\mathbf P_p(w)=p^{n_1(w)}(1-p)^{n_0(w)}\) where \(n_i(w)\) is the number of occurrences of \(i\) in \(w\) for \(i=0,1\). For a language \(L\) over \(\{0,1\}\), let \(\mathbf P_p(L)=\sum_{w\in L}\mathbf P_p(w)\). A pair \( (L_0,L_1)\) of disjoint prefix-free languages over \(\{0,1\}\) simulates a function \(f:\mathcal D\to(0,1)\) where \(\mathcal D\subseteq (0,1)\) if \(\mathbf P_p(L_ 0\cup L_1)=1\) and \(\mathbf P_p(L_1)=f(p)\) for all \(p\in \mathcal D\). An automaton \(\mathcal A\) simulates \((L_0,L_1)\) if there exist disjoint sets \(A_0\) and \(A_1\) of states such that \(\mathcal A\) with a final set \(A_i\) accepts \(L_i\) for \(i=0,1\). We say that a simulation \((L_0,L_1)\) of \(f\) is a block simulation if there exist a positive integer \(k\) and disjoint sets \(A_0,A_1\subseteq \{0,1\}^k\) with \(L_i=(A')^{*}A_i\) for \( i=0,1\) where \(A'=\{0,1\}^k\setminus (A_0\cup A_1)\). It is proved that for a function \(f:\mathcal D \to(0,1)\) where \(\mathcal D\subseteq (0,1)\) the following are equivalent: 1) \(f\) can be block simulated, 2) \(f\) can be simulated via a finite automaton, 3) \(f\) is a restriction of a rational function over \(\mathbb Q\). If \(f\) can be simulated via a pushdown automaton then \(f\) is a restriction of an algebraic function over \(\mathbb Q\). Several examples and open problems are presented.