9

Problem: $A, B, C, D$ are playing an archery game. They have equal probability of landing their arrow on any spot the target with radius of $R$. Their score is the distance to the center of the target. They take turn to shoot at the target $A, B, C, D, A, B, C, D...$. If one's score is closer to the center of the target than all previous arrows by all players, he survives, goes to the back of the queue, otherwise he is eliminated. We can assume the arrows always hit the target.

What's the probability that $D$ wins this game?

My thoughts: The distribution of the score is obviously linearly scaling from 0 to $R$. But I'm not sure if the distribution of the score matters here. Since we only care about the orders, any order of $x_1, ... x_n$ has $\frac{1}{n!}$ probability regardless of the distribution.

Other than that, I have little clue...

Dmitry Kamenetsky
  • 35,897
  • 5
  • 66
  • 276
Brandon Bolden
  • 99
  • 3
  • 1
    I've written a simple simulation script: https://pastebin.com/JQJPTffu

    It gives a value of about 18% (or 0.18) for D, so the actual answer is probably close to that value.

     – trolley813 Dec 30 '21 at 16:28
  • Depends on the equal probability. If all hit inside R > 0 with probability 1, the game never ends. If the probability is 1 for R >= 0, A wins by hitting the mathematical bullseye on the first shot. If the probability is 0 for any R, everyone always misses the target and D wins by default. – Bass Dec 30 '21 at 16:35
  • @trolley813 We can assume the arrows always hit the target. – Brandon Bolden Dec 30 '21 at 16:38
  • @Bass We can assume the arrows always hit the target. – Brandon Bolden Dec 30 '21 at 16:38
  • well, substitute epsilon for zero in the common hit probability then. – Bass Dec 30 '21 at 16:40
  • not sure what you mean by the game never ends. as long as the scores are not strictly descending, a player gotta be eliminated, and the game would end at one point? – Brandon Bolden Dec 30 '21 at 16:44
  • Is the location of the arrow on the circular target uniformly distributed, or is the score uniformly distributed? These are two different things. – Jeremy Dover Dec 30 '21 at 16:45
  • Each player can aim inside the radius R, where R (<0) is where the previous player hit.(because hitting at exactly 0 happens at zero probability) – Bass Dec 30 '21 at 16:45
  • 1
    @JeremyDover They have equal probability of landing their arrow on any spot the target with radius of R. so score is not uniformly distributed – Brandon Bolden Dec 30 '21 at 17:03
  • 1
    Got it. So your note in the puzzle "The distribution of the score is obviously linearly scaling from 0 to R." is not correct? – Jeremy Dover Dec 30 '21 at 17:49
  • @JeremyDover sorry why is it not correct? the chance of getting 2r is twice as likely as hitting r? However again I dont hink it matters, since we only care about the orders not numerical values, and every order of $x_1, ... x_n$ has same probability $1/n!$? – Brandon Bolden Dec 30 '21 at 19:53
  • 4
    It matters because probability is a function of area, not distance from the origin. You have a $1/2$ probability of hitting inside the circle with radius $R / \sqrt{2}$, not $R/2$. – Jeremy Dover Dec 30 '21 at 21:11
  • Where is this problem from? – bobble Dec 30 '21 at 23:36

1 Answers1

6

I have just answered this question on the math site.

The solution for this one is basically identical, taking into account the comments below my answer there.

In conclusion, the winning probability of $D$ is equal to $\sum_{a, b, c}\frac{a(a + b)(a + b + c)}{(a + b + c + 1)!}$ where the sum ranges through all triples of positive integers $(a, b, c)$ such that one of the following holds:

  • $a \equiv 0 \pmod 4$, $b \equiv 1 \pmod 3$, $c \equiv 1 \pmod 2$;
  • $a \equiv 0 \pmod 4$, $b \equiv 2 \pmod 3$, $c \equiv 0 \pmod 2$;
  • $a \equiv 1 \pmod 4$, $b \equiv 0 \pmod 3$, $c \equiv 1 \pmod 2$;
  • $a \equiv 1 \pmod 4$, $b \equiv 1 \pmod 3$, $c \equiv 0 \pmod 2$;
  • $a \equiv 2 \pmod 4$, $b \equiv 0 \pmod 3$, $c \equiv 0 \pmod 2$;
  • $a \equiv 2 \pmod 4$, $b \equiv 2 \pmod 3$, $c \equiv 1 \pmod 2$.

The result is approximately $0.18343765$.

WhatsUp
  • 7,387
  • 18
  • 46
  • "basically identical" does this account for the circular targets and higher chance to hit closer to the edge? – A username Dec 31 '21 at 01:41
  • 1
    Yes, this is mentioned in the comment below my linked answer: one can use any probability distribution as long as $\Bbb P(X = x) = 0$ for any $x \in \Bbb R$. This is because we have symmetry among $n$ independ random variables, hence any order of the $n$ numbers appears with probability $\frac 1{n!}$. – WhatsUp Dec 31 '21 at 01:55
  • for that particular problem you linked on the math site, I managed to come up with a close form analytical solution. Let $f_2(x)$ be if there are two people, probability of $A$ winning the game, when the lowest score so far is $x$, easy to solve that $f_2(x) = 1 - e^{-x}$, $f_2(1) = 1-1/e$. similarly define $f_3(x)$ for the case when there are 3 people, we can solve $f_3(x)$, and $f_3(1) = 1 - \frac{2\sqrt{3}}{3} e ^{-0.5} \sin (\frac{\sqrt{3}}{2})$. But this involves solving a second order ODE. for 4 persons, it got hairy... so it does seem like a close-form analytical solution exists – Brandon Bolden Jan 01 '22 at 15:30
  • I very much believe that such analytic solutions exist. I didn't work them out because the series that we currently have already converge super fast, thus there seems to be no gain in getting a closed formula. Of course it'll be interesting to know them (: – WhatsUp Jan 01 '22 at 17:30