0
$\begingroup$

Consider a simple game: you and I alternate flipping coins, and (arbitrarily) I flip first. I win if I flip a total of $M$ heads before you flip a total of $N$ heads. For integers $M$ and $N$, what is the probability that I will win?

I can easily write a program to determine the probability through random simulations, so I'm not interested in answers about that. What I'd like to know is whether any well-known probability distribution can model this situation, or whether there is any closed-form solution that can give an answer, even if only approximately.

I'm aware of the negative binomial distribution which seems related, but doesn't seem to apply directly. Of course generalizations (e.g. biased coins, simultaneous flips) are interesting too.

$\endgroup$
0
$\begingroup$

From Wikipedia: https://en.wikipedia.org/wiki/Negative_binomial_distribution Suppose there is a sequence of independent Bernoulli trials. Thus, each trial has two potential outcomes called "success" and "failure". In each trial the probability of success is p and of failure is (1 − p). We are observing this sequence until a predefined number r of failures have occurred. Then the random number of successes we have seen, X, will have the negative binomial (or Pascal) distribution: $X \sim NB(r,p)$.

If I understand right what is your problem, this seems to be exactly what you need. If $X \sim NB(M,\frac12)$, then $X+M$ should be the number of try to flip $M$ heads ($X$ counts the number of failures) and if $Y \sim NB(N,\frac12)$ your opponent has its $N$ heads at time $N+Y$. You are just trying to find $\mathbb{P}(X + M \leq Y + N)$ (the $\leq$ sign is because you play first).

Then by Fubini and by independence you easily obtain $$\mathbb{P}(X + M \leq Y + N) = \sum_{k = 1}^{\infty} \sum_{j = 1}^k \mathbb{P}(X = k - M) \mathbb{P}(Y = j-N). $$ (note that a lot of terms in this sum should be 0). Just use the definition of the negative binomial probability, this should lead you to the answer.

$\endgroup$
0
$\begingroup$

Let $P(M,N)$ be the probability of flipping $M$ heads before your opponent flips $N$ heads, and it is your turn. Note that the following relation holds $$P(M,N)=1-\frac{P(N,M)+P(N,M-1)}2$$And of course, $P(0,0)$ is undefined, $P(0,N)=1$, and $P(M,0)=0$.

We unwrap one more time, noting that $$P(N,M)=1-\frac{P(M,N)+P(M,N-1)}2$$

So, $$P(M,N)=1-\frac{2-P(M,N)-P(M,N-1)+2P(N,M-1)}4$$ $$P(M,N)=\frac{P(M,N)+P(M,N-1)+2-2P(N,M-1)}4$$$$P(M,N)=\frac{P(M,N-1)+P(M-1,N)+P(M-1,N-1)}3$$This formula is good since we know that we will eventually hit one of the base cases.

This code allows you to find the probability of any $M,N$ you like without any randomness.

$\endgroup$

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.