2
$\begingroup$

This game of two players has public parameters an integer $n\ge2$, and a probability $p$ with $1/n<p\le1$. E.g. $n=4$, $p=1/3$.

In the first phase of a game, a player secretly decides $n$ probabilities $p_i$ with $0\le p_i\le1$ for indexes $i\in[0,n)$, subject to the constraint $n\,p=\sum p_i$. It follows at least two $p_i$ are non-zero.

Then the other player repeatedly chooses an index $i\in[0,n)$ and has a hit for $i$ with probability $p_i$ (thus hits with probability $p$ if choosing $i$ uniformly at random).

A game stops after hits for two distinct $i$. The winner (if any) is the player who needed the least index choices for this, in two games with the roles reversed.

How to play in each of the two phases in order to maximize probability of winning ?

Under optimal strategy, what's the probability (or a tight lower bound for large $n$ or/and small $p$) that a player stops within $c$ choices, as a function of $n$, $p$, $c$ ?

Note: the strategies and probabilities asked are for the first of the two games, and subsidiarily for the second one should that need any adjustment according to the outcome of the first game, which is known by both players. If that matters, add that coin toss determines which player decides who guesses first, and tell how to make that decision.

$\endgroup$
4
  • $\begingroup$ Looks like an interesting question! So as the guesser, the only feedback we got in each turn is whether we get a hit, right? $\endgroup$
    – justhalf
    Apr 8 at 10:18
  • $\begingroup$ @justhalf: yes, that's the only clue we get about the other player's choice of $p_i$, beyond $n\,p=\sum p_i$. $\endgroup$
    – fgrieu
    Apr 8 at 10:35
  • 1
    $\begingroup$ Are the two games played in order, and if so, does that mean the score of the guesser in the first game affects each player's strategy in the second game? $\endgroup$
    – noedne
    Apr 8 at 12:07
  • $\begingroup$ @noedne: good question! I'm uncertain about if it's in the interest of a player to adjust it's strategy according to the result of the first game. And if it is, I'm not even sure if the player that has an edge is the first to guess or the first to decide the $p_i$. I added a note. $\endgroup$
    – fgrieu
    Apr 8 at 13:39

1 Answer 1

1
$\begingroup$

I haven't worked out the math and tested this theory yet, but at a glance my gut says that

The optimal guessing strategy is to just randomly choose indexes without replacement until you've won or gone through them all, and keep repeating this (avoiding any index you get a hit on) until you win.

e.g. in a game where $n = 4$, you might choose index 0 on your first turn. If you get a miss, you want to guess indexes 1, 2 and 3 at least once each before you guess index 0 again.

If you guess and get a hit, you never want to guess that index again. If you guess and miss, this lowers your estimate of the $p_i$ value for that index relative to the others. So you don't want to guess that index again until you've tried all the others.

And then:

Given that the optimal guessing strategy is to just guess randomly through the order, I suspect that there's no optimal strategy for secretly deciding the $p_i$ values as the overall probability of getting a hit is unchanged. May as well distribute them uniformly, or generate them randomly, or make all but two of them 0, etc.

I now suspect the optimal strategy is something like assigning a probability of $1$ to one of the indexes, $(n * p - 1)$ to another, and $0$ to all the rest. This means the guesser is guaranteed to get one hit on a single pass through all the indexes, but leaves as small as possible a chance of getting the second hit. I think the advantage of this strategy over others is magnified as $n$ gets larger and/or $p$ gets smaller.

$\endgroup$
3
  • $\begingroup$ I come to the same conclusion for the first hint. But I have a different feeling for the second. $\endgroup$
    – fgrieu
    Apr 8 at 18:14
  • $\begingroup$ Yes I think you may be right, I wrote a quick simulation and one of the strategies ends up different than the others. I'll have a go at figuring it out. $\endgroup$
    – SQLnoob
    Apr 8 at 18:39
  • $\begingroup$ Better, but I still disagree with the second hint. Per my (not cross-checked) simulation, with (n,p)=(4,1/3) your strategies generate games of an expected 9.11 choices and I claim significantly more (but I'm not even sure that expectancy is a correct metric to compare strategies). Also, the question is about arbitrary (n,p) with 1/n<p≤1 but your strategy as stated is applicable only if 1/n<p≤2/n. $\endgroup$
    – fgrieu
    Apr 9 at 5:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.