9
$\begingroup$

Consider a hypothetical coin (with two sides: heads and tails) that has a $3/4$ probability of landing on the side it was before the flip (meaning, if I flip it starting heads-up, then it will have an only $1/4$ probability of landing tails-up). If it begins on heads, what is the probability that it is on tails after 10 flips? What about 100 flips? Assume that each flip starts on the same side as it landed on the previous flip.

Note: this is not a homework problem, just something I thought up myself.

$\endgroup$
  • 1
    $\begingroup$ I was with you all the way up to the last sentence (Assume that each flip...) - what does that mean? The rest makes perfect sense. $\endgroup$ – mathguy May 24 '16 at 3:27
  • 1
    $\begingroup$ Coin flips have been shown to have a bias according to the side they start on actually. Don't remember the researcher name though, pretty famous person in California iirc, look it up. I'm guessing that the op wasn't aware of that though. $\endgroup$ – jdods May 24 '16 at 3:30
  • $\begingroup$ This could probably be solved by setting up a simple 2 state Markov chain. I'd write it up but an away for the evening now. $\endgroup$ – jdods May 24 '16 at 3:33
  • $\begingroup$ "this is not a homework problem, just something I thought up myself" -- then well done, because as it happens this is a fairly common kind of exercise! You've found the "right" problem, the one that (with others like it) provokes the theory of Markov chains. $\endgroup$ – Steve Jessop May 24 '16 at 10:18
  • 1
    $\begingroup$ @mathguy It seems to me he's saying the side facing up doesn't change from the time the coin lands to the time that it's flipped again. Which sounds redundant, but it's better than being unclear. $\endgroup$ – Turambar May 24 '16 at 12:46
8
$\begingroup$

Let $p_n$ be the probability the coin is on tails after $n$ flips. Note that $p_0=0$.

The coin can be on tails after $n+1$ flips in two different ways: (i) it was on tails after $n$ flips, and the next result was a tail or (ii) it was on heads after $n$ flips, and the next result was a tail.

The probability of (i) is $(3/4)p_n$ and the probability of (ii) is $(1/4)(1-p_n)$. Thus $$p_{n+1}=\frac{1}{4}+\frac{1}{2}p_n.\tag{1}$$ Solve this recurrence relation. The general solution of the homogeneous recurrence $p_{n+1}=\frac{1}{2}p_n$ is $A\cdot \frac{1}{2^n}$. A particular solution of the recurrence (1) is $\frac{1}{2}$. So the general solution of the recurrence (1) is $$p_{n}=A\cdot \frac{1}{2^n}+\frac{1}{2}.$$ Set $p_0=0$ to find $A$. We find that $p_n=\frac{1}{2}-\frac{1}{2^{n+1}}$.

$\endgroup$
6
$\begingroup$

If you mean that $\Pr(H_i|H_{i-1}) = \Pr(T_i|T_{i-1}) = 3/4$ for all $i$, then this is a two-state homogeneous Markov chain. The transition matrix is

$$ P = \begin{pmatrix} 3/4 & 1/4 \\ 1/4 & 3/4 \end{pmatrix}. $$

This should get you started....

I'd comment but I don't have the rep, strangely you require 50.

Also, with regards to the bias in a coin flip, it's a paper by Diaconis:

http://statweb.stanford.edu/~susan/papers/headswithJ.pdf

$\endgroup$
3
$\begingroup$

Let $p_n$ be the probability that the coin is heads up after $n$ tosses. Then $p_0=1$ since it starts on heads, and $$p_n=\frac34p_{n-1}+\frac14(1-p_{n-1})$$ which simplifies to $$\left(p_n-\frac12\right)=\frac12\left(p_{n-1}-\frac12\right)\ .$$ Iterating, $$p_n-\frac12=\Bigl(\frac12\Bigr)^{n+1}$$ so $$p_n=\frac12+\Bigl(\frac12\Bigr)^{n+1}\ .$$

$\endgroup$
  • $\begingroup$ This no longer fails for $p_1 = \frac 3 4$. $\endgroup$ – Axoren May 24 '16 at 3:36
3
$\begingroup$

Another way of looking at it is to imagine that you toss two fair coins each time, using the second coin to choose between the first coin and the previous (originally heads). If the second coin always chooses the previous result then you end up with heads, while if at any point the second coin chooses the first coin then as this is fair the end result will have equal probability of being heads or tails. The chances of the latter being $1-\frac1{2^n}$, the chance of the final result being tails is therefore half of that.

$\endgroup$
  • $\begingroup$ This is the best possible solution for p=1/4 and I think it generalizes to all other values of p. $\endgroup$ – zyx May 24 '16 at 17:32
  • $\begingroup$ At least for p<1/2, where coin 2 has probability (1-2p) of choosing the previous result and coin 1 is fair. One gets half of $(1 - (1-2p)^n)$ which is correct. Other than changing the probability for coin 2, every word of the answer stays the same and the argument works. This answer is just brilliant. Well done. $\endgroup$ – zyx May 24 '16 at 17:49
1
$\begingroup$

$p_n(\text{heads}) = \frac 3 4p_{n-1}(\text{heads}) + \frac 1 4 (1 - p_{n-1}(\text{heads}))$

$p_n(\text{heads}) = \frac 1 4 + \frac 1 2p_{n-1}(\text{heads})$

$p_1(\text{heads}) = \frac 3 4$

Everyone else beat me too it. Was still writing the recurrence relation. :\

$\endgroup$
1
$\begingroup$

Any solution with the words "heads" and "tails" is doing extra work.

We want the chance of an odd number of reversals, each with probability $p=1/4$, to happen in $n$ independent trials. The coin briefly remembers its current state but not whether that state was reached by reversing on the previous trial. This makes the reversals independent of each other.

From the binomial theorem that probability is $$\frac{((1-p)+p)^n - ((1-p) - p)^n)}{2} = \frac{1}{2} - \frac{(1 - 2p)^n}{2}$$ which is consistent with the other solutions and shows that the $(1/2)^{n}$ exponential decay of the "memory" is really a power of $(1-2p)$.

$\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.