Solved – Three players with their own coin flip untill they have heads. The first one with heads wins

distributionsjoint distributionprobability

I have been stuck with this question for some time and I'm not sure if I'm doing it correctly.

There are three players who each have their own coin—each coin having a different probability for it to land on heads. They play this game simultaneously, the first one to flip heads wins the game.

Let $X$ be the number of flips player 1 needs to get heads, $Y$ the number of flips for player 2 till he has heads, and $Z$ be the flips for player 3 till he has heads.

Now I noted this down as $X\sim \textrm{Geom}(p), Y\sim \textrm{Geom}(q)$, and $Z\sim \textrm{Geom}(r)$. These three variables are independent.

My first question would be: What is the probability that player 1 wins?
I thought it was enough to calculate $\mathrm{P}(X < Y < Z) + \mathrm{P}(X < Z < Y)$.

But now I'm not sure that this is enough.

I'm also not so sure about this: the number of turns needed to determine the winner of this game would be the $\mathrm{Min}\{X, Y, Z\}$, since the first person to flip heads will win. Hence meaning that its the minimum right?

So the number of turns after the winner is known until the last person to flip heads would be the $M = \mathrm{Max}\{X,Y,Z\}$, after someone wins the game you go and play until everyone has heads. This would mean the maximum of the flips? So since these three variables are geometric and independent this comes down to:
$$
\mathrm{P} (M>m) = \mathrm{P} (X>m; Y>m; Z>m)= ((1-p)(1-q)(1-r)^m)
$$

This means that $M$ is also Geometric but then moved to zero.

So I hope someone can maybe tell me if I'm doing this correctly, or if I should calculate these things differently.

Best Answer

I am sure there are many ways to analyze this situation, but the following one is appealing for its simplicity and use of only the most basic properties of probability. Assuming ties for heads cause the game to continue until a result is uniquely determined, it shows the chance of a player winning the game is her relative odds: the proportion of her odds of heads, divided by the sum of the odds of heads among all players. The game length obviously has a geometric distribution. Its parameter is proportional to this sum of odds. The constant of proportionality is the product of all the chances of tails.

Other methods of resolving ties (to create a definite winner) can be analyzed in a similar way, starting with computing the chance that a given player will win a particular round and continuing as shown here.

Let there be $m$ players, each using a coin with probability $p_i$ of heads. Let $i,j,\ldots, k$ be any permutation of $(1,2,\ldots,m)$.

Suppose that when a tie occurs, no outcome is declared and play continues. Then the chance that player $i$ wins is the chance that she is the sole person to toss heads, equal to

$$p_i(1-p_j)\ldots(1-p_k) = \frac{p_i}{1-p_i}\prod_{l=1}^m (1-p_l) = \pi_i Q$$

where I have written $\pi_i = p_i/(1-p_i)$ for player $i$'s odds of heads and $Q$ for the product of all $1-p_l$ (the chance that everybody simultaneously observes a tail).

If no player wins a round, the game starts over, with exactly the same probabilities. Therefore the chance that player $i$ wins the entire game is the chance they can win a given round, divided by the sum of all players' chances to win the round:

$$\Pr(i\text{ wins}) = \frac{\pi_i Q}{\sum_{l=1}^m \pi_l Q} = \frac{\pi_i}{\sum_{l=1}^m \pi_l} = \frac{\pi_i}{\pi}.$$

It is their proportion of the total odds $\pi$.

The chance that the game ends on any particular round is the chance that exactly one player observes heads, equal to

$$\sum_{l=1}^m \pi_l Q = \pi Q.$$

Thus the length of the game has a geometric distribution with parameter $\pi Q$.

This result is supported by simulation:

It was carried out with this R script, which can simulate and summarize tens of millions of tosses per second for arbitrarily many players (up to limits determined by RAM).

coins <- log(2:10); coins <- coins / sum(coins)
n.players <- length(coins)
n.rounds <- 1e6
#
# Simulate many rounds.
#
system.time({
  tosses <- matrix(runif(n.rounds * n.players), nrow=n.players) < coins
  wins <- colSums(tosses) == 1
  winners <- colSums(1:n.players * tosses) * wins
  (results <- tabulate(winners[winners != 0], n.players))
})
#
# Compare to theory.
#
odds <- coins / (1-coins)
p <- odds / sum(odds)
rbind(Simulation=results / sum(results), Theory=p)
#
# Display the distribution of game lengths compared to the geometric distribution.
#
lengths <- diff(c(0, which(wins==TRUE)))
Q <- prod(1 - coins)
pQ <- sum(odds) * Q
n.max <- ceiling((log(.002) + log(pQ)) / log(1-pQ)) # Plotting limit
prob.geometric <- (1 - pQ)^(1:n.max - 1) * pQ

subtitle <- paste(sum(results),"games played with coins", 
                  paste(round(coins, 2), collapse=","))
hist(lengths[lengths < n.max], freq=FALSE, breaks=(1:n.max)-1/2,
     main="Simulation (bars) vs. Theory (lines)",
     xlab="Game lengths",
     sub=subtitle)

invisible(sapply(1:n.max, function(i) {
  lines(c(i,i), c(0, prob.geometric[i]), lwd=2, col="Red")
}))

Example where your system makes absolutely no sense

Let $K$ be a draw from the normal distribution $\mathcal{N}(0,10000000000000)$ and let the payoff function be $f(K) = K^2$. Your system says I shouldn't pay more than $0$ for this gamble because $f(\mathrm{E}[K]) = 0^2 = 0$. But shouldn't you assign some positive value to this gamble?! There is a 100% probability the payoff is greater than zero!

A more classic resolution of the St. Petersburg Paradox

One approach is to add risk-aversion. If you're sufficiently risk averse, what you're willing to pay to play this infinite expectation gamble will be finite. If you accept the Von Neumann-Morgernstern axioms, then the certainty equivalent of playing the game is given by $z$ where:

$$u(w + z) = \mathrm{E}[ u(w + f(K)) ] $$

and where $w$ is your wealth and $u$ is a concave function (in jargon, a Bernoulli utility function) which captures your level of risk aversion. If $u$ is sufficiently concave, the valuation of $2^K$ will be finite.

A Bernoulli utility function with some nice properties turns out to be $u(x) = \log(x)$. Maximizing expected utility where the Bernoulli utility function is the log of your wealth is equivalent to maximizing the expected growth rate of your wealth. For simple binary bets, this gives you Kelly Criterion betting.

An important other point is that the risk aversion approach leads to different certainty equivalents depending on what side of the gamble you are on.

Solved – How to model flips until N successes

The distribution of the number of tails before achieving $10$ heads is Negative Binomial with parameters $10$ and $1/2$. Let $f$ be the probability function and $G$ the survival function: for each $n\ge 0$, $f(n)$ is the player's chance of $n$ tails before $10$ heads and $G(n)$ is the player's chance of $n$ or more tails before $10$ heads.

Because the players roll independently, the chance the first player wins with rolling exactly $n$ tails is obtained by multiplying that chance by the chance the second player rolls $n$ or more tails, equal to $f(n)G(n)$.

Summing over all possible $n$ gives the first player's winning chances as

$$\sum_{n=0}^\infty f(n)G(n) \approx 53.290977425133892\ldots\%.$$

That is about $3\%$ more than half the time.

In general, replacing $10$ by any positive integer $m$, the answer can be given in terms of a Hypergeometric function: it is equal to

$$1/2 + 2^{-2m-1} {_2F_1}(m,m,1,1/4).$$

When using a biased coin with a chance $p$ of heads, this generalizes to

$$\frac{1}{2} + \frac{1}{2}(p^{2m}) {_2F_1}(m, m, 1, (1 - p)^2).$$

Here is an R simulation of a million such games. It reports an estimate of $0.5325$. A binomial hypothesis test to compare it to the theoretical result has a Z-score of $-0.843$, which is an insignificant difference.

n.sim <- 1e6
set.seed(17)
xy <- matrix(rnbinom(2*n.sim, 10, 1/2), nrow=2)
p <- mean(xy[1,] <= xy[2,])
cat("Estimate:", signif(p, 4), 
    "Z-score:", signif((p - 0.532909774) / sqrt(p*(1-p)) * sqrt(n.sim), 3))

Best Answer

Related Solutions

Solved – What’s wrong with this proposed resolution to the St Petersburg Paradox

Example where your system makes absolutely no sense

A more classic resolution of the St. Petersburg Paradox

Solved – How to model flips until N successes

Related Question