The German Tank Problem

The German Tank Problem supposes that there are N tanks with ID numbers from 1 to N. We don’t know what N is, but have looked at a single tank’s ID number, which we’ll denote m. How would you estimate N?

This is a well-known problem in statistics, and you’re welcome to go over to Wikipedia and decide that Wikipedia is a better resource than I am and, you know, fair. But, the particular angle I would like to take, is using this problem to understand the difference between Bayesian and frequentist approaches to statistics.

I’m aware of the popular framing of Bayesian and frequentist approaches as being in an adversarial relationship. I’ve heard some people say they believe that one approach is the correct one and the other doesn’t make any sense. I’m not going to go there. My stance is that even if you’re on Team Bayes or whatever, it’s probably good to understand both approaches at least on a technical level, and that’s what I seek to explain.

[Read more…]

Logic puzzles, overexplained

By “logic puzzle”, I don’t just mean puzzles involving logic, but rather a specific genre of puzzles, whose most famous types are Sudoku and Picross. There are many other types of such puzzles, and creators of logic puzzles can create entirely new types, if they are so inclined. If you’re not sure what I’m talking about, or if you’re just interested in finding logic puzzles, at the bottom of this post I’ve included a list of places you can find them.

I’m fairly good at logic puzzles. I’ve done the US Puzzle Championship for over a decade, and I placed in the top 25 once? So not like top-of-the-world good, but decent. And I’m a generalist, which is to say that relatively speaking I’m not very good with Sudoku, and I do better with other types of puzzles, including entirely new types.

My goal here is to overexplain my understanding of logic puzzles, and solving strategy. I am not confident that this is actually helpful to someone trying to get better at solving logic puzzles, but that’s not really the point. The point is to explicitly describe what would otherwise only be understood intuitively.

[Read more…]

The physics of jigsaw puzzles

Wholesome jigsaw puzzle youtuber Karen Kavett recently did a challenge where she assembled a 1000 piece puzzle by selecting 100 pieces at random at a time. For a while, this just looked like a bunch of scattered pieces with only a few connections. But once she had 700 or 800 pieces, the whole puzzle started to come together, despite the gaps.

I found this fascinating, because it is a live demonstration of a concept in physics/math: the percolative transition. This is something I often think about when assembling puzzles.

[Read more…]

Computational complexity of jigsaw puzzles

During the pandemic, I started doing more jigsaw puzzles. Not real puzzles mind you—I found a jigsaw simulator on Steam that was fairly authentic to the real experience. And since I was doing jigsaw puzzles through the medium of video games, I couldn’t help but think about them in the context of puzzle video games. I realized, jigsaw puzzles are kind of weird! In your typical puzzle video game, the ideal is to have a set of levels, each of which require some crucial insight. In contrast, a jigsaw puzzle is more like a large task that you chip away at.

One way of thinking about this is through the lens of computational complexity. Take Sokoban, the classic block pushing puzzle upon which many puzzle video games are founded. In general, a Sokoban puzzle of size N requires exp(N) time to solve, in the worst case. However, the typical Sokoban puzzle does not present the worst case, it presents a curated selection of puzzles that can be solved more quickly. This gives the solver an opportunity to feel clever, rather than just performing a computation.

Jigsaw puzzles, on the other hand, are about performing a computation. And, if you wish to do a large jigsaw puzzle in a reasonable amount of time, you look for ways to perform that computation efficiently. This raises the question: what is the computational complexity of a jigsaw puzzle?

According to the open access paper, “No easy puzzles: Hardness results for jigsaw puzzles” by Michael Brand, realistic jigsaw puzzles require Θ(N2) steps both in the worst case and on average. On the other hand, this is not born out by my own statistics, which seem to fit a straight line.

[Read more…]

Review scores: a philosophical investigation

Normally, in the introduction to an article, I would provide a “hook”, explaining my interest in the topic, and why you should be too. But my usual approach felt wrong here, since I cannot justify my own interest, and arguably if you’re reading this rather than scrolling past the title, you should be less interested than you currently are.

So, review scores. WTF are they? I don’t have the answers, but I sure have some questions. Why is 0/10 bad, 10/10 good, and 5/10… also bad? What goals do people have in assigning a score, and do they align with the goals of people reading the same score? What does it mean to take the average of many review scores? And why do we expect review scores to be normally distributed?

Mathematical structure

Review scores are intuitively understood as a measure of the quality of a work (such as a video game, movie, book, or LP)–or perhaps a measure of our enjoyment of the work? Already we have this question: is it quality, or is it enjoyment, or are those two concepts the same? But we must leave that question hanging, because there are more existentially pressing questions to come. Review scores do more than just express quality/enjoyment, they assign a number. And numbers are quite the loaded concept.

[Read more…]

From the Archives: Evaluating FiveThirtyEight

This is a repost of a simple analysis I did in 2012, evaluating the presidential predictions of FiveThirtyEight.  What a different time it was.  If readers are interested, I could try to repeat the analysis for 2020.

The news is saying that Nate Silver (who does election predictions at FiveThirtyEight) got fifty states out of fifty. It’s being reported as a victory of math nerds over pundits.

In my humble opinion, getting 50 out of 50 is somewhat meaningless. A lot of those states weren’t exactly swing states! And if he gets some of them wrong, that doesn’t mean his probabilistic predictions were wrong. Likewise, if he gets them right, that doesn’t mean he was right.

[Read more…]

A 2D voting sim

I made a Monte Carlo voting simulation. No particular reason, I just think it’s neat.

Okay, so I was thinking about the Median Voter Theorem, which says that the winning position in an election is the position of the median voter. Of course, this conclusion only holds under certain assumptions, and none of those assumptions are actually true. And yet the conclusion is approximately correct in many situations. That’s why we care disproportionately about the median congress members (like Susan Collins), the median Supreme Court Justices (like Roberts), and the median “swing” states (like Pennsylvania).

But it should be obvious that the median voter fails in a lot of ways. In particular, it doesn’t predict the political polarization that occurs in US politics. And there are plenty of possible explanations: voter turnout, third parties, primary elections, politician’s charisma factors, multidimensional political spectra, and so on. But I’m not sure which among those explanations are most important.

The voting simulation won’t answer any of these questions, I’m just setting the context. One of the assumptions of the Median Voter Theorem is that political preferences exist along only one dimension. I thought I’d try running simulations with two dimensions to see what would happen, and to make some pretty graphs.

Plot showing all the voters and candidates along a two dimensional spectrum.

Voters and candidates in a 2D space

[Read more…]