Keep that card in mind

2021-07-08-MN-Keep That Card in Mind: Card Guessing with Limited Memory.pdf

paper

Results

Setup

• A Dealer deals cards via some strategy from a set of cards labeled by $1,\dots,n$.
• Guesser has to guess which card is dealt.
• A guesser with perfect memory can guess $\ln n$ correct guesses.
  • The guesser remembers which cards are played and picks randomly from the remaining cards.
• With no memory, the guesser can guess only 1 in expectation.

Results

• Guesser with $O(\log^2 n)$ bits has a near optimal result (static or random shuffle).
• No Guesser with $m$ bits of memory can score better than $O(\sqrt{m})$ correct guesses.
• There exists an adaptive dealer for which no guesser with memory $m$ can make more than $\ln m + 2\ln \log n + O(1)$ correct guesses in expectation.

Overview of Proofs

• Main result:
  • The guesser tracks from which cards were drawn from multiple subsets.
  • Every subset card in the subset is "tracked" by at most $2\log n$ bits.
  • Guesser can recover the last card that has not appeared in each subset and guesses it.
  • Subsets are build incrementally such that the $i$th subset contains the $i+1$th.
• Lower Bound:
  • The lower bound is proven by using correct guesses to encode an ordered set.
  • The encoding simulates the game and the bottom is the ordered set we wish to encode.
  • If sufficiently many correct guesses occur we store what is required to encode this game.
  • This gives us the set.
  • We store:
    • The memory state of the guesser
    • The set of turns it predicted correctly
    • The cards the dealer draws in the other turns with their order.
  • The memory saving is from turns predicted correctly + state of the guesser.
  • We also fix the randomness of the guesser overall (not per set) to make this deterministic.

Simple Strategies

• Subset Guessing:
  • Chose a random or predetermined subset of cards $A\in \binom{[n]}{m}$.
  • Every turn the guesser guesses one card in $A$ that not yet has occured.
  • This requires $m$ bits to store.
  • Counting the turns in which the dealer draws cards from $A$ we get that the guesser makes $\ln m$ correct guesses.
  • $1/n + 1/(n-1) + 1/(n-2) + \dots + 1/2 + 1$.
  • This works against any dealer as these cards have to be drawn at some point in the game.
  • Because we can predetermine the set and the above fact we do not need to store a description of the set.
• Remembering last $k$ cards:
  • Guess the last card by storing the sum $\sum_{i=1}^n i$ and subtract the card shown.
  • This generalizes via chinese remainder to $k$ cards.
  • Store $\sum_{i=1}^n i^p \mod n$ for $p=1,\dots, k$ and remove $d^p$ for the shown card $d$.
  • This requires $k\log n$ bits.
  • As the set of the last cards is now know, we make $\ln k$ correct guesses.
  • This works against any dealer.

Less Simple Strategy

• For certain subsets $S_1,\dots,$ store the number of cards seen from this subset and the number as in the remembering last $k$ cards.
• The sets will be $[1,2], [1,2,3,4], \dots, [1,\dots,n]$.
• Proof:
  • Call a set $S_i = [1,\dots,w]$ useful if the last card that appears in it does not appear in the next subset $S_{i+1}$.
  • Every subset will contribute a correct guess but it could be that the same guess comes from multiple subsets.
  • Not so if the subset is useful.
  • The probability that a subset is useful is $(2w-w)/2w$.
  • Hence, the expected number of useful sets is $\log n/2$.

Lower Bound Argument

• Any Guesser using $m$ bits of memory can get at most $O(\min { \ln n, \sqrt{m}})$ correct guesses in expectation against random shuffle dealer.
• Compression Argument:
  • Encoding function for ordered set $B$:
    • Simulate the guesser on a deck of cards where the last $k$ cards are $B$ (including order).
    • Record the memory of the guesser $m$ bits after the first $n-k$ cards.
    • If the guesser gives $\ell$ correct guesses than we supply the remaining $k-\ell$ guesses (without position).
    • We note the positions where the guesser was correct.
    • This gives us a size of $m + \log \binom{k}{\ell} + \log (\prod_{i=0}^{k-\ell-1} n-i)$.
    • The number of ordered sets is $\prod_{i=0}^{k-1} n-i$.
    • The probability over the choices of $B$ for any correct guess beyond $\frac{m+1}{\beta \ln n}$ drops exponentially.
      • This comes from comparing the encoding size with the size of the ordered sets.
    • Now we can use the following Lemma (2.1.5) and prefix freeness of the constructed code.
    • For every encoding function the probability that the encoding is $d$ bits less than its entropy is at most $2^{-d}$.

Other Results

• For every $m$ there exists an adaptive dealer such that any guesser makes at most $\ln m + 2\ln \log n + O(1)$ correct guesses.

Questions

• All of them seem to have a low probability for some cards.
• So can we make a guesser that will have a non negligable probability on all dealers?