Combinatorial Group Testing Magic Trick

You probably recall the different puzzles that feature some aspect or another of either compressive sensing or group testing. They are all listed here. Well, Anna Gilbert came up with one and detailed it in one of her blog entry entitled: Combinatorial Group Testing Magic Trick, please check it out for the instructions, I'll wait. Here is the YouTube video featuring the trick. 

Instead of asking the audience if it is their number 31 times, the magician asks only 5 questions. This is reminiscent of this trick (and attendant solution). As I said then, what separates this trick from others is that this one is non-adaptive, i.e. performing a bisection algorithm would also require five draws but it would be adaptive and would be readily understood by the audience. In other words, the magician doesn't need to compute anything while asking questions and doesn't let the audience know about what is going on. Also, whereas the decoding (finding the card) is done mechanically here, it requires a simple operation in the case of the 64 deck of cards. In both cases, very little effort is required on the part of the performer. 

Ever since the initial connection between compressive sensing and group testing by Anna and colleagues, it has yielded a number of productive insights both in compressive sensing and in group testing. Let me just add that group testing, as done here, is a special case of 2-bit quantized compressive sensing (a form of nonlinear compressive sensing) and is my favorite introductory example as shown in the recent presentation at Supelec.

Little thought question, considering everything we know about quantized compressive sensing and if the magician was willing to be the laughingstock of his/her audience, say with a 1 percent chance of not finding the card, how should this magic trick or the 64 deck of cards be re-designed ? What would be the minimal number of draws as a function of the trick failing ? wht sort of phase diagram can we have ?

Magic trick related are those entries featuring Persi Diaconis: We are not pleased with your conclusions... and Does anything happen at random ?.

Anna, Muthu, Hung Ngo, Ely Porat, Atri Rudra and Martin Strauss are organizing the SPARC 2013 meeting next week. Here is the abstract list.

 From the Compressed Sensing Puzzle page;

Different puzzles can be solved through the use of Compressive Sensing and Group Testing procedures as each of them is trying to find one unique element out of many:

• The 12-balls / coins problem (statement, solution): Find one ball out of twelve with three measurements

• Sudoku (solution in Python, solution in Matlab): Find one combination out of many with some known entries

• A magic trick with six cards (statement, solution):Find one number out of 63 in six measurements.

• or any of the puzzles listed in the Balance Puzzle.

Other examples include:
Finding three Cylons out of many people in the new Battlestar Galactica
Finding the few people with Syphilis out of many soldiers during WWII.

Other more up to date examples of high dimensionality group testing are listed under the "grouptesting" tag on Nuit Blanche.

If you come across others, please contact me, I'll be glad to feature them on Nuit Blanche.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.