Abstract-Generating slumpmässiga bitar från en källa av partiska mynt (den partiska är okänd) är en klassisk fråga som ursprungligen studerades av von Neumann. Det finns ett antal kända algoritmer som har asymptotiskt optimal informationseffektivitet, nämligen det förväntade antalet genererade slumpmässiga bitar per inmatning bit är asymptotiskt nära källans entropi. Men bara den ursprungliga von Neumann algoritmen har en "streaming egenskap" - den fungerar på en enda inmatning bit i taget och det genererar slumpmässiga bitar när det är möjligt, tyvärr, det inte har en optimal informationseffektivitet. Det viktigaste bidraget av detta papper är en algoritm som genererar slumpmässiga bitströmmar från partiska mynt, använder avgränsat utrymme och körs i förväntad linjär tid. När storleken på det tilldelade utrymmet ökar närmar sig algoritmen den informationsteoretiska övre gränsen för effektivitet. Dessutom diskuterar vi hur man utökar denna algoritm för att generera slumpmässiga bitströmmar från m-sidiga tärningar eller korrelerade källor som Markovkedjor.
I REF, författarnas huvudsakliga bidrag är en algoritm som genererar slumpmässiga bitströmmar från partiska mynt, använder avgränsat utrymme och körs i förväntad linjär tid.
Streaming Algorithms for Optimal Generation of Random Bits
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}