Smart Cats Have 25 Fifes, .... in Expectation

You’re a contestant on the hit new game show, “You Bet Your Fife.” On the show, a random real number (i.e., decimals are allowed) is chosen between $0$ and $100.$ Your job is to guess a value that is less than this randomly chosen number. Your reward for winning is a novelty fife that is valued precisely at your guess.

What number should you guess to maximize the average value of your fifing winnings?

If you guess $x \in [0,100],$ then the payoff function in terms of $x$ and the randomly selected $Y \sim U(0,100)$ is $$v(x|Y) = \begin{cases} x, &\text{if $Y > x$;}\\ 0, &\text{if $Y \leq x.$}\end{cases}$$ So in expectation, we have $$V(x) = \mathbb{E}_Y[v(x|Y)] = x \mathbb{P}[ Y > x ] + 0 \mathbb{P}[ Y \leq x ] = x \left(1-\frac{x}{100}\right).$$

Since $V(x)$ is continuously differentiable and concave, it is maximized exactly at $\hat{x}$ which solves $$V^\prime(\hat{x}) = 1 - \frac{\hat{x}}{50} = 0.$$ That is, the optimal solution is to choose $\hat{x} = 50,$ at which point $$V(\hat{x}) = 50 \left( 1 - \frac{50}{100} \right) = 25.$$

Marian's Olde Archer-e Game

Marian proposes two similar archery-based games for her true love, Dame Robin of Foxely, who has the peculiar ability to uniformly distribute the landing spot of her arrows along a circular target. Dame Robin will score a point in the archery game for each arrow shot, but must stop once one lands ``further away'' from the center of the target. In the main version of the game, the distance from the center is measured using Euclidean distance, whereas in the variant the circular target is discretized into 10 equally-spaced concentric bands and Dame Robin must cease volleying arrows once an arrow lands in the same or a wider band.

On average, what score can Dame Robin expect to achieve in this archery game?

Let's first tackle the main version of the game and then see how the discretized version compares. Let $S$ be Dame Foxely's score, which is synonymous with the total number of arrows shot. Since Marian's game seems to completely ignore the bearing of the arrows, focusing only on the relative distance of successive arrows from the center of the target, we will focus on the radial distribution of Dame Foxely's arrows.

For the main version of the game, we will try to calculate the probability that $S = k$, that is, the probability that $k$ is the last arrow shot. In particular, assume that the distances from the center of the target for Dame Foxely's $k$ arrows are $r_1, \dots, r_k.$ The event $\{S = k\}$ is equal to the event $\{ r_1 > r_2 > \cdots > r_{k-1}, r_k \geq r_{k-1} \}.$ There are several ways to conclude that $\mathbb{P}[S = k] = \frac{(k-1)}{k!},$ and we will highlight two:

1. Direct calculus approach:

Given that Dame Foxely arrows fall uniformly over the circular target, the radial distribution is $f_r(\rho) = 2\rho,$ for $\rho \in [0,1]$ and $0$ elsewhere. So \begin{align*}\mathbb{P}[S = k] &= \mathbb{P}\left[ r_1 > r_2 > \cdots > r_{k-1}, r_k \geq r_{k-1} \right]\\ &= \int_0^1 \int_0^{r_1} \int_0^{r_2} \cdots \int_0^{r_{k-2}} \int_{r_{k-1}}^1 2^k r_1 r_2 \cdots r_k \, dr_k \, dr_{k-1} \cdots \,dr_2 \, dr_1.\end{align*}

The iterated integral lends itself to a recursive solution. Define the sequense of polynomials $p_i(t) = a_i (t^2)^{i-1} - b_i (t^2)^i$ with recursion relation $$p_{i+1}(t)= \int_0^t 2s p_i(s) \, ds$$ and initial value $p_1(t) = 1 - t^2,$ that is $a_1 = b_1 = 1.$ Since the innermost integral in the formula for the probability is given by $p_1(r_{k-1}) = \int_{r_{k-1}}^1 2r_k \, dr_k = 1 - r_{k-1}^2,$ by taking the repeated integrals, we see that $\mathbb{P}[S = k] = p_k(1).$

We need to find $a_k$ and $b_k$ by translating the polynomial recursion relation into the relation for the $a_i$ and $b_i$ sequences. Since $$p_{i+1}(t) = \int_0^t 2s p_i(s) \,ds = \int_0^t 2s \left(a_i (s^2)^{i-1} - b_i (s^2)^i \right) \, ds = \frac{a_i}{i} (t^2)^i - \frac{b_i}{i+1} (t^2)^{i+1},$$ we have the recurrence relations $$a_{i+1} = \frac{a_i}{i} \,\, \text{and} \,\, b_{i+1} = \frac{b_i}{i+1}.$$ Given that $a_1 = b_1 = 1,$ we see that $$p_k(t) = \frac{1}{(k-1)!} (t^2)^{k-1} - \frac{1}{k!} t^{2k},$$ so as desired $$\mathbb{P}[S = k] = p_k(1) = \frac{1}{(k-1)!} - \frac{1}{k!} = \frac{k - 1}{k!}.$$

2. Combinatorial approach:

An integral-free combinatorial approach can be used as well (once we use exclude the measure zero event of two arrows having the same exact distance to the origin). There are $k!$ possible orderings of $k$ values $r_1, \dots, r_k \in [0,1].$ Since these values are distinct there is exactly one ordering in decreasing order $1 \geq r_1 > r_2 > r_3 > \cdots > r_{k-1} > r_k.$ If instead there we want $r_k \geq r_{k-1},$ there are $k-1$ possible places to insert $r_k$. So there are $k-1$ possible orders where $r_1 > r_2 > \cdots > r_{k-1}$ and $r_k \geq r_{k-1}.$ The probability is thus the number of desired orderings over the total possible number of orderings, that is $\mathbb{P}[S = k] = (k-1) / k!.$

Having established that $\mathbb{P}[S = k] = \frac{(k-1)}{k!},$ the expected score is simply calculated as $$\mathbb{E}[S] = \sum_{k=2}^\infty \frac{(k-1)}{k!} \cdot k = \sum_{k=2}^\infty \frac{1}{(k-2)!} = e \approx 2.718281828....$$

Discretized variant

Now that Marian's main game is handled, let's investigate here Firstly, it is clear that discretized version is a lower bound approximation of the main game, as there are clearly shots that might allow Dame Robin to continue shooting in the main game but would land in the same concentric circle thus ending her run in the variant. Further, if we allow the number of concentric bands $N$ to vary and $\mathbb{E}[S_N]$ is the expected score with $N$ discrete bands, then $\mathbb{E}[S_N] \nearrow \mathbb{E}[S] = e,$ as $N \to \infty.$

Fix some $N > 1$ as the number of discrete bands on the target. Let $B_k$ be the $k$th band (out of $N$ bands), which encompasses the entire area between the $(k-1)$th and $k$th concentric circle. Then the probability of an arrow landing in the $k$th band is $$p_k = \mathbb{P}[ A \in B_k ] = \frac{k^2 - (k-1)^2}{N^2} = \frac{2k-1}{N^2}.$$

For any $i = 1, \dots, k,$ let $e_i = \mathbb{E}[ S_N \mid A_1 \in B_i ]$ be the conditional expectation of the score given that the first arrow landed in the $i$th band. For $i=1,$ since no matter what the 2nd arrow will land in band $B_{i_2}$ where $i_2 \geq 1,$ we have $e_1 = \mathbb{E}[ S_N \mid A_1 \in B_1 ] = 2.$

Assume that instead for some $i > 1,$ we have $A_1 \in B_i.$ There are then $i$ distinct possible outcomes for where arrow 2 lands: $A_2 \in B_k$ for $k = 1, \dots, i-1$ or $A_2 \in \bigcup_{k=i}^N B_k.$ The last case results in a score of 2, while for each of the former cases, the conditional expectation is $\mathbb{E}[S_N \mid A_2 \in B_k].$ So from the law of total probability, we get $$e_i = 2 \sum_{k=i}^N p_k + \sum_{k=1}^{i-1} p_k \mathbb{E}[S_N \mid A_2 \in B_k].$$ The only difference between the game play conditional on $\{A_1 \in B_k\}$ for some $k = 1, \dots, i-1$ and the game play condition on $\{A_2 \in B_k\}$ is that the score will be incremented by $1$ for the latter scenario. That is, $$\mathbb{E}[ S_N \mid A_2 \in B_k ] = 1 + \mathbb{E}[ S_N \mid A_1 \in B_k ] = 1 + e_k,$$ so we have \begin{align*}e_i &= 2 \sum_{k=i}^N p_k + \sum_{k=1}^{i-1} p_k (1 + e_k)\\ &= 2 \left( 1 - \sum_{k=1}^{i-1} p_k \right) + \sum_{k=1}^{i-1} p_k (1 + e_k)\\ &= 2 + \sum_{k=1}^{i-1} p_k (e_k - 1).\end{align*} Since this formula holds for all $i > 1,$ if $i > 2,$ then we have \begin{align*}e_i = 2 + \sum_{k=1}^{i-1} p_k (e_k - 1) &= \left(2 + \sum_{k=1}^{i-2} p_k (e_k - 1)\right) + p_{i-1} (e_{i-1} - 1)\\ &= e_{i-1} + p_{i-1} (e_{i-1} - 1)\\ &= (1 + p_{i-1}) e_{i-1} - p_{i-1}.\end{align*}

Note that $e_2 = 2 + p_1 = 1 + (1+p_1).$ Assume that $e_i = 1 + \prod_{k=1}^{i-1} (1+p_k)$ for some $i > 1.$ Then by applying the above formula we get that $$e_{i+1} = (1 + p_i) e_i - p_i = (1 + p_i) \left(1 + \prod_{k=1}^{i-1} (1 + p_k)\right) - p_i = 1 + \prod_{k=1}^i (1+p_i),$$ so by induction we have $e_1 = 2$ and $$e_i = 1 + \prod_{k=1}^{i-1} (1+p_k),$$ for all $i = 2, \dots, N.$

From here, we get \begin{align*}\mathbb{E}[S_N] = \sum_{k=1}^N p_ke_k &= 2p_1 + \sum_{k=2}^N p_k \left(1 + \prod_{j=1}^{k-1} (1 + p_j) \right) \\ &=\sum_{k=1}^N p_k + p_1 + \sum_{k=2}^N p_k \prod_{j=1}^{k-1} (1 + p_j)\\ &= 1 + p_1 + \sum_{k=2}^N p_k \prod_{j=1}^{k-1} (1 + p_j)\\ &= (1 + p_1) \left(1 + p_2 + \sum_{k=3}^N p_k \prod_{j=2}^{k-1} (1+p_j) \right) \\ &= (1 + p_1) (1 + p_2) \left( 1 + p_3 + \sum_{k=4}^N p_k \prod_{j=3}^{k-1} (1 + p_j) \right) \\ &= \cdots = (1 + p_1) (1 + p_2) \cdots (1 + p_{N-2}) \left( 1 + p_{N-1} + p_N (1 + p_{N-1}) \right) \\ &= \prod_{k=1}^N \left(1 + \frac{2k-1}{N^2}\right).\end{align*} Note that for $N = 10,$ we get $$\mathbb{E}[S_{10}] = \prod_{k=1}^{10} \left(1 + \frac{2k-1}{100}\right) \approx 2.150024....$$ For any $N,$ we have $$\mathbb{E}[S_N] = \prod_{k=1}^N \left(1 + \frac{2k-1}{N^2}\right) \leq \exp \left( \sum_{k=1}^N \frac{2k-1}{N^2} \right) = \exp(1) = e,$$ since $\ln(1+x) \leq x.$ Furthermore, since $x - \frac{1}{2} x^2 \leq \ln (1 + x),$ we additionally have \begin{align*}\mathbb{E}[S_N] &\geq \exp \left( \sum_{k=1}^N \frac{2k-1}{N^2} -\frac{1}{2} \sum_{k=1}^N \left( \frac{2k-1}{N^2} \right)^2 \right)\\ &= \exp \left( 1 - \frac{1}{2N^4} \frac{N(2N-1)(2N+1)}{3} \right) \\ &= \exp \left( 1 - \frac{2}{3N} + \frac{1}{6N^3} \right).\end{align*} From the squeeze theorem, then we see what we expected that as $N \to \infty,$ the discretized game approaches the continuous limit $$\lim_{N \to \infty} \mathbb{E}[S_N] = e.$$

Can't cut squares from here (in the thickest Mainer accent imaginable)

Consider a generic square. It can be subdivided into smaller sub-squares, not necessarily of equal size so that the smaller squares do not overlap. For example, you can slice the big square into four smaller squares, each a quarter of the area of the big square. Or you could slice it into seven squares, if you take one of those four squares and slice it into four yet smaller squares.

What whole numbers of squares can you not slice the big square into?

Let $S$ be the set of whole numbers $n \in \mathbb{N},$ where the original big square can be partitioned into $n$ not necessarily equally sized smaller squares. The problem setup provides a hint that shows that for any $n \in S,$ by taking any single smaller square and dividing it equally into $4$ even smaller squares, we end up with $n + 3$ subsquares, so $n \in S \Rightarrow n+3 \in S.$ So in particular, since $1 \in S$ (just the original square with no further cuts), we have $(3\mathbb{N} + 1) \subset S.$

However, we needn't focus solely on subdividing into $4$ equally sized sub-squares. For instance for any $k \in \mathbb{N}$ we can subdivide into $k^2$ equally sized sub-squares by equally dividing the length and width of the original square into $k$ segments and forming a $k$ by $k$ grid of subsquares. In this case, for any $n \in S,$ we can take any sub-square and replace it with $k^2$ smaller sub-squares, getting $n + k^2 - 1$ total sub=squares. In particular, for $k = 3,$ we get $(8 \mathbb{N} + 1) \subset S,$ which implies that for instance $9 \in S$ and $17 \in S.$

Since $9 \equiv 0 \mod 3,$ by further subdividing squares into equal quarter squares, we get that any multiple of $3$ greater than or equal to $9$ is included in $S.$ That is, $(3 \mathbb{N} \setminus \{0,3,6\} ) \subset S.$ Similarly, since $17 \equiv 2 \mod 3,$ we get that $((3 \mathbb{N} + 2) \setminus \{2, 5, 8, 11, 14\}) \subset S.$ So since all remainders with respect to $3$ are covered for large enough values, we see that \begin{align*}S &= (3 \mathbb{N} + 1) \cup (3 \mathbb{N} \setminus \{0, 3, 6\}) \cup ((3 \mathbb{N} + 2) \setminus \{2, 5, 8, 11, 14\})\\ &= \mathbb{N} \setminus \{2, 3, 5, 6, 8, 11, 14\}.\end{align*}

Thus the complement of $S$ is given by $S^C = \{2, 3, 5, 6, 8, 11, 14\}.$

Attrition by subtraction

The Game of Attrition works by players successively subtracting their own remaining number of points from their opponents points until one player is left with a nonpositive point total. Assume player A has $N$ points to begin the game and always goes first against his opponent B.

What is the largest point total that B can start with such that A will still win?

Let's say that B has initial points of $P > N,$ since obviously if $P \leq N,$ then A will win in the first move. After one round of both A and B's moves, A will have $2N-P$ points remaining and B will have $P-N,$ both of which are binomials in terms of $N$ and $P.$

Let $A_n$ and $B_n$ be the point total for A and B, respectively after $n$ full turns. One full turn of gameplay gives the following recurrence:

\begin{align*} A_{n+1} &= 2 A_n - B_n \\ B_{n+1} &= B_n - A_n \\ A_0 = N, \,\,&\,\, B_0 = P\end{align*}

If we assume, as after the first turn, that both $A_n$ and $B_n$ are binomials in terms of $N$ and $P$, say $A_n = a_n N + b_n P$ and $B_n = c_n N + d_n P,$ then the above recurrence becomes \begin{align*} a_{n+1} &= 2 a_n - c_n \\ b_{n+1} &= 2 b_n - d_n \\ c_{n+1} &= c_n - a_n \\ d_{n+1} &= d_n - b_n \\ a_0 = d_0 = 1, \,\,&\,\, b_0 = c_0 = 0 \end{align*} We note that player $A$ will win after $n$ steps if $B_n \leq 0,$ or equivalently, if $$P \leq -\frac{c_n}{d_n} N.$$ The largest possible point total that B can start with such that A will still win is thus $$\sup \left\{ -\frac{c_n}{d_n}N : n \in \mathbb{N} \right\}.$$

Letting $x_n = (a_n, b_n, c_n, d_n)^T,$ and $$M =\left(\begin{array}{cccc} 2 & 0 & -1 & 0 \\ 0 & 2 & 0 & -1 \\ -1 & 0 & 1 & 0 \\ 0 & -1 & 0 & 1 \end{array}\right),$$ we can express the reccurence more compactly in matrix notation as: $$x_n = Mx_{n-1} = \cdots = M^n x_0,$$ where $x_0 = (1, 0, 0, 1)^T.$ The matrix $M$ has eigenvalues $\lambda_\pm = \frac{3 \pm \sqrt{5}}{2},$ each of order $2,$ associated with eigenvectors $$u_\pm = \sqrt{\frac{2}{5\mp \sqrt{5}}}\left( \begin{array}{c} 1 \\ 0 \\ \frac{1 \mp \sqrt{5}}{2} \\ 0\end{array} \right) \,\,\, \text{and} \,\,\, v_\pm = \sqrt{\frac{2}{5\mp \sqrt{5}}} \left( \begin{array}{c} 0 \\ 1 \\ 0 \\ \frac{1 \mp \sqrt{5}}{2}\end{array} \right).$$ So let's define $$L = \left(\begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ -\frac{\sqrt{5}-1}{2} & 0 & \frac{\sqrt{5} + 1}{2} & 0 \\ 0 & -\frac{\sqrt{5}-1}{2} & 0 & \frac{\sqrt{5} + 1}{2}\end{array}\right),$$ $$D = \left(\begin{array}{cccc} \frac{5-\sqrt{5}}{2} & 0 & 0 & 0 \\ 0 & \frac{5 - \sqrt{5}}{2} & 0 & 0 \\ 0 & 0 & \frac{5 + \sqrt{5}}{2} & 0 \\ 0 & 0 & 0 & \frac{5 + \sqrt{5}}{2}\end{array}\right) = L^TL$$ and $$\Lambda = \left(\begin{array}{cccc} \frac{3+\sqrt{5}}{2} & 0 & 0 & 0 \\ 0 & \frac{3+\sqrt{5}}{2} & 0 & 0 \\ 0 & 0 & \frac{3-\sqrt{5}}{2} & 0 \\ 0 & 0 & 0 & \frac{3-\sqrt{5}}{2}\end{array}\right).$$ Then the eigendecomposition of $M$ can be given by $M = Q \Lambda Q^T,$ where $Q = LD^{-1/2}.$ In particular, for any integer $n \geq 1,$ $$M^n = Q\Lambda^n Q^T = (LD^{-1/2})\Lambda^n (LD^{-1/2})^T = L D^{-1} \Lambda^n L^T.$$

For any integer $n \geq 1,$ $$D^{-1} \Lambda^n L^T x_0 = \left( \begin{array}{c} \frac{2}{5-\sqrt{5}} \left( \frac{3+\sqrt{5}}{2} \right)^n \\ -\frac{\sqrt{5}}{5} \left( \frac{3+\sqrt{5}}{2} \right)^n \\ \frac{2}{5+\sqrt{5}} \left( \frac{3-\sqrt{5}}{2} \right)^n \\ \frac{\sqrt{5}}{5}\left( \frac{3-\sqrt{5}}{2} \right)^n\end{array} \right).$$ So the recurrence relationship can be written as $x_n = M^n x_0 = L D^{-1} \Lambda^n L^T x_0,$ which is given by \begin{align*}x_n = M^n x_0 &= \left( \begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ -\frac{\sqrt{5}-1}{2} & 0 & \frac{\sqrt{5} + 1}{2} & 0 \\ 0 & -\frac{\sqrt{5}-1}{2} & 0 & \frac{\sqrt{5} + 1}{2}\end{array} \right) \left( \begin{array}{c} \frac{2}{5-\sqrt{5}} \left( \frac{3+\sqrt{5}}{2} \right)^n \\ -\frac{\sqrt{5}}{5} \left( \frac{3+\sqrt{5}}{2} \right)^n \\ \frac{2}{5+\sqrt{5}} \left( \frac{3-\sqrt{5}}{2} \right)^n \\ \frac{\sqrt{5}}{5}\left( \frac{3-\sqrt{5}}{2} \right)^n\end{array} \right)\\ &= \left( \begin{array}{c} \frac{2}{5-\sqrt{5}}\left(\frac{3+\sqrt{5}}{2} \right)^n + \frac{2}{5+\sqrt{5}}\left(\frac{3-\sqrt{5}}{2} \right)^n \\ -\frac{\sqrt{5}}{5} \left(\frac{3+\sqrt{5}}{2} \right)^n + \frac{\sqrt{5}}{5} \left(\frac{3-\sqrt{5}}{2} \right)^n \\ -\frac{\sqrt{5}}{5} \left(\frac{3+\sqrt{5}}{2} \right)^n + \frac{\sqrt{5}}{5} \left(\frac{3-\sqrt{5}}{2} \right)^n \\ \frac{\sqrt{5}(\sqrt{5}-1)}{10} \left(\frac{3 + \sqrt{5}}{2}\right)^n + \frac{\sqrt{5}(\sqrt{5}+1)}{10} \left(\frac{3 - \sqrt{5}}{2}\right)^n \end{array} \right).\end{align*} Therefore, we have $$-\frac{c_n}{d_n} N = \frac{ \frac{\sqrt{5}}{5} \left(\frac{3+\sqrt{5}}{2} \right)^n - \frac{\sqrt{5}}{5} \left(\frac{3-\sqrt{5}}{2} \right)^n }{ \frac{\sqrt{5}(\sqrt{5} - 1)}{10} \left(\frac{3+\sqrt{5}}{2} \right)^n + \frac{\sqrt{5}(\sqrt{5} + 1)}{10} \left(\frac{3-\sqrt{5}}{2} \right)^n } N,$$ which is a monotonically increasing sequence with $$\lim_{n\to \infty} -\frac{c_n}{d_n} N = \sup \left\{ -\frac{c_n}{d_n} N : n \in \mathbb{N}\right\} = \frac{\sqrt{5}+1}{2}N.$$ That is, if $P \leq \frac{\sqrt{5}+1}{2} N,$ then A will still win, or more specifically, the function $$P(N) = \left\lfloor \frac{\sqrt{5}+1}{2} N \right\rfloor$$ gives the maximal value that B can start with but lose to $A$, who starts with N and goes first.

Putting Santul through his paces

Santul completes two 20 mile training runs with different pace profiles:

1) A constant 9 minute mile pace (which is impressive both physically and for its consistency); and

2) His pace starts at 10 minutes per mile and then linearly decreases to 8 minutes per mile over the course of the race. So for instance, when Santul is halfway done with the race (in time, not distance), his pace is 9 minutes per mile.

The question is: which run did he complete faster and what were the two times?

Santul's 9 minute mile run will complete in $9 \,\text{min} \, / \, \text{mile}\, \cdot 20 \,\text{miles} = 180 \,\text{minutes}.$

Let's now look at the second run. Let $$p(t) = a + bt$$ be the linear function of Santul's pace at time $t$. From the initial data we know that $$p(0) = a = 10$$ and that if $T$ is that time that Santul finishes his second run, then $$p(T) = 10 + b T = 8.$$ So $a = 10$ and $b = -\frac{2}{T}.$

We can convert Santul's pace into distance by integrating as follows $d(s) = \int_0^t \,\frac{ds}{p(s)},$ so given the 20 mile course was finished in $T$, we have $$20 = \int_0^T \,\frac{ds}{10 - \frac{2t}{T}} = -\frac{T}{2} \ln (\frac{8}{10}).$$ Solving for $T$ we get $$T = \frac{40}{\ln 1.25} = 179.256804709...$$ which is just a shade under the constant pace time.

Von Neumann's fair coin simulator

For any $p \in (0,1)$, von Neumann showed that an unfair coin which shows heads with probability $p$ can be used to simulate a fair coin by flipping twice, ignoring/redrawing for HH or TT and associating HT with T and TH with H. The issue is that depending on the value of $p,$ one might need to ignore/redraw for HH and TT outcomes for a very large number of tries before getting either TH or HT and exiting.

For what values of $p \in (0,1)$ is it possible to simulate a fair coin in at most $N$ flips?

While the phrasing on the question is a bit vague, I will assume two main frameworks for what "possible" means:

1) For what values of $p \in (0,1)$ is the expected number of flips needed to exit less than or equal to $N$?; or

2) Given some value of $q \in (0,1),$ for what values of $p \in (0,1)$ does the probability that the simulation exists in less than or equal to $N$ exceed $q$?

Let $T$ be the number of flips of the van Neumann simulator needed to exit. The probability that the van Neumann simulator exits after in one flip is $\mathbb{P}\{T = 1\} = 2p(1-p).$ The probability for $k > 1$ that it exits in $k$ flips is $\mathbb{P}\{ T = k \} = 2p(1-p) \cdot (1 - 2p(1-p))^{k-1}.$ So the average is \begin{align*}\mathbb{E}[T] &= \sum_{k=1}^\infty k \mathbb{P} \{ T = k \} = \sum_{k=1}^\infty k 2p(1-p) (1 - 2p(1-p))^{k-1}\\ &= 2p(1-p) \frac{1}{(1 - (1-2p(1-p)))^2} = \frac{1}{2p(1-p)}.\end{align*}

So under framework 1, the question becomes solving for $p \in (0,1)$ such that $$\mathbb{E}_p [T] = \frac{1}{2p(1-p)} \leq N.$$ Thus the solution is $$p \in \left[\frac{1 - \sqrt{1-2/N}}{2}, \frac{1 + \sqrt{1 - 2/N}}{2} \right].$$

Under framework 2, the question becomes for some $q \in (0,1),$ solving for $p \in (0,1)$ such that $$\mathbb{P}_p \{ T \leq N \} = \sum_{k=1}^N 2p(1-p) (1 - 2p(1-p))^{k-1} = 1 - (1 - 2p(1-p))^N \geq q.$$ Since $2p(1-p) \in [0,0.5]$ for all $p \in (0,1),$ if $q > 1-2^{-N},$ then $\mathbb{P}_p \{T \leq N \} \lt q,$ for all $p \in (0,1).$ But for any $q \in [0, 1-2^{-N}],$ then $\mathbb{P}_p \{T \leq N \} \geq q$ for $$p \in \left[ \frac{1 - \sqrt{2 \sqrt[N]{1-q} - 1}}{2}, \frac{1 + \sqrt{ 2 \sqrt[N]{1-q} - 1}}{2} \right].$$

A Game of Hot Pumpkin, or How I Was Left Holding the Chinese Remainder

In a game of Hot Pumpkin with $61$ people, the players count off clockwise upward from $1$ to $N$, eliminating the $N$th player and then then beginning again with the player to the left of the most recently eliminated. The integer value of $N$ is mutually agreed upon prior to beginning the game.

I start and say $1$, with the first eliminated player sitting $18$ spots to my left. Then Ricky starts up the next round and the person $31$ spots to her left is eliminated next. Zach both begins and is eliminated in the third round.

Based on the first three eliminations, what is the smallest value of $N$?

This game sets up as an example of the Chinese remainder theorem, which states that the system of congruences involved in this game, namely \begin{align*} N & \equiv 19 \mod 61 \\ N & \equiv 32 \mod 60 \\ N & \equiv 1 \mod 59,\end{align*} has a single unique solution in $\mathbb{Z}_{59 \cdot 60 \cdot 61} = \mathbb{Z}_{215940}.$

For any two congruences, $N \equiv a_1 \mod n_1$ and $N \equiv a_2 \mod n_2,$ with $\text{gcd}(n_1,n_2) = 1,$ we can use Euclidean algorithm to calculate the integer solution to $$m_1 n_1 + m_2 n_1 = 1$$ that is asserted by B\'{e}zout's identity. From here, we note that $$N = a_1 m_2 n_2 + a_2 m_1 n_1 \mod n_1 \cdot n_2 $$ is a solution to both congruences.

So in particular, we see that $(m_1, m_2) = (1, -1)$ is a solution to $61m_1 + 60m_2 = 1$ and hence $$N = 19 \cdot (-1) \cdot 60 + 32 \cdot 1 \cdot 61 \mod 61 \cdot 60 = 812 \mod 3660$$ is a solution to the first two congruences of our game of Hot Pumpkin.

Continuing onward, we can use the extended Euclidean algorithm to find that the solution to $3660m_1 + 59m_2 = 1$ is $(m_1, m_2) = (-29, 1799).$ This gives the smallest possible solution to all three congruences as \begin{align*}N &= 812 \cdot 1799 \cdot 59 + 1 \cdot (-29) \cdot 3660 \mod 3660 \cdot 59\\ &= 86080352 \mod 215940 \equiv 136232.\end{align*}