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.$$
No comments:
Post a Comment