Keep That Card in Mind: Card Guessing with Limited Memory
summary
A deterministic algorithm using about log^2 N bits of memory tracks log N nested ranges and guarantees about half sqrt(M) correct guesses in expectation against a random-shuffle dealer; randomized version with pairwise-independent permutations and O(log^2 N) long-lived randomness gives Ω(log N) or amplified to Θ(log N) correct guesses against any static adversary. A matching lower bound shows O(sqrt(M)) is optimal by a compression encoding. Against an adaptive dealer moves guessed cards to back, any M-bit guesser gets only about Θ(log M) correct guesses.
AI-written summary · about