3
$\begingroup$

If you flip a fair coin 10 times, you could get TTTTTTTTTT. It is unlikely, 0.5^10, but possible. I've played video games that keep the 50% chance, but rearrange the odds so that you can never go more than a few tries without succeeding (getting a heads). They may do this by giving you a base 30% chance to get heads, but each time you get tails you add 10% to your probability of getting heads until you get heads. So your first roll has 30% heads, 70% tails. If you get tails, you have 40% heads 60% tails. Then 50/50, then 60/40, then 70/30, ... then 100/0. Whenever you get the heads, you go back to the original probability. I ran a computer simulation with base 30% then a 30.5% boost each tails, which gave me a net result of ~50% after 50 million tosses. Thats pretty complicated to think about analytically, so lets reduce this to the following:

So lets define a Pity Probability as follows:

A. If no coin toss has been made, or the last toss was heads:

  1. The coin has P probability of getting heads

  2. The coin has probability Q = (1-P) of tails.

B. If the last toss was tails:

  1. The coin has 100% probability of getting heads.

  2. The coin has 0% probability of getting tails.

This is equivalent to the original statement with base probability P and bonus probabilty 100%.

The question is what probability must P be such that the expected number of heads (Say after 1000 tosses) is some P'. Since we have these simplified rules instead of the general toss-by-toss P increase, we can not get below P' = 50% (That is P = 0, which is guaranteed to produce THTHTHTHTHTHTH...) since P(H) = 0 then upon T we have P(H) = 1.

Lets pick P' = 75%. It looks like P=2/3 gives us P'=75% according to my computer simulation. I tried to derive this analytically, but it is a fractal if you draw it out (Heads branch to heads and tails, tails only branch to heads).

The Net Heads Prob is calculated by summing the permutation probabilities multiplied by the number of heads in that permutation, divided by the number of trials, for all permutations.

Trials: 1
H 2/3
T 1/3
Net Heads Prob = (2/3 * 1)/1 = 66%

Trials: 2
HH 2/3 * 2/3 = 4/9
HT 2/3 * 1/3 = 2/9
TH 1/3 * 1 = 3/9
TT 1/3 * 0 = 0/9
Net Heads Prob = ((4/9)*2 + (2/9)*1 + (3/9)*1)/2 = 13/18 ~= 72.2%

Trials: 3
HHH = (2/3)^3 = 8/27
HHT = (2/3)^2 * 1/3 = 4/27
HTH = (2/3)*(1/3)*1 = 6/27
HTT = (2/3)*(1/3)*0 = 0
THH = (1/3)*1*(2/3) = 6/27
THT = (1/3)*1*(1/3) = 3/27
TTH = (1/3)*0*1 = 0
TTT = (1/3)*0*0 = 0

Net Heads prob = ((8/27)*3 + (4/27)*2 + (6/27)*2 + (6/27)*2 + (3/27)*1)/3 = 59/81 ~= 72.839%

We can see we're approaching 75%, and my simulation of 50 million confirms it, but is there a way we can show this in closed form? That is, as the number of trials approaches infinity, the probability of heads is P'=75%? How about the original problem, where you have a base probability then keep adding to it every time you fail until you succeed?

$\endgroup$
2
$\begingroup$

This is a solution to the simplified version of the problem presented in OP.

By the rules of the game, we can write

$$P(H_{t+1}) = P(H_{t+1}|H_t)P(H_t) + P(H_{t+1}|\neg H_t)(1-P(H_t)) = \theta P(H_t) + (1-P(H_t))$$ where $H_t$ is the event that the $t$th flip lands on heads and $\theta$ is the base probability.

After enough flips we would arrive at a steady state distribution, therefore $P(H_t) = P(H_{t+1}$). This simplifies the equation to

$$P(H) = P(H)\theta+1-P(H)$$

which can be rearranged into the form

$$P(H) = \frac{1}{2-\theta}$$

or

$$\theta = 2-\frac{1}{P(H)}$$

It can be verified that $P(H) = \frac{3}{4}$ implies $\theta = \frac{2}{3}$ and vice-versa, and also that $P(H) \geq \frac{1}{2}$ for all valid values of $\theta$.


In the more general case, you would model this as a markov process, and define the transition matrix $T$ for going from one state to another. For this simple problem we have $$T = \begin{bmatrix}\theta& 1 \\ 1-\theta & 0 \end{bmatrix}$$ Then find the probability vector $\pi$ such that $\pi = T\pi$. Note that $$\pi = \begin{bmatrix}\frac{1}{2-\theta} \\ \frac{1-\theta}{2-\theta} \end{bmatrix}$$ is a valid solution to this equation, and gives us the probability that a flip will be heads or tails respectively. This formulation can be used to solve the more general problem proposed in OP.

$\endgroup$
  • $\begingroup$ Combining recurrence, conditional probability, and limits ( P(H_t+1) = P(H_t) )... but is so simple and elegant. I may play with the general problem using the suggested method and post the results as an edit. Thanks very much for your time writing this up, it's expanded my knowledge and interest in probability. Also ,your machine learning answers are awesome! $\endgroup$ – user2770791 Jul 7 '18 at 14: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.