Abstract-Problemet med slumptalsgenerering från en okorrelerad slumpmässig källa (av okänd sannolikhetsfördelning) går tillbaka till von Neumanns arbete 1951. Elias (1972) generaliserade von Neumanns plan och visade hur man uppnår optimal effektivitet i opartisk slumpmässig bitsgenerering. Vad är därför en naturlig fråga, om källorna är korrelerade? Både Elias och Samuelson föreslog metoder för att generera opartiska slumpmässiga bitar i fallet med korrelerade källor (av okänd sannolikhetsfördelning), specifikt, de ansåg ändliga Markov kedjor. De föreslagna metoderna är emellertid inte effektiva eller har genomförandesvårigheter. Blum (1986) utarbetade en algoritm för att effektivt generera slumpmässiga bitar från grad-2 finita Markov-kedjor i förväntad linjär tid, men hans vackra metod är fortfarande långt ifrån optimal på informationseffektivitet. I den här artikeln generaliserar vi Blums algoritm till godtycklig grad ändliga Markovkedjor och kombinerar den med Elias metod för effektiv generering av opartiska bitar. Som ett resultat av detta tillhandahåller vi den första kända algoritmen som genererar opartiska slumpmässiga bitar från en godtycklig finit Markov-kedja, fungerar i förväntad linjär tid och uppnår den informationsteoretiska övre gränsen för effektivitet.
I REF tillhandahöll författarna den första kända algoritmen som genererar opartiska slumpmässiga bitar från en godtycklig finit Markov-kedja, som fungerar i förväntad linjär tid och uppnår den informationsteoretiska övre gränsen för effektivitet.
Efficient Generation of Random Bits From Finite State Markov Chains
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Mathematics', 'Computer Science']}