Posted on Categories data science, Mathematics, Statistics, TutorialsTags , , , , , 2 Comments on Imputing Out of Mixtures, or Un-Stirring Spicy Soup

Imputing Out of Mixtures, or Un-Stirring Spicy Soup

Here is a fun combinatorial puzzle. I’ve probably seen this used to teach before, but let’s try to define or work this one from memory. I would love to hear more solutions/analyses of this problem.

Suppose you have n kettles of soup labeled 0 through n-1. For our problem we assume that k kettles of soup are extremely spicy. We want to figure out which kettles contain spicy soup.

71FvGZBxgHL SX679

Image source: Mad Dog 357 / Amazon

This presents an interesting puzzle when k is much smaller than n. We are assuming that spicy is a rare event we want to detect. We are also assuming the spicy soups are so spicy, that they remain spicy even when combined with other soups. So when we prepare mixtures of soups we experience the union of the spiciness of the included soups.

The question is: if we prepare tasting bowls that are mixtures of samples from the kettles- how many bowls do we have to prepare to reliably identify all of the spicy soup kettles? This is hopefully in the spirit of the “counterfeit gold coin puzzle” as seen in the Columbo detective show (though I end up using a bit more math).

Continue reading Imputing Out of Mixtures, or Un-Stirring Spicy Soup

Posted on Categories Mathematics, Opinion, TutorialsTags , ,

A Beautiful 2 by 2 Matrix Identity

While working on a variation of the RcppDynProg algorithm we derived the following beautiful identity of 2 by 2 real matrices:

The superscript “top” denoting the transpose operation, the ||.||^2_2 denoting sum of squares norm, and the single |.| denoting determinant.

This is derived from one of the check equations for the Moore–Penrose inverse and we have details of the derivation here, and details of the messy algebra here.

Posted on Categories MathematicsTags , ,

Proof style in the Erdős-Ko-Rado theorem

I recently wrote a tiny bit about the style of the original published proof of the Erdős-Ko-Rado theorem. In this note I’ll write a bit about the theorem and a bit more about the style of some later proofs. In particular I want to write about two different readings of Katona’s proof. Continue reading Proof style in the Erdős-Ko-Rado theorem

Posted on Categories Computer Science, MathematicsTags , , 2 Comments on Erdős writing like a programmer

Erdős writing like a programmer

Here is a neat example of famous mathematician Pál Erdős (often rendered in English as Paul Erdős) writing like a programmer in 1961. He goes to some trouble to introduce notation that allows him to index everything from zero. Continue reading Erdős writing like a programmer

Posted on Categories Mathematics, OpinionTags , , , ,

The Mathematician’s Dilemma

A recent run of too many articles on the same topic (exhibits: A, B and C) puts me in a position where I feel the need to explain my motivation. Which itself becomes yet another article related to the original topic. The explanation I offer is: this is the way mathematicians think. To us mathematicians the tension is that there are far too many observable patterns in the world to be attributed to mere chance. So our dilemma is: for which patterns/regularities should we derive some underlying law and which ones are not worth worrying about. Or which conjectures should try to work all the way to proof or counter-example? Continue reading The Mathematician’s Dilemma