Card Trick Leads to New Bound on Data Compression

Here’s a card trick to impress your friends. Give a deck of cards to a pal and ask him or her to cut the deck, draw six cards and list their colours. You then immediately name the cards that have been drawn.

Magic? Not quite. Instead, it’s the next best thing: mathematics. The key is to arrange the deck in advance so that the sequence of the card colours follows a specific pattern called a binary De Bruijn cycle. A De Bruijn sequence is a set from an alphabet in which every possible subsequence appears exactly once.

So when a deck of cards meets this criteria, it uniquely defines any sequences of six consecutive cards. All you have to do to perform the trick is memorise the sequences.

Usually these kinds of tricks come about as the result of some new development in mathematical thinking. Today, Travis Gagie from the University of Chile in Santiago turns the tables. He says that this trick has led him to a new mathematical bound on data compression

Gagie achieves this new bound by considering a related trick. Instead of pre-arranging the cards, you shuffle the pack and then ask your friend to draw seven cards. He or she then lists the cards’ colours, replaces them in the pack and cuts the deck. You then examine the deck and say which cards were drawn.

This time you’re relying on probability to get the right answer. “It is not hard to show that the probability of two septuples of cards having the same colours in the same order is at most 1/128,” say Gagie.

He goes on to consider the probability of correctly predicting the sequence of cards pulled at random from a deck of a certain size and after a few extra steps, finds a lower bound on the probability of doing this correctly.

This turns out to be closely related to various problems of data compression and leads to a lower bound than has been found by any other means.

“We know of no previous lower bounds comparable to [this one],” he says.

That’s impressive, a really neat trick in itself.

Ref: arxiv.org/abs/1011.4609: Bounds from a Card Trick