Consider the following poker-like game, played with two players: Alice and Bob. Bob posts a blind of 1. Both players are dealt a single, continuous hand chosen uniformly at random from $[0,1]$. Alice can fold, call, or raise any amount $b \gt 0$ (calling means $b = 0$). Bob either calls or folds. My original plan was to work out the Nash equilibrium for this game, and therefore derive interesting smooth curves describing the optimal way for Alice to bluff and generally obscure her hand.

Consider $n$ cars arranged in random order along a road, all moving in the same direction. Each car has its own distinct ideal speed, and will travel at that speed unless blocked by another car ahead. No passing is allowed (this is a windy, mountain road, say). After some time, the cars will have settled into a series of chains of cars, each composed of a bunch of cars trapped behind a slower car in the front of the chain.

Tai chi as a martial art seems far removed from actual fighting, since the motions are slow to the point of static. However, a few years ago during a conversation with Debra Page we came up with a cool analogy to describe part of why studying tai chi is valuable to the full speed case. I never got around to writing it up, so here goes: tai chi is like calculus.

Say you want to flip a perfect coin, but the only coins available are imperfect. First, let’s consider the case where we don’t know the details of the available coins, and would prefer not to measure them. The simplest strategy is to flip a bunch of coins and determine whether the total number of heads is even or odd. As long as there’s a reasonable number of both heads and tails, the probability of an even number of heads will be close to one half.

Currently, we (or at least I) don’t know how to do multigrid on general problems, so we’re stuck using conjugate gradient. The problem with conjugate gradient is that it is fundamentally about linear systems: given $Ax = b$, construct the Krylov subspace $b, Ax, A^2 x, \ldots$ and pick out the best available linear combination. It’s all in terms of linear spaces. Interesting human scale physics is mostly not about linear spaces: it’s about half-linear subspaces, or linear spaces with inequality constraints.

Here’s a combinatorial problem I found recently: given a 100 story building and two identical plates, what is the worst case number of drops required to determine the lower floor from which the plates break when dropped (if a plate drops and does not break, it is undamaged). The answer is 14, which I’ll state without proof. In the interest of completely useless generalization, we can ask what happens if we add more plates.

Success! I found a reference to Mertens’ theorem in a paper by Adam Kalai, which is exactly what I needed to analyze the complexity of the prime sieve from the previous post. Alas, my previous complexity guess was wrong. The actual complexity is $O(n^{3/2} / \log^3 n)$. Apparently my numerical estimates didn’t go out far enough (also I was biased towards finding $O(n \log^m n)$). From before, the cost of the algorithm is $O(C(n))$ where $$C(n) = \sum_{c \lt n} \pi(lpf(c ))$$ where $c \lt n$ means all composite numbers up to $n$.

Here’s an interesting lazy variant of the sieve of Eratosthenes by Nick Chapman, from a discussion on LTU: primes = 2 : diff [3..] (composites primes) composites (p:ps) = cs where cs = (pp) : merge (map (p) (merge ps cs)) (composites ps) merge (x:xs) (y:ys) | xy = diff (x:xs) ys In words, the algorithm computes the list of primes as all numbers which are not composites, and the computes the list of composites by extremely constructing and merging all prime factorizations.