Jane Street Shirt Problem

A month ago, Jane Street came to KAIST to present their company and what their employees did, which was quite fascinating. They also hosted an estimathon, and divided us into random groups to compete. It was quite fun! I solved some problems and I think our team did alright, but unfortunately we didn’t get the overall win. At the end of the session, they gave us all some stickers and a t-shirt with a nice little problem on it

(There’s supposed to be a photo! But I haven’t taken it yet :D)

$$ \lim_{n \to \infty }E \left[\int_{[0,1]^2} \left( \left (\sum_{i=1}^{n}1_{B(X_i, r_i)}(x)\right) \; mod \; 2 \right)\; dx\right] $$

Where $X_i$ and $r_i$ are independent random variable with distribution $X_i \sim U([0,1]^2)$ and $r_i \sim U(0, \sqrt{3/{\pi n}})$ . I think this is a really interesting problem and I’ve never encountered problems like this before. It seems daunting at first but it turns out to be quite simple to understand.

We can definitely see that it is finite (as the maximum value of the whole integral is 1), then by Fubini’s theorem we can rewrite it as

$$ \lim_{n \to \infty }\int_{[0,1]^2} E \left[\left( \left (\sum_{i=1}^{n}1_{B(X_i, r_i)}(x)\right) \; mod \; 2 \right)\right]\; dx $$

Then as the inner sum only possible value is either 0 or 1, we can rewrite the expectation to a sum of probability

$$E \left[\left( \left( \sum_{i=1}^{n}1_{B(X_i, r_i)}(x) \right) \; mod \; 2 \right)\right] = P \left( \left( \sum_{i=1}^{n}1_{B(X_i, r_i)}(x)\right) is \; odd \right) $$

Let’s take a step back and look at the probability of a fixed point being covered by one particular circle. The probability can be rephrased into the probability that the radius of the circle is large enough to contain that particular point, which is

$$ p = \pi E[r_i^2] = \pi \int_{0}^{\sqrt{3/{\pi n}}} \sqrt{\frac{\pi n}{3}} r_i^2 = \pi \left[\sqrt{\frac{\pi n}{3}} \frac{r_i^3}{3} \right]_{0}^{\sqrt{3/{\pi n}}} =1 / n $$

Which means that every point has a probability of $1/n$ of being covered by a circle. And as each circle is sampled independently, we can model how many circle covers a point by a binomial distribution with $p=1/n$. Using a well known formula for binomial successes, we got

$$ P \left( \left( \sum_{i=1}^{n}1_{B(X_i, r_i)}(x)\right) is \; odd \right) = \frac{1}{2} - \frac{1}{2}(1-{\frac{2}{n}})^n $$

Taking the limit, we have

$$ \lim_{n \to \infty }\frac{1}{2} - \frac{1}{2}(1-{\frac{2}{n}})^n = \frac{1}{2} - \frac{e^{-2}}{2} $$

Finally, as each of $\frac{1}{2} + \frac{1}{2}(1-{\frac{2}{n}})^n$ is bounded above by 1, we can apply Lebesque’s dominated convergence to get out final answer

$$ \lim_{n \to \infty }\int_{[0,1]^2} \frac{1}{2} - \frac{1}{2}(1-{\frac{2}{n}})^n\; dx = \int_{[0,1]^2} \lim_{n \to \infty } \frac{1}{2} - \frac{1}{2}(1-{\frac{2}{n}})^n\; dx = \frac{1}{2} - \frac{e^{-2}}{2} $$

This concludes my solution, it may not be that rigorous but I think it’s right :) I also made some visualization and simulation codes (which may not be finished yet)!