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
Deep Dive
Uncategorized

It will soon be easy for self-driving cars to hide in plain sight. We shouldn’t let them.
If they ever hit our roads for real, other drivers need to know exactly what they are.

Maximize business value with data-driven strategies
Every organization is now collecting data, but few are truly data driven. Here are five ways data can transform your business.

Cryptocurrency fuels new business opportunities
As adoption of digital assets accelerates, companies are investing in innovative products and services.

Where to get abortion pills and how to use them
New US restrictions could turn abortion into do-it-yourself medicine, but there might be legal risks.
Stay connected

Get the latest updates from
MIT Technology Review
Discover special offers, top stories, upcoming events, and more.