Skip to Content
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.

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

Keep Reading

Most Popular

Large language models can do jaw-dropping things. But nobody knows exactly why.

And that's a problem. Figuring it out is one of the biggest scientific puzzles of our time and a crucial step towards controlling more powerful future models.

OpenAI teases an amazing new generative video model called Sora

The firm is sharing Sora with a small group of safety testers but the rest of us will have to wait to learn more.

Google’s Gemini is now in everything. Here’s how you can try it out.

Gmail, Docs, and more will now come with Gemini baked in. But Europeans will have to wait before they can download the app.

This baby with a head camera helped teach an AI how kids learn language

A neural network trained on the experiences of a single young child managed to learn one of the core components of language: how to match words to the objects they represent.

Stay connected

Illustration by Rose Wong

Get the latest updates from
MIT Technology Review

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

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at customer-service@technologyreview.com with a list of newsletters you’d like to receive.