Uncategorized

# Card Trick Leads to New Bound on Data Compression

A magician’s card trick has prompted a mathematical re-evaluation of the limits on data compression.
November 26, 2010

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

### DeepMind’s cofounder: Generative AI is just a phase. What’s next is interactive AI.

“This is a profound moment in the history of technology,” says Mustafa Suleyman.

New variants will pose a challenge, but early signs suggest the shots will still boost antibody responses.

### Human-plus-AI solutions mitigate security threats

With the right human oversight, emerging technologies like artificial intelligence can help keep business and customer data secure

### Next slide, please: A brief history of the corporate presentation

From million-dollar slide shows to Steve Jobs’s introduction of the iPhone, a bit of show business never hurt plain old business.

### Stay connected

Illustration by Rose Wong

## Get the latest updates fromMIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!