Dummymandering for Dummies

In the next election cycle you’re back at it, gerrymandering on behalf of the Moon party once more. This time, you can draw a map that results in any set of probabilities $p_1$, $p_2$, $p_3$, $p_3$, $p_5$, $p_6$, and $p_7$ that you’ll win each of the corresponding districts—subject to the constraint that the average of the probabilities is $1/2.$ In other words, $$p_1 + p_2 + p_3 + p_4 + p_5 + p_6 + p_7 = 7/2.$$

The bosses of the Moon party want to go big. More specifically, they want to maximize the party’s chances of winning at least five of the seven districts. However, you are concerned that such a greedy attempt at gerrymandering may backfire, a phenomenon that has become known as dummymandering. When you draw a map that maximizes your chances of winning at least five districts, the probability the Moon party blows it and winds up losing most of the districts is $L_A.$

Your personal preference is to simply maximize the party’s chances of winning at least four of the seven districts—a simple majority of them. When you draw that maximizes these chances, the probability the Moon party loses most of the districts is $L_B.$ How much greater than $L_B$ is $L_A$?

Again, we will assume that $p_1 \leq p_2 \leq p_3 \leq \cdots \leq p_7.$ We have $X_i \sim B(p_i)$ is a Bernoulli distribution with probability of success $p_i.$ Then the Moons want $\sum_{i=1}^7 X_i \geq 5,$ so we should determine $$f_5(p) = \mathbb{P} \left\{ \sum_{i=1}^7 X_i \geq 5 \right\}.$$ In particular, we could have $$g(p) = \mathbb{P} \left\{ \sum_{i=1}^7 X_i = 7 \right\} = p_1 p_2 \cdots p_7.$$ We have $$h(p)=\mathbb{P} \left\{ \sum_{i=1}^7 X_i = 6 \right\} = (1-p_1) p_2 \cdots p_7 + p_1 (1-p_2) p_3 \cdots p_7 + \cdots + p_1 \cdots p_6 (1-p_7).$$ Finally, we have \begin{align*} k(p) = \mathbb{P} \left\{ \sum_{i=1}^7 X_i = 5 \right\} &= (1-p_1)(1-p_2) p_3 \cdots p_7 + (1-p_1)p_2(1-p_3)p_4 \cdots p_7 + \cdots + (1-p_1)p_2 \cdots p_6 (1-p_7) \\ & \quad + p_1 (1-p_2) (1-p_3) p_4 \cdots p_7 + \cdots + p_1 (1-p_2) p_3 \cdots p_6 (1-p_7) \\ & \quad\quad + \cdots + p_1 p_2 \cdots p_5 (1-p_6)(1-p_7)\end{align*} Putting this altogether we get f_5(p) = g(p) + h(p) + k(p), and for instance, we see that \begin{align*}f_5(p) &= p_1 \Biggl( p_2 \cdots p_7 + (1-p_2) p_3 \cdots p_7 + p_2 (1-p_3) p_4 \cdots p_7 + \cdots + p_2 \cdots p_6 (1-p_7) \Biggr. \\ & \quad\quad\quad\quad \Biggl.+ (1-p_2) (1 - p_3) p_4 \cdots p_7 + \cdots + p_2 \cdots p_5 (1-p_6) (1 - p_7) \Biggr) + \\ & \quad + (1 - p_1) \Biggl( p_2 \cdots p_7 + (1 - p_2) p_3 \cdots p_7 + p_2 (1-p_3) p_4 \cdots p_7 + \cdots + p_2 \cdots p_6 (1 -p_7 ) \Biggr) \\ & \quad\quad\quad + \text{ other terms not involving $p_1$ } \\ &= p_1 \Biggl( (1-p_2)(1-p_3) p_4 \cdots p_7 + (1-p_2) p_3 (1-p_4) p_5 p_6 p_7 + \cdots + p_2 \cdots p_5 (1-p_6) (1-p_7) \Biggr) \\ &\quad + \text{ other terms not involving $p_1$}.\end{align*} Therefore, we see that $\frac{\partial}{\partial p_1} f_5(p) \geq 0$ for all $0 \leq p \leq 1.$ Since the choice of $p_1$ was arbitrary, this holds for all $p_i, i = 1, \dots, 7.$ So it is clear that there will not be some $p^*$ such that $\nabla f_5(p^*) = 0.$ Therefore, we need to look at the boundary $\sum_{i=1}^7 p_i = 7/2,$ along with the other boundaries $0 \leq p_1 \leq p_2 \leq \cdots \leq p_6 \leq p_7 \leq 1.$

In particular, we need to look at potential solutions of the form $$q^{i,j} = \bigl( \overbrace{0, \dots, 0}^{i}, \overbrace{\lambda_{ij}, \dots, \lambda_{ij}}^{7-i-j}, \overbrace{1, \dots, 1}^j \bigr),$$ where $\lambda_{ij} = \frac{7 - 2j}{2(7- i - j)}.$ We see that for each $i, j,$ $$0 \leq q^{i,j}_1 \leq q^{i,j}_2 \leq \cdots \leq q^{i,j}_7 \leq 1,$$ and we have $$\sum_{k=1}^7 q^{i,j}_k = i \cdot 0 + (7-i-j) \cdot \lambda_{ij} + j \cdot 1 = \frac{7}{2}.$$ Plugging $q^{i,j}$ into $f_5(p),$ we see that, since the Moons will automatically lose $i$ districts and win $j$ districts, that $$f_5(q^{i,j}) = \sum_{k=5}^{7-i} \binom{7-i-j}{k-j} (1 - \lambda_{ij})^{7-i-k} \lambda_{ij}^{k-j},$$ which is just the upper tail of a binomial distribution with probability $\lambda_{ij}.$

Since we are already at it, and without the need to rigorously reprove anything, we can also define $$f_4(p) = \mathbb{P} \left\{ \sum_{i=1}^7 X_i \geq 4 \right\}.$$ We can reassert that when maximizing for $f_4$ that there will be no feasible solutions p^* with \nabla f_4(p^*) = 0, so we will also look for $f_4(q^{i,j})$ as previously define, where we additionally have $$f_4(q^{i,j}) = \sum_{k=4}^{7-i} \binom{7-i-j}{k-j} (1 - \lambda_{ik})^{7-i-k} \lambda_{ij}^{k-j}.$$

We obviously cannot have $j \gt 3,$ since there is only $7/2$ total probability to go around. Similarly, we see that $f_5(q^{5,j}) = 0,$ for each $j,$ since you have already allowed the Suns to win 3 districts and hence can only win a maximum of 4. Additionally, whenever So for $i, j \in \{0,1,2, 3\},$ we can calculate the values of $f_5$ and $f_4$ using some handy-dandy calculators, whether Excel or numpy or whatever you fancy, to obtain the following table:

$i$	$j$	$\lambda_{ij}$	$f_5(q^{i,j})$	$f_4(q^{i,j})$
$0$	$0$	$1/2$	$0.2265625$	$0.5000000$
$1$	$0$	$7/12$	$0.2082593$	$0.5097931$
$2$	$0$	$7/10$	$0.1680700$	$0.5282200$
$3$	$0$	$7/8$	$0.0000000$	$0.5861864$
$0$	$1$	$5/12$	$0.2030319$	$0.4902069$
$1$	$1$	$1/2$	$0.1875000$	$0.5000000$
$2$	$1$	$5/8$	$0.1525878$	$0.5187988$
$3$	$1$	$5/8$	$0.0000000$	$0.5787037$
$0$	$2$	$3/10$	$0.1630800$	$0.4717800$
$1$	$2$	$3/8$	$0.1680700$	$0.4812012$
$2$	$2$	$1/2$	$0.1516113$	$0.5000000$
$3$	$2$	$3/4$	$0.1516113$	$0.5625000$
$0$	$3$	$1/8$	$0.1630800$	$0.4138184$
$1$	$3$	$1/6$	$0.0740741$	$0.4212963$
$2$	$3$	$1/4$	$0.0625000$	$0.4375000$
$3$	$3$	$1/2$	$0.0000000$	$0.5000000$

We further note that the probability of losing the election is $L(p) = 1 - f_4(p).$ Therefore, we see that if the Moons want to greedily maximize the probability of winning at least 5 districts, then they need to pick $$p^A = (1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2),$$ which will give probability of losing the election of $$L_A = 1 - f_4(p^A) = \frac{1}{2}.$$ However, we see that $p^B = (0, 0, 0, 7/8, 7/8, 7/8, 7/8)$ is the maximizer of $f_4,$ which means that $$L_B = 1 - f_4(p^B) = 1- \frac{2401}{4096} = \frac{1695}{4096} = 0.4138184\dots.$$ Therefore, we see that the Moons' greedy decision to maximize the probability of winning 5 or more districts cost them $$L_A - L_B = \frac{353}{4096} = 8.61816\dots \%$$ in winning percentage.

Non-representative Democracy

Fiddler Nation has an upcoming election between its two major political parties: the Suns and the Moons. You are drawing a new electoral map, and you have been tasked with gerrymandering on behalf of your party, the Moons. Fortunately, you know exactly how every citizen will vote in the election.

Fiddler Nation has seven districts, each with an equal population. For simplicity, assume that the Moons win any district in which they receive at least half of the vote.

What is the smallest total fraction of Fiddler Nation’s population needed to vote Moon such that it’s possible for the Moons to win a majority of the seven districts?

Let's let $p_i \in [0,1]$ be the proportion of voters in district $i$ that vote for the Moons. We see that the Moons will win district $i$ if and only if $p_i \geq 0.5.$ So without loss of generality, we assume that $p_1 \leq p_2 \leq \dots \leq p_6 \leq p_7,$ so if the Moons are only going to win 4 districts, then they would win districts 4 through 7, that is we would need $p_i \geq 0.5, i = 4, \dots, 7.$ Since each district has the same population, say $1/7$ of the total, we have that the total number of votes for the Moons would be $\frac{1}{7} \sum_{i=1}^7 p_i.$ For the classic problem, we want \begin{align*} \min \,\, & \frac{1}{7} \sum_{i=1}^7 p_i \\ \text{suct that} \,\, & 0 \leq p_1 \leq p_2 \leq \dots \leq p_6 \leq p_7 \leq 1 \\ & p_i \geq \frac{1}{2}, \, i = 4, 5, 6, 7\end{align*} We see that the minimizer is $$p^*_1 = p_2^* = p_3^* = 0, p^*_4 = p^*_5 = p^*_6 = p_7^* = 1/2,$$ so the smallest total proportion of the entire voting population to vote for the Moons that could result in a Moon victory is $$p^* = \frac{1}{7} \left( 3 \cdot 0 + 4 \cdot \frac{1}{2} \right) = \frac{2}{7}$$ of the population, which is indeed a pitifully low portion of the populace.

Surf's Up 2: WaveMania

The surfer rides the crest of the combined wave, $y = 2\sin(x−t) + \sin(x+2t),$ for a very long time. What is her average speed, in meters per second?

As we saw in the Classic answer, the surfer's horizontal speed with as a function of time is given by $$\dot{x}(t) = \frac{ 2(1-\cos (3t))}{5 + 4 \cos(3t)},$$ while her horizontal location $$x(t) = \pi \left\lceil \frac{x}{\pi} \right\rceil + \tan^{-1} \left( \frac{\cos (2t) + 2\cos t}{\sin (2t) - 2 \sin t} \right).$$

There are obviously two ways of measuring the average speed: (a) integrate the periodic function $\dot{x}(t)$ over some large time period from $0$ to $T \gg 1;$ or (b) rely on the relationship between distance and average speed to take $\bar{x} = (x(T) - x(0)) / T$ for some large $T \gg 1.$ For kicks, let's do both!

Since $\dot{x}$ is periodic with period $2\pi/3,$ we get that \begin{align*}\bar{x} &= \frac{1}{T} \int_0^T \dot{x}(t)\, dt\\ &=\frac{1}{T} \left( \int_0^{\frac{2\pi}{3} \lfloor 3T/2\pi \rfloor} \dot{x}(t) \,dt + \int_{\frac{2\pi}{3} \lfloor 3T/2\pi \rfloor}^T \dot{x}(t) \,dt \right).\end{align*} Firstly, we see that \begin{align*}I = \int_0^{2\pi/3} \dot{x}(t) \,dt &= 2 \int_0^{\pi/3} \frac{2(1-\cos (3t))}{5 + 4 \cos (3t)} \,dt \\ &= 2\int_0^\infty \frac{ 2 \left( 1 - \frac{1 - s^2}{1+ s^2} \right)}{ 5 + 4 \frac{1-s^2}{1+s^2} } \, \frac{ 2 ds }{ 3 ( 1 + s^2 ) } \\ &= \frac{16}{3} \int_0^\infty \frac{s^2}{(9+s^2)(1+s^2)} \,ds,\end{align*} where we have taken advantage of the powerful and mysterious tangent half-angle substitution $s = \tan \frac{3t}{2},$ where $\cos 3t = \frac{1 - s^2}{1+ s^2}$ and $dt = \frac{2ds}{3(1+s^2)}.$ Using the method of partial fractions we see that $$\frac{16}{3} \frac{s^2}{(9+s^2)(1+s^2)} = \frac{6}{9+s^2} - \frac{2}{3(1+s^2)},$$ and since $\int \frac{du}{a^2+u^2} = \frac{1}{a} \tan^{-1} (u/a) + C,$ so we have \begin{align*}I &= \frac{16}{3} \int_0^\infty \frac{ s^2 }{ (9+s^2) (1+s^2) } \, ds = \int_0^\infty \frac{6}{9+s^2} \,ds - \frac{2}{3} \int_0^\infty \frac{ds}{1+s^2} \\ &= 6 \left[ \frac{1}{3} \tan^{-1} \frac{s}{3} \right]_0^\infty - \frac{2}{3} \left[ \tan^{-1} s \right]_0^\infty \\ &= 2 \left( \frac{\pi}{2} - 0 \right) - \frac{2}{3} \left( \frac{\pi}{2} - 0 \right) \\ &= \frac{2\pi}{3}.\end{align*} We have $$\int_0^{\frac{2\pi}{3} \lfloor 3T/2\pi \rfloor} \dot{x}(t) \,dt = \left\lfloor \frac{3T}{2\pi} \right\rfloor \int_0^{2\pi/3} \dot{x}(t)\,dt = \left\lfloor \frac{3T}{2\pi} \right\rfloor I = \frac{2\pi}{3} \left\lfloor \frac{3T}{2\pi} \right\rfloor.$$ Since we already saw that $0 \leq \dot{x}(t) \leq 4,$ we have \begin{align*}\bar{x} &=\frac{1}{T} \left( \int_0^{\frac{2\pi}{3} \lfloor 3T/2\pi \rfloor} \dot{x}(t) \,dt + \int_{\frac{2\pi}{3} \lfloor 3T/2\pi \rfloor}^T \dot{x}(t) \,dt \right) \\ & \geq \frac{1}{T} \left( \frac{2\pi}{3} \left\lfloor \frac{3T}{2\pi} \right\rfloor + 0 \right) = \frac{2\pi}{3T} \left\lfloor \frac{3T}{2\pi} \right\rfloor =: m(T).\end{align*} Additionally, since $0 \leq T - \left\lfloor \frac{3T}{2\pi} \right\rfloor \frac{2\pi}{3} \leq \frac{2\pi}{3},$ we have $$\bar{x} \leq \frac{1}{T} \left( \frac{2\pi}{3} \left\lfloor \frac{3T}{2\pi} \right\rfloor + 4 \left( T - \left\lfloor \frac{3T}{2\pi} \right\rfloor \frac{2\pi}{3} \right) \right) \leq \frac{2\pi}{3T} \left\lfloor \frac{3T}{2\pi} \right\rfloor + \frac{8\pi}{3T} =: M(T).$$ Since we further have that for any $z \gt 0$ that $1 - \frac{1}{z} \leq \frac{\lfloor z \rfloor}{z} \leq 1,$ we have that $\lim_{T \to \infty} m(T) = \lim_{T \to \infty} M(T) = 1,$ so by the Squeeze Theorem, we have that the surfer's average speed is $\hat{x} = 1$ m/s, as $T \to \infty.$

Alternatively, let's try to directly bound $(x(T) - x(0))/ T$ for large $T \gg 1.$ First, let's look at the behavior of $\dot{x}$ on $[0, 2\pi/3].$ We see that there are two solutions to $\dot{x} = 1,$ namely $t_1 = \frac{2\pi}{9}$ and $t_2 = \frac{4\pi}{9}.$ The tangent lines at $t_1$ and $t_2$ are given by $\dot{x}(t_1) (t-t_1) + x(t_1) = t + \pi/3$ and $\dot{x}(t_2) (t-t_2) + x(t_2) = t + 2\pi/3,$ respectively. Since we can differentiate again to obtain $$\ddot{x}(t) = \frac{54 \sin (3t)}{(5+4\cos(3t))^2},$$ we see that $x(t)$ is concave up from $[0, \pi/3]$ and concave down from $[\pi/3, 2\pi/3].$ Since the concavity of a function determines whether tangent lines lie above or below the curves, we see that we have $t+\pi/3 \leq x(t) \leq t + 2\pi/3,$ at least for $[0, 2\pi/3];$ however, due to the periodicity of $x$, we can extend this result to show that for all $t \geq 0$ we have $$ t + \frac{\pi}{3} \leq x(t) \leq t + \frac{2\pi}{3}.$$ Therefore, we have $$1 - \frac{\pi}{6T} = \frac{ T + \frac{\pi}{3} - \frac{\pi}{2} }{T} \leq \bar{x} = \frac{x(T) - x(0)}{T} \leq \frac{T + \frac{2\pi}{3} - \frac{\pi}{2}}{T} = 1 + \frac{\pi}{6T}.$$ Again, since both the upper and lower bounds converge to $1$, we see that as $T \to \infty,$ the surfers average speed will converge to $1$ m/s.

Surf's Up

A surfer is riding along a crest of a sinusoidal wave given by the function $y = 2·sin(x−t),$ where $y$ is the height above sea level in meters, $x$ is horizontal position in meters, and $t$ is time in seconds. Based on this, the surfer knows that her speed—and the speed of the wave—is $1$ meter per second.

But hold on—it appears that another wave is approaching from the opposite direction. This wave has half the amplitude but twice the speed: $y = sin(x+2t).$

The two waves, the forward and the backward, ”interfere,” meaning they combine. In other words, the height of the water at position $x$ and time $t$ is given by $y = 2·sin(x−t) + sin(x+2t).$ Nevertheless, the surfer stays atop a crest of the combined wave. As the wave moves along, what are the surfer’s slowest and fastest speeds, in meters per second?

Let's assume that at time $t = 0$, that the surfer is perch above the crest of the wave at $x(0)=\frac{\pi}{2},$ with $y(0)=3.$ Since at this point we have $\frac{\partial y}{\partial x}=0,$ for any $t \gt 0,$ we can take the derivative of $y$ with respect to $x$ and solve for $x$ in terms of time $t.$ That is, for any t, we have \begin{align*}\frac{\partial y}{\partial x} &= 2 \cos ( x - t ) + \cos (x + 2t) \\ &= 2 \cos x \cos t + 2 \sin x \sin t + \cos x \cos (2t) - \sin x \sin (2t) \\ &= \left( \cos (2t) + 2 \cos t \right) \cos x - \left( \sin (2t) - 2 \sin t \right) \sin x.\end{align*} So by setting $\frac{\partial y}{\partial x} = 0,$ we get $$\tan x = \frac{ \cos (2t) + 2\cos t }{ \sin (2t) - 2\sin t }.$$ One way to solve this equation is to set $$x(t) = \tan^{-1} \left( \frac{ \cos (2t) + 2\cos t }{ \sin (2t) - 2\sin t } \right);$$ however, this will have a bunch of nasty jump discontinuities that likely would be fairly gnarly for the surfer to deal with. Instead, let's resolve this by ensuring that $x(t)$ is a nondecreasing, continuous function of $t,$ which would lead us to $$x(t) = \pi \left\lceil \frac{t}{\pi} \right\rceil + \tan^{-1} \left( \frac{\cos (2t) + 2\cos t }{ \sin (2t) - 2\sin t } \right).$$

Since we want to compute the surfer's horizontal speed at various times, we can ignore the almost everywhere constant initial term, $\pi \lceil t/\pi \rceil,$ and calculate \begin{align*}\dot{x}(t) = \frac{d}{dt} x(t) &= \frac{1}{1 + \left( \frac{\cos (2t) + 2 \cos t }{\sin (2t) - 2 \sin t} \right)^2} \frac{d}{dt} \left( \frac{ \cos (2t) + 2\cos t}{\sin (2t) - 2\sin t} \right).\end{align*} We first see that \begin{align*}\frac{d}{dt} \left( \frac{\cos (2t) + 2\cos t}{\sin (2t) - 2\sin t} \right) &= \frac{ (\sin (2t) - 2\sin t) (-2\sin (2t) - 2\sin t) - (\cos (2t) + 2\cos t) (2\cos (2t) - 2 \cos t)}{ (\sin(2t) - 2 \sin t)^2} \\ &= \frac{ -2 \sin^2 (2t) + 2 \sin t \sin (2t) + 4 \sin^2 t - 2 \cos^2 (2t) - 2 \cos t \cos (2t) + 4 \cos^2 (2t)}{ (\sin (2t) - 2 \sin t)^2} \\ &= \frac{ -2 - 2 \left( \cos t \cos (2t) - \sin t \sin (2t) \right) + 4 }{ (\sin (2t) - 2 \sin t)^2} \\ &= \frac{ 2( 1 - \cos (3t))}{ (\sin (2t) - 2 \sin t)^2}. \end{align*} Secondly, we see that \begin{align*}\frac{1}{1 + \left( \frac{ \cos (2t) + 2 \cos t }{ \sin (2t) - 2 \sin t } \right)^2} &= \frac{ (\sin (2t) - 2 \sin t)^2}{ (\sin (2t) - 2 \sin t)^2 + (\cos (2t) - 2 \cos t)^2 } \\ &= \frac{ (\sin (2t) - 2 \sin t)^2}{ \sin^2 (2t) - 4 \sin t \sin (2t) + 4 \sin^2 t + \cos^2 (2t) + 4 \cos t \cos (2t) + 4 \cos^2 t} \\ &= \frac{( \sin (2t) - 2 \sin t)^2}{ 1 + 4 \left( \cos t \cos (2t) - \sin t \sin (2t) \right) + 4 } \\ &= \frac{ (\sin (2t) - 2 \sin t)^2}{ 5 + 4 \cos (3t)}.\end{align*} Therefore, putting everything together we get $$\dot{x}(t) = \frac{ (\sin (2t) - 2 \sin t)^2 }{ 5 + 4 \cos (3t)} \frac{ 2 ( 1 - \cos (3t) )}{ (\sin (2t) - 2 \sin t)^2} = \frac{ 2(1 - \cos (3t))}{ 5 + 4 \cos (3t) }.$$

Ok, so far so good for our surfer. We see that since $5 + 4 \cos (3t) \geq 1$ for all $t \leq 0,$ that the denominator of her speed is always well defined. Furthermore, we see that if we define $$f(s) = \frac{ 2(1-s) }{5 + 4s}$$ then we have $$f'(s) = \frac{-18}{(5+4s)^2} \leq 0$$ for all $s \in \mathbb{R},$ so $f$ is a monotone decreasing function of $s.$ Therefore, in particular, since $-1 \leq \cos (3t) \leq 1$ for all $t \geq 0,$ we see that if $-1 \leq s = \cos (3t) \leq 1,$ then we have $$0 =\frac{ 2 ( 1 - 1 )}{ 5 + 4 \cdot 1} = \dot{x} \left( \frac{1}{3} \cos^{-1} 1 \right) \leq \dot{x} (t) \leq \dot{x} \left( \frac{1}{3} \cos^{-1} (-1) \right) = \frac{ 2(1 - (-1))}{ 5 + 4 \cdot -1} = 4.$$ So the surfer's slowest and fastest speeds in meters per second are 0 and 4, respectively.

Just keep swimming, normally ...

Another pond that’s also long and straight contains many, many koi. Initially, they’re all placed at the center of the pond, after which they all swim off at random velocities chosen from a normal distribution with a mean of 0 and a standard deviation of 1 mile per hour. A fish with a positive velocity initially swims toward one end of the pond, while a fish with a negative velocity initially swims toward the other end. The fish then swim back and forth, over and over again.

As before, you place a sensor in the water that measures the speed of each passing fish. All speeds are recorded as positive; direction no longer matters. You collect many such measurements over the course of several days, after which you read out the data and compute the average speed the sensor detected. Toward what value will this average speed converge?

As we saw in the Classic problem, with the added caveat that the sensor will pick up absolute speed, rather than signed velocities, if we have $v_i \sim \mathcal{N}(0,1),$ $i = 1, \dots, n,$ then we have $$\hat{v}_n = \frac{\sum_{i=1}^n v_i^2}{\sum_{i=1}^n |v_i|}.$$ Since we have many fish, let's define break the numerator and denominator up and try to use the Central Limit Theorem to understand what will happen in this case.

Let's define $A_n = \sum_{i=1}^n v_i^2$ and $B_n = \sum_{i=1}^n |v_i|.$ Let's first establish the prerequisites for the CLT. Firstly we see that for each $i = 1, \dots, n,$ we have $$\mathbb{E} |v_i| = 2 \int_0^\infty v \frac{e^{-v^2/2}}{\sqrt{2\pi}} \,dv = \sqrt{\frac{2}{\pi}} \left[ - e^{-v^2/2} \right]_{v=0}^{v=\infty} = \sqrt{\frac{2}{\pi}} \lt \infty,$$ and since each $v_i \sim \mathcal{N}(0,1)$ we have $$\mathbb{E} v_i^2 = 1.$$ Further we have $$var(|v_i|) = \mathbb{E} \left( |v_i| - \sqrt{\frac{2}{\pi}} \right)^2 = \mathbb{E} v_i^2 - 2\sqrt{\frac{2}{\pi}} \mathbb{E} |v_i| + \left( \sqrt{\frac{2}{\pi}} \right)^2 = 1 - \frac{2}{\pi} \lt \infty$$ and $$var(v_i^2) = \mathbb{E} \left( v_i^2 - 1 \right)^2 = \mathbb{E} v_i^4 - 2 \mathbb{E} v_i^2 + 1 = 3 - 2 + 1 = 2 \lt \infty.$$ Therefore, we see from the CLT, that $A_n \to \mathcal{N} (n, 2n)$ and $B_n \to \mathcal{N} ( n\sqrt{\frac{2}{\pi}}, n(1- \frac{2}{\pi}) ),$ uniformly in distribution. In particular, since we have each $v_i$ is independent we have $$\mathbb{E} \left[ v_i^2 |v_j| \right] = \mathbb{E} \left[ v_i^2 \right] \mathbb{E} |v_j| = \sqrt{\frac{2}{\pi}}$$ if $i \ne j$ and \begin{align*}\mathbb{E} |v_i|^3 &= 2 \int_0^\infty v^3 \frac{e^{-v^2/2}}{\sqrt{2\pi}} \,dv\\ &= \sqrt{\frac{2}{\pi}} \left[ \left( -v^2e^{-v^2/2} \right)_{v=0}^{v=\infty} + 2\int_0^\infty ve^{-v^2/2} \,dv \right]\\ &= 2 \sqrt{\frac{2}{\pi}},\end{align*} so we further see that \begin{align*}corr(A_n, B_n) &= \mathbb{E} \left[ \left( \frac{A_n - n}{\sqrt{2n}} \right) \left( \frac{B_n - n \sqrt{\frac{2}{\pi}}}{\sqrt{n(1 - \frac{2}{\pi})}} \right) \right]\\ &= \frac{\sqrt{\pi}}{n\sqrt{2(\pi-2)}} \mathbb{E} \left[ \sum_{i=1}^n \sum_{j=1}^n v_i^2 |v_j| - n \sqrt{\frac{2}{\pi}} \sum_{i=1}^n v_i^2 - n \sum_{j=1}^n |v_j| + n^2 \sqrt{\frac{2}{\pi}} \right] \\ &= \frac{\sqrt{\pi}}{n \sqrt{2(\pi-2)}} \left( n \left(2 \sqrt{\frac{2}{\pi}} \right) + (n^2 - n) \sqrt{\frac{2}{\pi}} - n^2 \sqrt{\frac{2}{\pi}} \right) \\ &= \frac{\sqrt{\pi}}{ n \sqrt{2(\pi -2)}} \left( n \sqrt{\frac{2}{\pi}} \right) = \frac{1}{\sqrt{\pi - 2}}.\end{align*} So in particular, if we define $Z_A, Z_B \sim \mathcal{N}(0,1)$ with $\mathbb{E} Z_AZ_B = \frac{1}{\sqrt{\pi-2}},$ then we can define $A_n = n + \sqrt{2n} Z_A$ and $B_n = n\sqrt{\frac{2}{\pi}} + \sqrt{n (1 - \frac{2}{\pi})} Z_B.$

Let's define use the properties of the natural logarithm to see if we can discern the distribution of $\hat{v}_n = A_n / B_n.$ We see that \begin{align*}\ln \hat{v} = \ln \left(\frac{A_n}{B_n}\right) &= \ln \left( \frac{ n + \sqrt{2n} Z_A }{ n\sqrt{\frac{2}{\pi}} + \sqrt{ n(1-\frac{2}{\pi})} Z_B } \right) \\ &= \ln \left( \frac{n}{n \sqrt{\frac{2}{\pi}}} \frac{1 + \sqrt{\frac{2}{n}} Z_A}{1 + \sqrt{ \frac{\pi -2}{2n} } Z_B } \right)\\ &= \ln \sqrt{\frac{\pi}{2}} + \ln \left( 1 + \sqrt{\frac{2}{n}} Z_A \right) - \ln \left( 1 + \sqrt{\frac{ \pi - 2 }{ 2n} } Z_B \right) \\ & \approx \ln \sqrt{\frac{\pi}{2}} + \sqrt{\frac{2}{n}} Z_A - \sqrt{\frac{\pi-2}{2n}} Z_B,\end{align*} where we take advantage of the Taylor approximation $\ln (1+t) = t + O(t^2).$ Let's define $\tilde{Z} = \sqrt{\frac{2}{n}} Z_A - \sqrt{\frac{\pi-2}{2n}} Z_B \sim \mathbb{N}(0,\nu^2),$ where we can calculate \begin{align*}\nu^2 &= \left( \sqrt{\frac{2}{n}} \right)^2 + \left( \frac{\pi - 2}{2n} \right)^2 - 2 \left( \sqrt{\frac{2}{n}} \right) \left( \sqrt{\frac{\pi-2}{2n}} \right) \mathbb{E} Z_AZ_B \\&= \frac{2}{n} + \frac{\pi-2}{2n} - 2 \sqrt{ \frac{2}{n} \frac{\pi - 2}{2n} \frac{1}{\pi - 2} } = \frac{\pi-2}{2n}.\end{align*} Therefore, we see that $\hat{v}$ is approximately log-normally distributed as $\hat{v} \sim \text{Log}\mathcal{N} (\mu, \sigma^2)$ with parameters $\mu = \ln \sqrt{\frac{\pi}{2}}$ and $\sigma^2 = \frac{\pi-2}{2n}.$ From here we see that if there are many fish with normally distribution signed velocities, then the average speed recorded by our sensor will converge to $$\lim_{n\to \infty} \mathbb{E} \hat{v}_n = \lim_{n\to \infty} \exp \left( \ln \sqrt{\frac{\pi}{2}} + \frac{1}{2} \left( \frac{\pi-2}{2n} \right) \right) = \lim_{n\to\infty} \sqrt{\frac{\pi}{2}} \exp \left( \frac{\pi - 2}{4n} \right) = \sqrt{\frac{\pi}{2}}.$$

Just keep swimming ....

Two koi, Nemo and Dory, live in a pond that’s long and straight. All day long, they swim back and forth, over and over again. Nemo supposedly swims at a speed of exactly 1 mile per hour, while Dory swims faster at 2 miles per hour. That said, you design an experiment to measure their speeds.

You place a sensor in the water that measures the speed of any passing fish and records the event in a log. You collect many such measurements over the course of several days, after which you read out the data and compute the average speed of all the events in the log. If indeed the fish’s speeds were 1 and 2 miles per hour, what average should you expect to get?

Let's assume that the pond has a length of $\ell$ miles. No matter where Nemo and Dory start within the pond or where the sensor is, we know that if the fish's speeds really where 1 and 2 miles per hour, respectively, then after $T = 2 \ell$ hours, then Nemo would pass the sensor exactly twice while Dory would pass the sensor exactly four times. Therefore, the sensor's log would read something like $[ 2, 1, 2, 2, 1, 2 ],$ or any of the other 30 orderings, and thus the average fish speed would be $\frac{ 4 \cdot 2 + 2 \cdot 1 }{4 + 2} = \frac{5}{3}.$

But wait, you say, what if $T$ is not a multiple of $2 \ell$? Let's define the $N_n(T)$ and $N_d(T)$ as the number of times that the sensor picks up Nemo and Demo, respectively. Though obviously counting statistics are defined only on the integers, we see that we should have roughly $$N_n(T) \approx \frac{T}{\ell} \,\, \text{and} \,\, N_d(T) \approx \frac{2T}{\ell}.$$ Therefore, we again arrive at the fact that the average speed recorded by our sensor will be $$\hat{v} = \frac{ 1 \cdot N_n(T) + 2 \cdot N_d(T) }{N_n(T) + N_d(T)} \approx \frac{\frac{T}{\ell} + \frac{4T}{\ell}}{ \frac{T}{\ell} + \frac{2T}{\ell}} = \frac{5}{3}.$$

In general, we see that for any speeds $v_n$ and $v_d,$ that the average speed recorded would be $\hat{v}= \frac{v_n^2 + v_d^2}{v_n + v_d}.$

Triangular Frame Job

Congratulations—you just won your school’s tabletop football championship! You flicked your lucky paper football to victory countless times, and would now like to frame it for posterity. The football is an equilateral triangle with a side length of 1 inch. What is the side length of the smallest square frame that will contain the football?

For this week's Fiddler, let's just skip to the Extra Credit problem where we answer the general question and from which we can infer the answer to the Classic problem, so ...

To add a little excitement to the framing process, your new plan is to spin the triangular football by a random angle, and then frame it with a square that is not rotated. That is, the square consists of two perfectly horizontal sides and two perfectly vertical sides. On average, what can you expect the side length of the smallest resulting square frame to be?

Let's choose how to parameterize everything. Let's assume that one of the corners of our paper football is fixed at the origin, and that for any $\theta \in [0, 2\pi/3],$ that the other two corners are at $$p_1(\theta) = (\cos \theta, \sin \theta)$$ and $$p_2(\theta) = \left(\cos \left(\theta + \frac{\pi}{3}\right), \sin \left(\theta + \frac{\pi}{3} \right) \right).$$

In order to choose the smallest possible square with two sides parallel to the $x$-axis and two sides parallel to the $y$-axis, we need only determine the maximum horizontal and vertical distances between the three corners. Since \begin{align*}\cos \theta - \cos \left( \theta + \frac{\pi}{3} \right) & = \cos \theta - \left( \frac{1}{2} \cos \theta - \frac{\sqrt{3}}{2} \sin \theta \right) \\ & = \frac{1}{2} \cos \theta + \frac{\sqrt{3}}{2} \sin \theta \\ & = \sin \left( \theta + \frac{\pi}{6} \right),\end{align*} we see that the maximum horizontal distance between the corners is \begin{align*}h(\theta) &= \max \left\{ \left|\cos \theta\right|, \left| \cos \left(\theta + \frac{\pi}{3} \right)\right|, \left| \cos \theta - \cos \left( \theta + \frac{\pi}{3} \right) \right| \right\}\\ & = \begin{cases} \cos \theta, &\text{for $0 \leq \theta \leq \pi/6;$}\\ \sin \left( \theta + \frac{\pi}{6} \right), &\text{for $\pi/6 \leq \theta \leq \pi/2$;}\\ -\cos \left( \theta + \frac{\pi}{3} \right), &\text{for $\pi/2 \leq \theta \leq 2\pi/3.$}\end{cases}\end{align*} Meanwhile, since \begin{align*}sin(\theta) - \sin\left(\theta + \frac{\pi}{3} \right) & = \sin \theta - \left( \frac{1}{2} \sin \theta + \frac{\sqrt{3}}{2} \cos \theta \right) \\ &= -\frac{\sqrt{3}}{2} \cos \theta + \frac{1}{2} \sin \theta \\ &= \sin \left( \theta - \frac{\pi}{3} \right)\end{align*} and because $$\left| \sin \left( \theta - \frac{\pi}{3} \right) \right| \leq \max \left\{ \sin \left( \theta + \frac{\pi}{3} \right), \sin \theta \right\},$$ for all $\theta \in [0, 2\pi/3],$ the maximum vertical distance between the corners is \begin{align*} v(\theta) &= \max \left\{ \left|\sin \theta\right|, \left| \sin \left( \theta + \frac{\pi}{3} \right)\right|, \left| \sin \theta - \sin \left( \theta + \frac{\pi}{3} \right) \right| \right\} \\ &= \begin{cases} \sin \left( \theta + \frac{\pi}{3} \right), &\text{ for $0 \leq \theta \leq \pi/3;$} \\ \sin \theta, &\text{ for $\pi/3 \leq \theta \leq 2\pi/3.$}\end{cases}\end{align*} Since the side length should be the maximum of the vertical and horizontal distances we have $$s(\theta) = \max \{ h(\theta), v(\theta) \} = \begin{cases} \cos \theta, &\text{for $0 \leq \theta \leq \pi/12;$} \\ \sin \left(\theta + \frac{\pi}{3} \right), &\text{for $\pi/12 \leq \theta \leq \pi/4;$}\\ \sin \left( \theta + \frac{\pi}{6} \right), &\text{for $\pi/4 \leq \theta \leq 5\pi/12;$} \\ \sin \theta, &\text{for $5\pi/12 \leq \theta \leq 7\pi/12;$} \\ -\cos \left( \theta + \frac{\pi}{3} \right), &\text{for $7\pi/12 \leq \theta \leq 2\pi/3.$}\end{cases}$$

Therefore, we see that for the Classic problem we want the minimal sidelength under any orientation, which is $$s^* = \min_{\theta \in [0, 2\pi/3]} s(\theta) = \cos \frac{\pi}{12} = \frac{\sqrt{2 + \sqrt{3}}}{2} \approx 0.965925826289\dots$$ Furthermore, we notice that, by symmetry, the average sidelength over any possible orientation is \begin{align*}\bar{s} &= \frac{3}{2\pi} \int_0^{2\pi/3} s(\theta) \,d\theta\\ &= \frac{12}{\pi} \int_0^{\pi/12} \cos \theta \,d\theta\\ &= \frac{12}{\pi} \sin \frac{\pi}{12} = \frac{6}{\pi} \sqrt{ 2 - \sqrt{3} } \approx 0.988615929465\dots.\end{align*}