Martina and Olivia each secretly generate their own random real number, selected uniformly between 0 and 1. Starting with Martina, they take turns declaring (so the other can hear) who they think probably has the greater number until the first moment they agree. Throughout this process, their respective numbers do not change.
They are playing as a team, hoping to maximize the chances they correctly predict who has the greater number. For any given round with randomly generated numbers, what is the probability that the person they agree on really does have the bigger number?
Extra credit: Martina and Olivia change the rules so that they stop when Olivia first says that she agrees with Martina. That is, if Martina says on her turn that she agrees with Olivia, that is not a condition for stopping. Again, if they play to maximizing their chances, what is the probability that the person they agree on really does have the bigger number?
Martina and Olivia are excellent Bayesian statisticians and after each response they update the current bounds for the other's random value. In particular, after $k$ responses from Olivia, there are estimates $O_\text{lo}^k, O_\text{hi}^k$ and $M_\text{lo}^k, M_\text{hi}^k$ such that Martina believes that Olivia's number is distributed as $U(O_\text{lo}^k, O_\text{hi}^k)$ and Olivia believes that Martina's number is distributed as $U(M_\text{lo}^k, M_\text{hi}^k).$ Given this assumption and that Martina knows the realization of her own random process $m$, she will respond for her $k$th response that she believes her own value is bigger whenever $$\mathbb{P} \{ O \leq m \mid O \sim U(O_\text{lo}^k, O_\text{hi}^k) \} \geq 0.5$$ and that Olivia's number is larger otherwise. Similarly, since Olivia knows ther realization of her own random process $o,$ Olivia's $k$th response will similarly be that she believes her own value is bigger whenever $$\mathbb{P} \{M \leq o \mid M \sim U(M_\text{lo}^k, M_\text{hi}^k) \} \geq 0.5.$$
Based on the faithful behavior of the players to estimate which of them have the larger number based on all of the available inforation, the updating procedure for $O_\text{lo}^k, O_\text{hi}^k, M_\text{lo}^k$ and $M_\text{hi}^k$ are interrelated, with \begin{align*} M_\text{lo}^k &= \begin{cases} \frac{1}{2}(O^{k-1}_\text{lo} + O^{k-1}_\text{hi}), &\text{if Martina says her number is bigger}\\ M^{k-1}_\text{lo}, &\text{if Martina says Olivia's number is bigger}\end{cases}\\ M_\text{hi}^k &= \begin{cases} M^{k-1}_\text{hi}, &\text{if Martina says her number is bigger}\\ \frac{1}{2}(O_\text{lo}^{k-1} + O_\text{hi}^{k-1}), &\text{if Martina says Olivia's number is bigger}\end{cases}\\ O_\text{lo}^k &= \begin{cases} O^{k-1}_\text{lo}, &\text{if Olivia says Martina's number is bigger}\\ \frac{1}{2}(M^{k-1}_\text{lo} + M^{k-1}_\text{hi}), &\text{if Olivia says her number is bigger}\end{cases}\\ O_\text{hi}^k &= \begin{cases} \frac{1}{2}(M^{k-1}_\text{lo} + M^{k-1}_\text{hi}), &\text{if Olivia says Martina's number is bigger}\\ O_\text{hi}^{k-1}, &\text{if Olivia says her number is bigger}\end{cases}\end{align*}
For any $(m,o) \in [0,1] \times [0,1],$ the gameplay can be characterized by a finite string in the alphabet $\{M,O\}$ corresponding the concatenating Martina's and Olivia's responses until there is either an instance of $MM$ or $OO.$ We can carve up the unit square $[0,1] \times [0,1]$ into response regions where each $(m,o)$ in that region would lead to the same response history from Martina and Olivia in their game. So, for instance the $MM$ region is $[0.5,1] \times [0,0.75],$ and the subregion within $MM$ where the identified player does not have the largest number is a right isoceles triangle with side length $0.75 - 0.5 = 0.25.$ On the flip side the $OO$ region is $[0,0.5] \times [0.25,1]$ and also has a misidentified region that is right isoceles triangle with side length $0.25.$ So if the gameplay string has $2$ characters, the mischaracterization region has area (1/4)^2.$
Moving further, we see that the regions $MOO$ given by $[0.5,0.875] \times [0.75,1]$ and $OOM$ given by $[0.125,0.5] \times [0,0.25]$ are congruent and each has a misidentification region shaped like a right isoceles with side length $0.125.$ If the gameplay string has $3$ characters, then the misidentification region has area $(1/8)^2.$ Moving further on, we see that if the gameplay string has $k$ characters, then the misidentification region has area $(1/2^k)^2 = 4^{-k}$. Therefore, the entire misclassification region has area given by $$\sum_{k=2}^\infty \frac{1}{4^k} = \frac{1}{1-\frac{1}{4}} - 1 - \frac{1}{4} = \frac{4}{3} - \frac{5}{4} = \frac{1}{12}$$ and thus the probability of correctly identifying the player with the larger number is $\frac{11}{15}.$
If Martina and Olivia modified the game to end only if Olivia agrees with Martina, then this limits the response strings to only those with even lengths. In this case, the misidentified region now has area $$\sum_{k=1}^\infty \frac{1}{4^{2k}} = \sum_{k=1}^\infty \frac{1}{16^k} = \frac{1}{1-\frac{1}{16}} - 1 = \frac{1}{15},$$ and so the modification allows the pair gets better at identifying the player with probability $\frac{15}{16}.$
No comments:
Post a Comment