31
$\begingroup$

I've been thinking about the following game for a while and am curious if anyone has any ideas of how to analyze it.

Problem description

Say I have two biased coins: coin 1 that shows heads with probability $p$ and coin 2 that shows heads with probability $q$. You and I both know the statistics of the coins.

The game proceeds in multiple rounds as follows:

  • In the starting round $n=0$:

    • I (privately) pick a coin and flip it, we both observe the outcome
    • you decide to make a guess of which coin I just flipped, or continue watching
    • if you guess correctly, I pay you $\$100$; if you guess incorrectly, you receive no reward and the game is over

  • At each subsequent round $n\ge 1$:

    • I decide to stay with my current coin or reach into my pocket and swap out the current coin for the other coin
    • you can see whether I swapped out the coin or not (assume I must switch if I reach into my pocket)
    • I flip the coin and we both observe the outcome
    • you decide to guess which coin was just flipped, or keep watching
    • if you guess correctly, I pay you $\$100\cdot\delta^n$, where $\delta\in(0,1)$; if you guess incorrectly the game ends with you getting nothing

Question

I want to find the "best" switching strategy to minimize the (expected) amount of money I have to pay you.

Notes

The probabilities $p$ and $q$ can take on any value, but let's assume that they cannot be equal.

Since you are trying to maximize your reward, the discount factor $\delta$ incentives you to guess correctly as quickly as possible.

Since there are only two coins and you observe when I switch, you are trying to discern between two possible coin sequences, one where the initial coin was coin 1 and the other where the initial coin was coin 2.

My first thoughts are that I would want to keep the empirical averages (of the two sequences) as close as possible to each other. Intuitively this will be easy if $p$ and $q$ are close, but hard if they are far apart.

$\endgroup$
9
  • 2
    $\begingroup$ Nothing else is know about $p$ and $q$? They could both be $<\frac12$ for example? Also, I'm not sure how " the expected time it takes you to make a correct guess" is to be computed. How do we deal with the cases when an incorrect guess is made? Suppose $p=.4$ and $q=.4001.$ I would be very likely to just guess $p$ after the first flip, no matter what the result, since it would take an inordinate number of flips before I had any confidence at all that I knew which was which. Is this to be taken into account somehow? $\endgroup$
    – saulspatz
    May 4, 2019 at 15:43
  • 4
    $\begingroup$ Suppose q=1/4 and p=1/8. Suppose there is a well defined solution to this problem, and suppose the optimum requires the game controller to pick a specific coin first. Then player 2 can in principle solve this problem and will know player 1 will choose that specific coin first, so player 2 can always guess perfectly even before any coins are flipped! $\endgroup$
    – Michael
    May 5, 2019 at 1:10
  • 3
    $\begingroup$ @Michael - yeah, this will certainly be a mixed strategy. i'm thinking it might be fun just to solve the "no swapping" case. i.e. if Player 1 is never allowed to swap, what mixed strategies should each player use? The Nash equilibrium for even that simple case is not trivial for me... $\endgroup$
    – antkam
    May 5, 2019 at 3:24
  • 3
    $\begingroup$ @Michael, in which case player 1, knowing that player 2 can solve the problem, would choose the non optimal starting coin to avoid paying player 2. Unless player 2, knowing player 1 knows that player 2 can solve the problem and would thus choose the non optimal starting coin, ... (Feels like something out of the Princess Bride!) $\endgroup$
    – Richard Ambler
    May 9, 2019 at 14:07
  • 2
    $\begingroup$ @RichardAmbler : Inconceivable! =) $\endgroup$
    – Michael
    May 9, 2019 at 15:31

3 Answers 3

Reset to default
1
$\begingroup$

Here are solutions for some very special cases. Assume, without loss of generality, that $\ p> q\ $.

If $\ p+q \le 1\ $, and $\ \delta\le \frac{1-q}{2-p-q}\ $, you can keep my expected winnings to at most $\ \frac{100\,(1-q)}{2-p-q}\ $ dollars by choosing coin $1$ with probability $ \frac{1-q}{2-p-q}\ $ and coin $2$ with probability $ \frac{1-p}{2-p-q}\ $. I can ensure that my expected winnings are at least $\ \frac{100\,(1-q)}{2-p-q}\ $ dollars by guessing coin $1$ if the result of the first toss is heads, or coin $1$ with probability $ \frac{1-p-q}{2-p-q}\ $ and coin $2$ with probability $ \frac{1}{2-p-q}\ $ if the result of the first toss is tails. Because I can't win more than $\ 100\,\delta \le \frac{100\,(1-q)}{2-p-q}\ $ dollars by waiting until the next toss, I have nothing to gain by doing so.

If $\ p+q = 1\ $ (and therefore $\ p>\frac{1}{2}\ $, given the above assumption that $\ p>q\ $), and $\ \delta\le p $, you can keep my expected winnings to at most $\ 100\,p\ $ by choosing either coin $1$ or $2$ with probability $\ \frac{1}{2}\ $ each. I can ensure my expected winnings are at least $\ 100\,p\ $ by guessing coin $1$ if the result of the first toss is heads, or coin $2$ if the result of the first toss is tails. Again I can do no better by waiting for the second toss.

If $\ p+q > 1\ $, and $\ \delta\le \frac{p}{p+q}\ $, you can keep my expected winnings to at most $\ \frac{100\,p}{p+q}\ $ by choosing coin $1$ with probability $\ \frac{q}{p+q}\ $ and coin $2$ with probability $\ \frac{p}{p+q}\ $. I can ensure my expected winnings are at least $\ \frac{100\,p}{p+q}\ $ by guessing coin $2$ if the result of the first toss is tails, or coin $1$ with probability $\ \frac{1}{p+q}\ $ and coin $2$ with probability $\ \frac{p+q-1}{p+q}\ $ if the result of the first toss is heads.Once again, I can't do better by waiting for the second toss.

$\endgroup$
1
$\begingroup$

This is a problem of Bayesian parameter estimation. The following link Bayesian coin flips might be useful. If you are interested in simulation , check out this link.

In any case essential here is the fact that the player doing the guessing can keep track of the outcomes related to each of the two coins (even if initially he does not know which one is the p-coin and which one is the q-coin).

The best strategy for the player doing the switching is to keep the number of outcomes related to each of the two coins, equal or close to equal, because the more outcomes are available to the guessing player (related to a coin), the probability of guessing correctly increases. In other words, the switching player must switch the coins at almost every stage of the game.

Edit. If you want an interesting statistical approach , see the related question confidence two biased dice are the same (and one of the comments, the Kolmogorov-Smirnov test). The transition from dice to coins is obvious.

$\endgroup$
4
  • $\begingroup$ Hi Cristian, thanks, the "fee" you mention is captured by the discount factor. $\endgroup$
    – Erik M
    May 19, 2019 at 2:18
  • $\begingroup$ According to the fifth condition specified for rounds subsequent to the first ($\ n=0\ $), you won't win $\ \$100\ $, but $\ \$100\,\delta^n\ $, where $\ n\ $ is the number of rounds for which you have kept passing, and $\ 0<\delta<1\ $. $\endgroup$
    – lonza leggiera
    May 19, 2019 at 2:25
  • $\begingroup$ Yes, got it. I am not sure if a Markov chain model is suitable here, since your strategy will depend on my actions, so it will depend on the past. Interesting little problem. $\endgroup$
    – Cristian Dumitrescu
    May 19, 2019 at 2:37
  • $\begingroup$ Thank you @ErikM for the clarification. As a consequence I edited my answer appropriately. I hope it's useful. $\endgroup$
    – Cristian Dumitrescu
    May 19, 2019 at 4:19
0
$\begingroup$

I'll think about the simpler situation where you can't switch the coins at all. I think this is complicated enough. After each coin flip, I have three choices -- guess coin 1, guess coin 2, or see another flip.

Intuitively, I think my strategy should have to do with:

  • the difference between $p$ and $q$: if they are very close, it will take me more flips to distinguish between them with, say, 95% certainty.
  • the value of $\delta$: if it is close to $1$, I'm more willing to see more flips; if it's close to $0$, I'll want to guess while I'm less certain.

The expected value of guessing coin 1 (with heads probability $p$) after seeing $n$ of $N$ flips come up heads is:

$\delta^N \times p(c_1|n, N) = \delta^N \times p(\theta = p|n, N) \propto \delta^N \times p(n, N|\theta = p)$

This is easily computable. The same can be done for coin 2. But what's the expected value of waiting to see another coin? If we had that, we could straightforwardly pick the option with the highest expected value.

I think it should also have something to do with the specific values of the flips that I've seen so far. Supposing $0 < p < q < 1$, here are some "corner" cases:

  • $n = 0$: I would guess coin 1 or wait -- never guess coin 2.
  • $\frac{n}{N} = \frac{p + q}{2}$: It's tempting to want to say that I'd always wait for another flip in this case, but consider $p = 0, q = 0.8, n = 4, N = 10$. It's clear that you've chosen coin 2. The thing to remember here is that the sampling variance is smaller around probabilities close to the edges than around probabilities close to the middle.
  • $n = N$: I would guess coin 2 or wait -- never guess coin 1.

Generally, I can say, if $p(n, N|\theta = p) > p(n, N|\theta = q)$, I will either guess coin 1 or wait -- never guess coin 2. Whether to guess coin 1 or wait...not sure.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .