Flip a coin. If tails, your next flip is guaranteed to be heads.

[Eraser]

Question: flip a fair coin. If tails, your next flip is guaranteed to be heads. If heads, your next flip is fair. If you flip this coin an arbitrarily large number of times, what portion of your flips are heads?

First, I know that the answer must be greater than 0.5; even if we get tails on every fair flip, the number of heads will never drop below 0.5. But beyond that I'm not sure how to approach this problem. I drew a tree below, showing the number of heads on each flip. It seems to approach 0.7, but I don't know how to prove that algebraically.

 

[BigBeachBanana]

Question: flip a fair coin. If tails, your next flip is guaranteed to be heads. If heads, your next flip is fair. If you flip this coin an arbitrarily large number of times, what portion of your flips are heads?

First, I know that the answer must be greater than 0.5; even if we get tails on every fair flip, the number of heads will never drop below 0.5. But beyond that I'm not sure how to approach this problem. I drew a tree below, showing the number of heads on each flip. It seems to approach 0.7, but I don't know how to prove that algebraically.

How much do you know about Markov Chain and Discrete Stochastic Processes?
Please provide more background knowledge and how did you come across this question?

 

[Steven G]

First, I know that the answer must be greater than 0.5; even if we get tails on every fair flip, the number of heads will never drop below 0.5

Sorry, but I don't agree with that statement.
Suppose I start off tossing a T. Then next is H. Then a "fair" toss resulting in T. Then H. Then a "fair" toss resulting in T. Then H, then T, then H...

This sequence is T H T H T H T H T H T ....
Why is the number of heads greater than .5??

Not a big deal, but I don't think that you should start off by saying this is a fair coin.

 

[Dr.Peterson]

Question: flip a fair coin. If tails, your next flip is guaranteed to be heads. If heads, your next flip is fair. If you flip this coin an arbitrarily large number of times, what portion of your flips are heads?

First, I know that the answer must be greater than 0.5; even if we get tails on every fair flip, the number of heads will never drop below 0.5. But beyond that I'm not sure how to approach this problem. I drew a tree below, showing the number of heads on each flip. It seems to approach 0.7, but I don't know how to prove that algebraically.

I don't see how a flip of a fair coin can be guaranteed to he heads! I am interpreting this as saying that we use a fair coin except when we just got tails, in which case we either flip a two-headed coin instead, or just write down heads instead of the next flip.

Anyway, when I make a tree showing just the results of each flip, the rows look like
T H = 1 H, 1 T H T H = 1 T, 2 H H T H H T = 2 T, 3 H H T H H T H T H = 3 T, 5 H
What I notice is that the numbers (and the totals) are all Fibonacci numbers, which suggests not only a possible answer, but a recursion to try in order to see if my guess is valid.

 

[Steven G]

Dr Peterson,
I am unclear as to why you have only this particular outcomes.
Why not also include THH, HTHT, HTHHTHHH?
It seems as though you made your list follow Fibonacci numbers.
Can you please explain?

 

[BigBeachBanana]

Question: flip a fair coin. If tails, your next flip is guaranteed to be heads. If heads, your next flip is fair. If you flip this coin an arbitrarily large number of times, what portion of your flips are heads?

First, I know that the answer must be greater than 0.5; even if we get tails on every fair flip, the number of heads will never drop below 0.5. But beyond that I'm not sure how to approach this problem. I drew a tree below, showing the number of heads on each flip. It seems to approach 0.7, but I don't know how to prove that algebraically.

This is a Discrete-time Markov Chain process in which the value of the next variable depends only on the value of the current variable; but not any of the past. We can denote the outcomes of the chain of events as [imath]X_0, X_1,\dots, X_n,\dots[/imath] where [imath]X_0 = [0.5~~0.5][/imath] is the initial state of the when the process starts which we were told to have equally likely outcomes (fair coin) and [imath]X_n[/imath] is the outcome of after [imath]n[/imath] transitions (flips). This process continues indefinitely.

To discuss the long-term behavior of a Discrete Markov Chain, we wish to know the fraction of time the chain spends in each state (Head or Tail) as [imath]n[/imath] becomes large a.k.a the Limiting Distribution commonly denoted by [imath]\pi = [\pi_H~~\pi_T][/imath]; where [imath]\pi_H[/imath] is the fraction of time the process came up head, and [imath]\pi_T[/imath] is the fraction of time the process came up as tail. Naturally, [imath]\pi_H + \pi_T = 1[/imath].
More formally,
[math]\pi_i = \lim_{n\to \infty} \Pr(X_n = i)[/math]
How much do you already know?

 

[Dr.Peterson]

Dr Peterson,
I am unclear as to why you have only this particular outcomes.
Why not also include THH, HTHT, HTHHTHHH?
It seems as though you made your list follow Fibonacci numbers.
Can you please explain?

Anyway, when I make a tree showing just the results of each flip, the rows look like
H T = 1 H, 1 T H T H = 1 T, 2 H H T H H T = 2 T, 3 H H T H H T H T H = 3 T, 5 H

These are single rows in the tree, not chains of successive flips -- that is, only what is circled here:



(I have the rows reversed from what he showed, because I took H first.)

This is how I think of such trees, showing just the outcome at each step, so there is less writing. I've never made a tree the way the OP did.

And, no, I didn't have the numbers in mind before making my tree.

 

[BigBeachBanana]

It has been more than 4 days and the OP has not returned. I won't disclose the solution in case the OP takes an interest in the thread again.

For those who are curious, if you flip this coin an arbitrarily large number of times, 2/3 of the time would be expected to show up head.

 

[Eraser]

This sequence is T H T H T H T H T H T ....
Why is the number of heads greater than .5??

Not a bit deal, but I don't think that you should start off by saying this is a fair coin.

The coin is only fair under certain conditions. The coin is fair at the beginning, and after every Heads. But immediately after tails, the next flip will by a Heads. and then after that heads, it will be fair again.

Getting "T H T H T H T H..." is technically possible, but this is very unlikely. It is the worst possible case. I'm trying to find the average case, which must be higher than the worst case.

 

[Eraser]

This is a Discrete-time Markov Chain process

How much do you already know?

Thank you for the info. I've just done some research and I came up with this:

The problem can be rewritten as a Markov Chain with two states: H and T. It looks like the graph shown below. Then we can use linear algebra to find the stationary distribution. To do this, we represent the graph as an adjacency matrix A. We solve for the eigenvector π. Then we scale π so that π[0] + π[1] equals 1. You can see my work in the picture.

According to the stationary distribution, the state of the system after an arbitrarily large number of coin flips will be heads 2/3 of the time.

 

[BigBeachBanana]

Thank you for the info. I've just done some research and I came up with this:

The problem can be rewritten as a Markov Chain with two states: H and T. It looks like the graph shown below. Then we can use linear algebra to find the stationary distribution. To do this, we represent the graph as an adjacency matrix A. We solve for the eigenvector π. Then we scale π so that π[0] + π[1] equals 1. You can see my work in the picture.

According to the stationary distribution, the state of the system after an arbitrarily large number of coin flips will be heads 2/3 of the time.

Your matrix A is incorrect. All the rows should add up to 1.
[math]\pi = \pi A[/math][math] [\pi_0~~\pi_1] = [\pi_0~~\pi_1] \begin{bmatrix} 0.5 & 0.5 \\ 1 & 0 \end{bmatrix}\\ [\pi_0~~\pi_1] = [0.5\pi_0 + \pi_1 \quad 0.5\pi_0] [/math]This gives us 2 of the same equation [imath]\pi_1 = 0.5\pi_0[/imath]
However, with the condition [imath]\pi_0 + \pi_1 = 1[/imath], the system gives us [imath]\pi_0 = \dfrac{1}{1.5} = \dfrac{2}{3}[/imath].