Antag att vi får en funktion f : (0, 1) → (0, 1) och, för några okända p  till (0, 1), en sekvens av oberoende kast av en p-mynt (dvs, ett mynt med sannolikhet p av "huvuden"). För vilka funktioner f är det möjligt att simulera en f (p)-mynt? Denna fråga togs upp av S. Asmussen och J. Propp. Ett enkelt simuleringsschema för den konstanta funktionen f (p)  på 1/2 beskrevs av von Neumann (1951); detta system kan enkelt implementeras med hjälp av en ändlig automaton. Vi bevisar att i allmänhet kan en f (p)-mynt simuleras av en ändlig automaton för alla p 0, 1), om och endast om f är en rationell funktion över Q. Vi visar också att om en f (p)-mynt kan simuleras av en pushdown automaton, då f är en algebraisk funktion över Q; dock, pushdown automata kan simulera f (p)-mynt för vissa icke-rationella funktioner som f (p) = ε p. Dessa resultat kompletterar arbetet av Keane och O'Brien (1994), som bestämde de funktioner f för vilka en f (p)-mynt kan simuleras när det inte finns några beräkningsbegränsningar för simuleringssystemet.
Mossel, Peres och Hillar REF karakteriserar uppsättningen funktioner f : (0, 1) → (0, 1) för vilka det är möjligt att simulera ett f (p)-försått mynt med ett p-försått mynt när p är okänt.
New coins from old : computing with unknown bias
{'venue': 'Combinatorial Algorithms on Words, ed. A. Apostolico and Z. Galil, NATO ASI SERIES, Springer-Verlag', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}