Ask the Experts

Each day, you must make a binary decision: to buy or sell a stock, whether to bring an umbrella to work, whether to take surface streets or the freeway on your commute, etc. Each time you make the wrong decision, you are penalized. Fortunately you have help in the form of \(n\) “expert” advisers each of whom suggest a choice for you. However, some experts are more reliable than others, and you do not initially know which is the most reliable. How can you find the most reliable expert while…

Keep reading

Numberphile video on the Josephus Problem

Recently, the following Numberphile video on the Josephus Problem has been making the rounds on math-related social media. I watched the video, and I thought Daniel Erman did a remarkably good job at explaining how to solve a mathematical problem. Daniel’s approach is similar to the techniques described in Polya‘s “How to Solve It.” Yet the particular story that Daniel tells also has an appealing narrative arc. Daniel’s video adheres to the following principles, which I think are fairly universal in mathematical problem solving. Start with a…

Keep reading

Testing Equality in Networks

Yesterday, I went to an interesting talk by Klim Efremenko about testing equality in networks. The talk was based on his joint paper with Noga Alon and Benny Sudakov. The basic problem is as follows. Suppose there is a network with \(k\) nodes, and each node \(v\) has an input in the form of an \(n\)-bit string \(M_v \in \{0, 1\}^n\). All of the nodes in the network want to verify that all of their strings are equal, i.e., that \(M_v = M_u\) for all…

Keep reading

Probability Primer

This post is a very brief introduction to some basic concepts in probability theory. We encounter uncertainty often in our everyday lives, for example, in the weather, games of chance (think of rolling dice or shuffling a deck of cards), financial markets, etc. Probability theory provides a language to quantify uncertainty, thereby allowing us to reason about future events whose outcomes are not yet known. In this note, we only consider events where the number of potential outcomes is finite. The basic object of study in probability is a probability…

Keep reading

Audio Fingerprinting

The first time I saw the Shazam app, I was floored. The app listens to a clip of music through your phone’s microphone, and after a few seconds it is able to identify the recording. True to its name, the software works like magic. Even with significant background noise (for instance, in a noisy bar) the app can recognize that Feels Like We Only Go Backwards is playing on the jukebox. I recently came across a fantastic writeup by Will Drevo about how “audio fingerprinting” schemes are able to…

Keep reading