Jeremy Kun on the UCB1 algorithm for the multi-armed bandit problem. (Incidentally, none of the authors of the paper introducing the algorithm were affiliated with UCB – it stands for “upper confidence bound”.)

What is the sound of sorting?

Colm Mulcahy has a magic trick based on polydivisible numbers.

A friend of mine just got a job at Swapdom, which organizes multi-way swaps of clothes among people who don’t want them anymore and want to rejuvenate their wardrobes. You can search the community and point to things you would like and things you’d happily give up in exchange for them, and they find swaps that actually work. In particular they orchestrate multi-way swaps (A gives to B, which gives to C, which gives to A, or even longer cycles).

If you’re Alvin Roth, you can win a Nobel* Prize for this stuff. At least if it’s kidneys being traded instead of clothes.   The Nobel foundation has both popular and technical expositions of his work in market design; the largest kidney swap in history, a few months ago, involved 28 kidneys.

(Disclaimer: I don’t actually know what’s going on behind the scenes with Swapdom’s algorithm; my friend is not a technical person.)

The return of weekly links:

Statistics done wrong, a guide to the most common statistical errors.

Cloudflare (a web security company) has a primer on elliptic curve cryptography and its uses for privacy and security online. Quick version: RSA cryptography relies on the fact that multiplying integers is easy but factoring them is hard. Elliptic curve cryptography relies on the fact that there’s a group law for elliptic curves over the integers mod n, and applying that group law repeatedly (exponentiation) is easy but determining how many times that law was applied (taking the discrete logarithm) is hard.

I’ve been on a bit of an inadvertent hiatus from blogging – stuff picked up at my day job and then I got married. Time to get back into the swing of things.

I went to the DMV this morning. (That’s the “Department of Motor Vehicles”, for non-American readers; this is the government agency that handles vehicle registration and driver licensing.) It was “fun”, by which I mean not fun, but I was reminded of this clip from Seinfeld (transcript here):

JERRY: Elaine, what percentage of people would you say are good looking?

ELAINE: Twenty-five percent.

JERRY: Twenty-five percent, you say? No way! It’s like 4 to 6 percent. It’s a twenty to one shot.

ELAINE: You’re way off.

JERRY: Way off? Have you been to the motor vehicle bureau? It’s like a leper colony down there.

ELAINE: So what you are saying is that 90 to 95 percent of the population is undateable?

JERRY: UNDATEABLE!

ELAINE: Then how are all these people getting together?

JERRY: Alcohol.

Jerry is implying here that the people at the DMV are a good sample of the general population. This seems like a reasonable assumption, although of course we can quibble:

• rich people are more likely to own multiple cars, which means they have to go the DMV more often to handle car-registration-related business;
• similarly, poor people are more likely to not have cars at all and perhaps not even be licensed drivers. Since Seinfeld is set in New York, which has low car ownership rates, this is especially true, although it might be counteracted by the fact that public transit is better in the more wealthy parts of that city;
• results should vary by time of day, day of week, and DMV office

Still, it kept me amused while I waited.

From Deathsplanation, How tall is an alpaca? (and how long did people live in the past?)

From the Aperiodical, how to win at (the UK game show) Pointless.

Igor Pak has a collection of attempts to define combinatorics and a blog post on the subject.

From the MAA, some beautiful drawings of Platonic solids from the 16th-century printmaker Wenzel Jamnitzer.

From the Telegraph, Quants: the maths geniuses running Wall Street.

George Hart on making music with Mobius strips (following Dmitri Tymoczko).

Andrew Gelman and Kevin O’Rourke ask how statisticians pick their methods.

Carlos Futuri’s cartographical map projections.

OpenSignal on how phone batteries measure the weather (via Hacker News)

Hanging Hyena on unbeatable words in Hanging with Friends.

Emily Singer for Quanta magazine: In Natural Networks, Strength in Loops.

Hannah Fry on why everyone is more popular than you.

Jiri Matousek has a collection of Thirty-three miniatures: Mathematical and algorithmic applications of linear algebra

A Quora question, What kind of math do you use in your work?

Let’s say for some reason that you know $\sin \theta$ and $\cos \theta$, for some angle $\theta$, and you need to figure out what $\theta$ is. Let’s say, furthermore, that you live in some benighted age which doesn’t have calculators or even trigonometric tables.

There are a few approaches to this. One is what I did in my “Pythagoras goes linear” post. We can fit a linear model to the points

$(x_i, y_i) = (\cos \theta_i \sin \theta_i)$

where the $\theta_i$ range over an arithmetic sequence with endpoints 0 and $\latex \pi/2$, namely

$0, {\pi \over 2n}, {2\pi \over 2n}, \cdots, {n\pi \over 2n}.$

The model you get out is quite simple:

$\theta \approx \pi/4 - 0.7520 \sin \theta + 0.7520 \cos \theta$

This is actually just a few lines of R.

 n = 10^6
theta = (c(0:n))*pi/(2*n);
x = cos(theta); y = sin(theta);
summary(lm(theta~x+y))

I’ll save you the output, but be impressed: r2 = 0.9992\$, and the mean square error is 0.0126 radians or 0.72 degrees. So we can write $\theta \approx \pi/4 + 0.7520 (-\cos \theta + \sin \theta)$, in radians. In degrees this is $\theta \approx 45^o + 43.08^o(-\cos \theta + \sin \theta)$.

For example, say you have an angle with $\sin \theta = 5/13, \cos \theta = 12/13$ — the smaller angle of a 5-12-13 right triangle. Then we get $\theta \approx 45^o + 43.08^o (-7/13) \approx 21.8^o$. In fact $\theta = \tan^{-1} 5/12 \approx 22.6^o$ — we’re not off by much! And the error is never more than a couple degrees, as you can see in the plot below.

This was inspired by a post by Jordan Ellenberg that I came across recently: How to compute arctangent if you live in the 18th century, which refers back to my Pythagoras goes linear. A better approximation, although nonlinear, is

$\theta \approx (3y)/(2 + x)$

where $x = \sin \theta, y = \cos \theta$. This is essentially a simplification of the rule that Ellenberg’s source (Hugh Worthington’s 1780 textbook, The Resolution of Triangles) gives, which can be translated into our notation as

$\theta = {86*pi \over 180} {y \over x/2 + 1}.$ Applying this to our test angle with $x = 12/13, y = 5/13$, we get $\theta \approx 15/38 = 0.39474$ radians, while in truth $\tan^{-1} 5/12 = 0.39479$.

This formula $\theta \approx (3y)/(2+x)$ is so nice that I can’t help but suspect there’s a simple derivation. Any takers?