Mixing
Let $T$ be the number of tosses required until three consecutive heads appear for the first time. Find...
$begingroup$
A fair coin is tossed repeatedly. Let $A_{n}$ be the event that three heads have appeared in consecutive tosses for the first time on the $n$-th toss. Let $T$ be the number of tosses required until three consecutive heads appear for the first time. Find $textbf{P}(A_{n})$ and $textbf{E}(T)$.
Let $U$ be the number of tosses required until the sequence $HTH$ appears for the first time. Can you find $textbf{E}(U)$?
EDIT
The textbook provides an answer based on recurrence equations, but I seek for an alternative approach if it is possible. Can somebody please help me out? Thanks in advance.
probability probability-theory probability-distributions expected-value
asked Jan 18 at 19:04
user1337user1337
46110
$endgroup$
add a comment |
$begingroup$
A fair coin is tossed repeatedly. Let $A_{n}$ be the event that three heads have appeared in consecutive tosses for the first time on the $n$-th toss. Let $T$ be the number of tosses required until three consecutive heads appear for the first time. Find $textbf{P}(A_{n})$ and $textbf{E}(T)$.
Let $U$ be the number of tosses required until the sequence $HTH$ appears for the first time. Can you find $textbf{E}(U)$?
EDIT
The textbook provides an answer based on recurrence equations, but I seek for an alternative approach if it is possible. Can somebody please help me out? Thanks in advance.
probability probability-theory probability-distributions expected-value
asked Jan 18 at 19:04
user1337user1337
46110
$endgroup$
2
$begingroup$
$P(A_n) = P(T = n) = p^3(1-p)^{n-3}$, where $ngeq 3$. Here $p=0.5$. So then $E(T) = sumlimits_{n=3}^infty nP(T=n)$.
$endgroup$
– James Yang
Jan 18 at 19:19
$begingroup$
The displayed form of $A_n$ is not correct. It does not need to be all $T$-s before you get $3$ heads.
$endgroup$
– Hayk
Jan 18 at 19:21
$begingroup$
@JamesYang: That would be correct if we required $n-3$ tails followed by $3$ heads. I think we are allowed any starting string as long as the first occurrence of $HHH$ comes at the end.
$endgroup$
– Ross Millikan
Jan 18 at 19:21
$begingroup$
I see I totally missed that. Then the only other way is to use Markov chain I guess I was trying to avoid that for a simpler answer.
$endgroup$
– James Yang
Jan 18 at 19:25
$begingroup$
@JamesYang, Markov chains are not the only way. There is a straightforward approach through martingales, which gives the answer $14$ for the expected time.
$endgroup$
– Hayk
Jan 18 at 19:28
add a comment |
$begingroup$
A fair coin is tossed repeatedly. Let $A_{n}$ be the event that three heads have appeared in consecutive tosses for the first time on the $n$-th toss. Let $T$ be the number of tosses required until three consecutive heads appear for the first time. Find $textbf{P}(A_{n})$ and $textbf{E}(T)$.
Let $U$ be the number of tosses required until the sequence $HTH$ appears for the first time. Can you find $textbf{E}(U)$?
EDIT
The textbook provides an answer based on recurrence equations, but I seek for an alternative approach if it is possible. Can somebody please help me out? Thanks in advance.
probability probability-theory probability-distributions expected-value
asked Jan 18 at 19:04
user1337user1337
46110
$endgroup$
A fair coin is tossed repeatedly. Let $A_{n}$ be the event that three heads have appeared in consecutive tosses for the first time on the $n$-th toss. Let $T$ be the number of tosses required until three consecutive heads appear for the first time. Find $textbf{P}(A_{n})$ and $textbf{E}(T)$.
Let $U$ be the number of tosses required until the sequence $HTH$ appears for the first time. Can you find $textbf{E}(U)$?
EDIT
The textbook provides an answer based on recurrence equations, but I seek for an alternative approach if it is possible. Can somebody please help me out? Thanks in advance.
probability probability-theory probability-distributions expected-value
probability probability-theory probability-distributions expected-value
asked Jan 18 at 19:04
user1337user1337
46110
asked Jan 18 at 19:04
user1337user1337
46110
edited Jan 18 at 19:23
user1337
asked Jan 18 at 19:04
user1337user1337
46110
asked Jan 18 at 19:04
user1337user1337
46110
asked Jan 18 at 19:04
user1337user1337
46110
46110
2
$begingroup$
$P(A_n) = P(T = n) = p^3(1-p)^{n-3}$, where $ngeq 3$. Here $p=0.5$. So then $E(T) = sumlimits_{n=3}^infty nP(T=n)$.
$endgroup$
– James Yang
Jan 18 at 19:19
$begingroup$
The displayed form of $A_n$ is not correct. It does not need to be all $T$-s before you get $3$ heads.
$endgroup$
– Hayk
Jan 18 at 19:21
$begingroup$
@JamesYang: That would be correct if we required $n-3$ tails followed by $3$ heads. I think we are allowed any starting string as long as the first occurrence of $HHH$ comes at the end.
$endgroup$
– Ross Millikan
Jan 18 at 19:21
$begingroup$
I see I totally missed that. Then the only other way is to use Markov chain I guess I was trying to avoid that for a simpler answer.
$endgroup$
– James Yang
Jan 18 at 19:25
$begingroup$
@JamesYang, Markov chains are not the only way. There is a straightforward approach through martingales, which gives the answer $14$ for the expected time.
$endgroup$
– Hayk
Jan 18 at 19:28
add a comment |
2
$begingroup$
$P(A_n) = P(T = n) = p^3(1-p)^{n-3}$, where $ngeq 3$. Here $p=0.5$. So then $E(T) = sumlimits_{n=3}^infty nP(T=n)$.
$endgroup$
– James Yang
Jan 18 at 19:19
$begingroup$
The displayed form of $A_n$ is not correct. It does not need to be all $T$-s before you get $3$ heads.
$endgroup$
– Hayk
Jan 18 at 19:21
$begingroup$
@JamesYang: That would be correct if we required $n-3$ tails followed by $3$ heads. I think we are allowed any starting string as long as the first occurrence of $HHH$ comes at the end.
$endgroup$
– Ross Millikan
Jan 18 at 19:21
$begingroup$
I see I totally missed that. Then the only other way is to use Markov chain I guess I was trying to avoid that for a simpler answer.
$endgroup$
– James Yang
Jan 18 at 19:25
$begingroup$
@JamesYang, Markov chains are not the only way. There is a straightforward approach through martingales, which gives the answer $14$ for the expected time.
$endgroup$
– Hayk
Jan 18 at 19:28
2
2
$begingroup$
$P(A_n) = P(T = n) = p^3(1-p)^{n-3}$, where $ngeq 3$. Here $p=0.5$. So then $E(T) = sumlimits_{n=3}^infty nP(T=n)$.
$endgroup$
– James Yang
Jan 18 at 19:19
$begingroup$
$P(A_n) = P(T = n) = p^3(1-p)^{n-3}$, where $ngeq 3$. Here $p=0.5$. So then $E(T) = sumlimits_{n=3}^infty nP(T=n)$.
$endgroup$
– James Yang
Jan 18 at 19:19
$begingroup$
The displayed form of $A_n$ is not correct. It does not need to be all $T$-s before you get $3$ heads.
$endgroup$
– Hayk
Jan 18 at 19:21
$begingroup$
The displayed form of $A_n$ is not correct. It does not need to be all $T$-s before you get $3$ heads.
$endgroup$
– Hayk
Jan 18 at 19:21
$begingroup$
@JamesYang: That would be correct if we required $n-3$ tails followed by $3$ heads. I think we are allowed any starting string as long as the first occurrence of $HHH$ comes at the end.
$endgroup$
– Ross Millikan
Jan 18 at 19:21
$begingroup$
@JamesYang: That would be correct if we required $n-3$ tails followed by $3$ heads. I think we are allowed any starting string as long as the first occurrence of $HHH$ comes at the end.
$endgroup$
– Ross Millikan
Jan 18 at 19:21
$begingroup$
I see I totally missed that. Then the only other way is to use Markov chain I guess I was trying to avoid that for a simpler answer.
$endgroup$
– James Yang
Jan 18 at 19:25
$begingroup$
I see I totally missed that. Then the only other way is to use Markov chain I guess I was trying to avoid that for a simpler answer.
$endgroup$
– James Yang
Jan 18 at 19:25
$begingroup$
@JamesYang, Markov chains are not the only way. There is a straightforward approach through martingales, which gives the answer $14$ for the expected time.
$endgroup$
– Hayk
Jan 18 at 19:28
$begingroup$
@JamesYang, Markov chains are not the only way. There is a straightforward approach through martingales, which gives the answer $14$ for the expected time.
$endgroup$
– Hayk
Jan 18 at 19:28
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
What follows is a well-known approach to computing the expectation of $T$.
Consider the following gambling scheme: just before each time $nin mathbb{N}$ a new gambler arrives and bets $1$ $ that the $n$-th outcome of the coin toss is $H$. If the bet is correct the gambler wins $2$ (since the coin is fair) and bets it, the $2$, on the next outcome to be $H$ as well. Again, if the gambler win, he bets the fortune of $4$ on the next toss to be $H$. Winning that also, ends the game and leaves him with a fortune of $8$.
Now let $X_k^i$, where $kgeq 1$ and $i=1,2,3$ be the fortune of the $k$-th gambler after their $i$-th bet. For instance, the winner, if he was the $k$-th to enter the game, will have $X_k^1 = 2$, $X_k^2 = 2^2$ and $X_k^3 = 2^3$, while for all gamblers who did not make to the third from the last move, $X_k^i = 0$ for each $i=1,2,3$.
Define
$$
S_n = sum_{substack{k=1\i=1,2,3\ k + i leq n + 1}}^n X_k^i
$$
which is the total fortune of all gamblers after the $n$-th toss. Notice that exactly $n$ dollars were bet up to and including time $n$. Since the coin is fair and in view of our definition of $X_k^i$, it is easy to see that the sequence
$$
M_n: = S_n - n
$$
is a martingale with respect to the natural filtration generated by ${X_n}_{nin mathbb{N}}$. Define
$$
tau = inf{nin mathbb{N}: X_{n-2} X_{n-1} X_n = H H H },
$$
which is a stopping time, and defines the time when the game ends. We have $mathbb{E}(tau) <infty$. Indeed, the probability of getting $HHH$ on tosses $3k, 3k+1,3k+2$ equals $1/8$, hence dividing the interval of integers $[1,...,3k]$ to length $3$ intervals, it follows that the probability of NOT getting $HHH$ up to time $3k$ is bounded above by $1/8^k$. Thus $mathbb{P}(tau > 3k) leq 1/8^k$, hence the conclusion of $mathbb{E}(tau) < infty$.
Now, using the fact that $M_n$ has bounded increments and $tau$ has fininte expectation, we apply the optional stopping theorem to get $mathbb{E}M_tau = 0 $, thus
$$
0 = mathbb{E}M_tau = mathbb{E} S_tau - mathbb{E} tau.
$$
But observe, that at the time of finishing the game, i.e. at time $tau$, the only gamblers with non-zero fortunes are the winner, and the other two who entered the game at times $tau-1$ and $tau$ respectively. Each of these three gets $2^3$, $2^2$ and $2$, hence
$$
mathbb{E} tau = 2^3 + 2^2 + 2 = 14.
$$
For instance, using the same argument, it follows that for the pattern $HTH$, the expected time equals $2^3 + 2$.
See also this post for non-martingale approach to the above problem, which gives a combinatorial argument based on generator functions.
We can also get a formula for the probability of the event $A_n$. It was already mentioned in the other answer above that the event $A_n$ comprises of all sequence of length $n$ ending in $THHH$ and having at most $2$ consecutive $H$-s before time $n-4$.
Hence we need to compute the number of length $n$ sequences of ${H,T}$ with at most $2$ consecutive $H$. Denote this number by $a_n$.
Clearly $a_1 = 1$, $a_2 = 3 $, $a_3 = 5$. For $n>3$ we claim that
$$
tag{1} a_n = a_{n-1} + a_{n-2} + a_{n-3}.
$$
Indeed, each such sequence of length $n$ either ends in $H$ or $T$. If it ends with $T$, we have length $n-1$ remaining which can end in both $H$ and $T$, hence $a_{n-1}$ of such contributions. For sequences ending with $H$, we continue tracking the $n-1$-th position: if it's $H$, then the $n-2$-th needs to be $T$, hence $a_{n-3}$ of these, otherwise, if it's $T$, we are free to choose the $n-2$-th, thus we get $a_{n-2}$.
Since the set $A_n$, sequences of length $n$ where $HHH$ appears for the first time on step $n$ has the following structure:
$$
text{length } n-4 text{sequences of at most } 2 text{ Heads } text{ followed by } THHH,
$$
it follows
$$
mathbb{P}(A_n) = 2^{-n}a_{n-4},
$$
with $a_n$ as in $(1)$.
answered Jan 19 at 20:41
HaykHayk
2,6271214
$endgroup$
add a comment |
$begingroup$
Let $e$ be the expected number of tosses. Start tossing. If we get a tail immediately (probability $frac{1}{2}$) then the expected number is $e+1$. If we get a head then a tail (probability $frac{1}{4}$), then the expected number is $e+2$ If we get $2$ heads then a tail, the expected number is $e+3$. Finally, if our first $3$ tosses are heads, then the expected number is $3$. Thus
$$e=frac{1}{2}(e+1)+frac{1}{4}(e+2)+frac{1}{8}(e+3)+frac{1}{8}(3).$$
IF you solve the equation, you get $e = 14$.
Remark: emabraced the idea from Andre Nicolas's solution.
answered Jan 20 at 8:42
Satish RamanathanSatish Ramanathan
10k31323
$endgroup$
add a comment |
$begingroup$
You can't have $P(A_n)=2^{-n}$ for $n ge 3$ because the probabilities do not sum to $1$. It is true that $P(A_3)=frac 18$ because you need $HHH$ and $P(A_4)=frac 1{16}$ because you need $THHH$, but $P(A_5)=frac 1{16}$ because you win with both $TTHHH$ and $HTHHH$. For $n ge 5, A_n$ consists of a string of $n-4$ tosses that does not have three heads in a row followed by $THHH$. If you count the probability that you can have $n-4$ tosses without three heads in sequence the chance of $A_n$ is $frac 1{16}$ of this.
answered Jan 18 at 19:20
Ross MillikanRoss Millikan
298k23198371
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3078630%2flet-t-be-the-number-of-tosses-required-until-three-consecutive-heads-appear-fo%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
What follows is a well-known approach to computing the expectation of $T$.
Consider the following gambling scheme: just before each time $nin mathbb{N}$ a new gambler arrives and bets $1$ $ that the $n$-th outcome of the coin toss is $H$. If the bet is correct the gambler wins $2$ (since the coin is fair) and bets it, the $2$, on the next outcome to be $H$ as well. Again, if the gambler win, he bets the fortune of $4$ on the next toss to be $H$. Winning that also, ends the game and leaves him with a fortune of $8$.
Now let $X_k^i$, where $kgeq 1$ and $i=1,2,3$ be the fortune of the $k$-th gambler after their $i$-th bet. For instance, the winner, if he was the $k$-th to enter the game, will have $X_k^1 = 2$, $X_k^2 = 2^2$ and $X_k^3 = 2^3$, while for all gamblers who did not make to the third from the last move, $X_k^i = 0$ for each $i=1,2,3$.
Define
$$
S_n = sum_{substack{k=1\i=1,2,3\ k + i leq n + 1}}^n X_k^i
$$
which is the total fortune of all gamblers after the $n$-th toss. Notice that exactly $n$ dollars were bet up to and including time $n$. Since the coin is fair and in view of our definition of $X_k^i$, it is easy to see that the sequence
$$
M_n: = S_n - n
$$
is a martingale with respect to the natural filtration generated by ${X_n}_{nin mathbb{N}}$. Define
$$
tau = inf{nin mathbb{N}: X_{n-2} X_{n-1} X_n = H H H },
$$
which is a stopping time, and defines the time when the game ends. We have $mathbb{E}(tau) <infty$. Indeed, the probability of getting $HHH$ on tosses $3k, 3k+1,3k+2$ equals $1/8$, hence dividing the interval of integers $[1,...,3k]$ to length $3$ intervals, it follows that the probability of NOT getting $HHH$ up to time $3k$ is bounded above by $1/8^k$. Thus $mathbb{P}(tau > 3k) leq 1/8^k$, hence the conclusion of $mathbb{E}(tau) < infty$.
Now, using the fact that $M_n$ has bounded increments and $tau$ has fininte expectation, we apply the optional stopping theorem to get $mathbb{E}M_tau = 0 $, thus
$$
0 = mathbb{E}M_tau = mathbb{E} S_tau - mathbb{E} tau.
$$
But observe, that at the time of finishing the game, i.e. at time $tau$, the only gamblers with non-zero fortunes are the winner, and the other two who entered the game at times $tau-1$ and $tau$ respectively. Each of these three gets $2^3$, $2^2$ and $2$, hence
$$
mathbb{E} tau = 2^3 + 2^2 + 2 = 14.
$$
For instance, using the same argument, it follows that for the pattern $HTH$, the expected time equals $2^3 + 2$.
See also this post for non-martingale approach to the above problem, which gives a combinatorial argument based on generator functions.
We can also get a formula for the probability of the event $A_n$. It was already mentioned in the other answer above that the event $A_n$ comprises of all sequence of length $n$ ending in $THHH$ and having at most $2$ consecutive $H$-s before time $n-4$.
Hence we need to compute the number of length $n$ sequences of ${H,T}$ with at most $2$ consecutive $H$. Denote this number by $a_n$.
Clearly $a_1 = 1$, $a_2 = 3 $, $a_3 = 5$. For $n>3$ we claim that
$$
tag{1} a_n = a_{n-1} + a_{n-2} + a_{n-3}.
$$
Indeed, each such sequence of length $n$ either ends in $H$ or $T$. If it ends with $T$, we have length $n-1$ remaining which can end in both $H$ and $T$, hence $a_{n-1}$ of such contributions. For sequences ending with $H$, we continue tracking the $n-1$-th position: if it's $H$, then the $n-2$-th needs to be $T$, hence $a_{n-3}$ of these, otherwise, if it's $T$, we are free to choose the $n-2$-th, thus we get $a_{n-2}$.
Since the set $A_n$, sequences of length $n$ where $HHH$ appears for the first time on step $n$ has the following structure:
$$
text{length } n-4 text{sequences of at most } 2 text{ Heads } text{ followed by } THHH,
$$
it follows
$$
mathbb{P}(A_n) = 2^{-n}a_{n-4},
$$
with $a_n$ as in $(1)$.
answered Jan 19 at 20:41
HaykHayk
2,6271214
$endgroup$
add a comment |
$begingroup$
What follows is a well-known approach to computing the expectation of $T$.
Consider the following gambling scheme: just before each time $nin mathbb{N}$ a new gambler arrives and bets $1$ $ that the $n$-th outcome of the coin toss is $H$. If the bet is correct the gambler wins $2$ (since the coin is fair) and bets it, the $2$, on the next outcome to be $H$ as well. Again, if the gambler win, he bets the fortune of $4$ on the next toss to be $H$. Winning that also, ends the game and leaves him with a fortune of $8$.
Now let $X_k^i$, where $kgeq 1$ and $i=1,2,3$ be the fortune of the $k$-th gambler after their $i$-th bet. For instance, the winner, if he was the $k$-th to enter the game, will have $X_k^1 = 2$, $X_k^2 = 2^2$ and $X_k^3 = 2^3$, while for all gamblers who did not make to the third from the last move, $X_k^i = 0$ for each $i=1,2,3$.
Define
$$
S_n = sum_{substack{k=1\i=1,2,3\ k + i leq n + 1}}^n X_k^i
$$
which is the total fortune of all gamblers after the $n$-th toss. Notice that exactly $n$ dollars were bet up to and including time $n$. Since the coin is fair and in view of our definition of $X_k^i$, it is easy to see that the sequence
$$
M_n: = S_n - n
$$
is a martingale with respect to the natural filtration generated by ${X_n}_{nin mathbb{N}}$. Define
$$
tau = inf{nin mathbb{N}: X_{n-2} X_{n-1} X_n = H H H },
$$
which is a stopping time, and defines the time when the game ends. We have $mathbb{E}(tau) <infty$. Indeed, the probability of getting $HHH$ on tosses $3k, 3k+1,3k+2$ equals $1/8$, hence dividing the interval of integers $[1,...,3k]$ to length $3$ intervals, it follows that the probability of NOT getting $HHH$ up to time $3k$ is bounded above by $1/8^k$. Thus $mathbb{P}(tau > 3k) leq 1/8^k$, hence the conclusion of $mathbb{E}(tau) < infty$.
Now, using the fact that $M_n$ has bounded increments and $tau$ has fininte expectation, we apply the optional stopping theorem to get $mathbb{E}M_tau = 0 $, thus
$$
0 = mathbb{E}M_tau = mathbb{E} S_tau - mathbb{E} tau.
$$
But observe, that at the time of finishing the game, i.e. at time $tau$, the only gamblers with non-zero fortunes are the winner, and the other two who entered the game at times $tau-1$ and $tau$ respectively. Each of these three gets $2^3$, $2^2$ and $2$, hence
$$
mathbb{E} tau = 2^3 + 2^2 + 2 = 14.
$$
For instance, using the same argument, it follows that for the pattern $HTH$, the expected time equals $2^3 + 2$.
See also this post for non-martingale approach to the above problem, which gives a combinatorial argument based on generator functions.
We can also get a formula for the probability of the event $A_n$. It was already mentioned in the other answer above that the event $A_n$ comprises of all sequence of length $n$ ending in $THHH$ and having at most $2$ consecutive $H$-s before time $n-4$.
Hence we need to compute the number of length $n$ sequences of ${H,T}$ with at most $2$ consecutive $H$. Denote this number by $a_n$.
Clearly $a_1 = 1$, $a_2 = 3 $, $a_3 = 5$. For $n>3$ we claim that
$$
tag{1} a_n = a_{n-1} + a_{n-2} + a_{n-3}.
$$
Indeed, each such sequence of length $n$ either ends in $H$ or $T$. If it ends with $T$, we have length $n-1$ remaining which can end in both $H$ and $T$, hence $a_{n-1}$ of such contributions. For sequences ending with $H$, we continue tracking the $n-1$-th position: if it's $H$, then the $n-2$-th needs to be $T$, hence $a_{n-3}$ of these, otherwise, if it's $T$, we are free to choose the $n-2$-th, thus we get $a_{n-2}$.
Since the set $A_n$, sequences of length $n$ where $HHH$ appears for the first time on step $n$ has the following structure:
$$
text{length } n-4 text{sequences of at most } 2 text{ Heads } text{ followed by } THHH,
$$
it follows
$$
mathbb{P}(A_n) = 2^{-n}a_{n-4},
$$
with $a_n$ as in $(1)$.
answered Jan 19 at 20:41
HaykHayk
2,6271214
$endgroup$
add a comment |
$begingroup$
What follows is a well-known approach to computing the expectation of $T$.
Consider the following gambling scheme: just before each time $nin mathbb{N}$ a new gambler arrives and bets $1$ $ that the $n$-th outcome of the coin toss is $H$. If the bet is correct the gambler wins $2$ (since the coin is fair) and bets it, the $2$, on the next outcome to be $H$ as well. Again, if the gambler win, he bets the fortune of $4$ on the next toss to be $H$. Winning that also, ends the game and leaves him with a fortune of $8$.
Now let $X_k^i$, where $kgeq 1$ and $i=1,2,3$ be the fortune of the $k$-th gambler after their $i$-th bet. For instance, the winner, if he was the $k$-th to enter the game, will have $X_k^1 = 2$, $X_k^2 = 2^2$ and $X_k^3 = 2^3$, while for all gamblers who did not make to the third from the last move, $X_k^i = 0$ for each $i=1,2,3$.
Define
$$
S_n = sum_{substack{k=1\i=1,2,3\ k + i leq n + 1}}^n X_k^i
$$
which is the total fortune of all gamblers after the $n$-th toss. Notice that exactly $n$ dollars were bet up to and including time $n$. Since the coin is fair and in view of our definition of $X_k^i$, it is easy to see that the sequence
$$
M_n: = S_n - n
$$
is a martingale with respect to the natural filtration generated by ${X_n}_{nin mathbb{N}}$. Define
$$
tau = inf{nin mathbb{N}: X_{n-2} X_{n-1} X_n = H H H },
$$
which is a stopping time, and defines the time when the game ends. We have $mathbb{E}(tau) <infty$. Indeed, the probability of getting $HHH$ on tosses $3k, 3k+1,3k+2$ equals $1/8$, hence dividing the interval of integers $[1,...,3k]$ to length $3$ intervals, it follows that the probability of NOT getting $HHH$ up to time $3k$ is bounded above by $1/8^k$. Thus $mathbb{P}(tau > 3k) leq 1/8^k$, hence the conclusion of $mathbb{E}(tau) < infty$.
Now, using the fact that $M_n$ has bounded increments and $tau$ has fininte expectation, we apply the optional stopping theorem to get $mathbb{E}M_tau = 0 $, thus
$$
0 = mathbb{E}M_tau = mathbb{E} S_tau - mathbb{E} tau.
$$
But observe, that at the time of finishing the game, i.e. at time $tau$, the only gamblers with non-zero fortunes are the winner, and the other two who entered the game at times $tau-1$ and $tau$ respectively. Each of these three gets $2^3$, $2^2$ and $2$, hence
$$
mathbb{E} tau = 2^3 + 2^2 + 2 = 14.
$$
For instance, using the same argument, it follows that for the pattern $HTH$, the expected time equals $2^3 + 2$.
See also this post for non-martingale approach to the above problem, which gives a combinatorial argument based on generator functions.
We can also get a formula for the probability of the event $A_n$. It was already mentioned in the other answer above that the event $A_n$ comprises of all sequence of length $n$ ending in $THHH$ and having at most $2$ consecutive $H$-s before time $n-4$.
Hence we need to compute the number of length $n$ sequences of ${H,T}$ with at most $2$ consecutive $H$. Denote this number by $a_n$.
Clearly $a_1 = 1$, $a_2 = 3 $, $a_3 = 5$. For $n>3$ we claim that
$$
tag{1} a_n = a_{n-1} + a_{n-2} + a_{n-3}.
$$
Indeed, each such sequence of length $n$ either ends in $H$ or $T$. If it ends with $T$, we have length $n-1$ remaining which can end in both $H$ and $T$, hence $a_{n-1}$ of such contributions. For sequences ending with $H$, we continue tracking the $n-1$-th position: if it's $H$, then the $n-2$-th needs to be $T$, hence $a_{n-3}$ of these, otherwise, if it's $T$, we are free to choose the $n-2$-th, thus we get $a_{n-2}$.
Since the set $A_n$, sequences of length $n$ where $HHH$ appears for the first time on step $n$ has the following structure:
$$
text{length } n-4 text{sequences of at most } 2 text{ Heads } text{ followed by } THHH,
$$
it follows
$$
mathbb{P}(A_n) = 2^{-n}a_{n-4},
$$
with $a_n$ as in $(1)$.
answered Jan 19 at 20:41
HaykHayk
2,6271214
$endgroup$
What follows is a well-known approach to computing the expectation of $T$.
Consider the following gambling scheme: just before each time $nin mathbb{N}$ a new gambler arrives and bets $1$ $ that the $n$-th outcome of the coin toss is $H$. If the bet is correct the gambler wins $2$ (since the coin is fair) and bets it, the $2$, on the next outcome to be $H$ as well. Again, if the gambler win, he bets the fortune of $4$ on the next toss to be $H$. Winning that also, ends the game and leaves him with a fortune of $8$.
Now let $X_k^i$, where $kgeq 1$ and $i=1,2,3$ be the fortune of the $k$-th gambler after their $i$-th bet. For instance, the winner, if he was the $k$-th to enter the game, will have $X_k^1 = 2$, $X_k^2 = 2^2$ and $X_k^3 = 2^3$, while for all gamblers who did not make to the third from the last move, $X_k^i = 0$ for each $i=1,2,3$.
Define
$$
S_n = sum_{substack{k=1\i=1,2,3\ k + i leq n + 1}}^n X_k^i
$$
which is the total fortune of all gamblers after the $n$-th toss. Notice that exactly $n$ dollars were bet up to and including time $n$. Since the coin is fair and in view of our definition of $X_k^i$, it is easy to see that the sequence
$$
M_n: = S_n - n
$$
is a martingale with respect to the natural filtration generated by ${X_n}_{nin mathbb{N}}$. Define
$$
tau = inf{nin mathbb{N}: X_{n-2} X_{n-1} X_n = H H H },
$$
which is a stopping time, and defines the time when the game ends. We have $mathbb{E}(tau) <infty$. Indeed, the probability of getting $HHH$ on tosses $3k, 3k+1,3k+2$ equals $1/8$, hence dividing the interval of integers $[1,...,3k]$ to length $3$ intervals, it follows that the probability of NOT getting $HHH$ up to time $3k$ is bounded above by $1/8^k$. Thus $mathbb{P}(tau > 3k) leq 1/8^k$, hence the conclusion of $mathbb{E}(tau) < infty$.
Now, using the fact that $M_n$ has bounded increments and $tau$ has fininte expectation, we apply the optional stopping theorem to get $mathbb{E}M_tau = 0 $, thus
$$
0 = mathbb{E}M_tau = mathbb{E} S_tau - mathbb{E} tau.
$$
But observe, that at the time of finishing the game, i.e. at time $tau$, the only gamblers with non-zero fortunes are the winner, and the other two who entered the game at times $tau-1$ and $tau$ respectively. Each of these three gets $2^3$, $2^2$ and $2$, hence
$$
mathbb{E} tau = 2^3 + 2^2 + 2 = 14.
$$
For instance, using the same argument, it follows that for the pattern $HTH$, the expected time equals $2^3 + 2$.
See also this post for non-martingale approach to the above problem, which gives a combinatorial argument based on generator functions.
We can also get a formula for the probability of the event $A_n$. It was already mentioned in the other answer above that the event $A_n$ comprises of all sequence of length $n$ ending in $THHH$ and having at most $2$ consecutive $H$-s before time $n-4$.
Hence we need to compute the number of length $n$ sequences of ${H,T}$ with at most $2$ consecutive $H$. Denote this number by $a_n$.
Clearly $a_1 = 1$, $a_2 = 3 $, $a_3 = 5$. For $n>3$ we claim that
$$
tag{1} a_n = a_{n-1} + a_{n-2} + a_{n-3}.
$$
Indeed, each such sequence of length $n$ either ends in $H$ or $T$. If it ends with $T$, we have length $n-1$ remaining which can end in both $H$ and $T$, hence $a_{n-1}$ of such contributions. For sequences ending with $H$, we continue tracking the $n-1$-th position: if it's $H$, then the $n-2$-th needs to be $T$, hence $a_{n-3}$ of these, otherwise, if it's $T$, we are free to choose the $n-2$-th, thus we get $a_{n-2}$.
Since the set $A_n$, sequences of length $n$ where $HHH$ appears for the first time on step $n$ has the following structure:
$$
text{length } n-4 text{sequences of at most } 2 text{ Heads } text{ followed by } THHH,
$$
it follows
$$
mathbb{P}(A_n) = 2^{-n}a_{n-4},
$$
with $a_n$ as in $(1)$.
answered Jan 19 at 20:41
HaykHayk
2,6271214
edited Jan 21 at 12:29
answered Jan 19 at 20:41
HaykHayk
2,6271214
answered Jan 19 at 20:41
HaykHayk
2,6271214
answered Jan 19 at 20:41
HaykHayk
2,6271214
2,6271214
add a comment |
add a comment |
$begingroup$
Let $e$ be the expected number of tosses. Start tossing. If we get a tail immediately (probability $frac{1}{2}$) then the expected number is $e+1$. If we get a head then a tail (probability $frac{1}{4}$), then the expected number is $e+2$ If we get $2$ heads then a tail, the expected number is $e+3$. Finally, if our first $3$ tosses are heads, then the expected number is $3$. Thus
$$e=frac{1}{2}(e+1)+frac{1}{4}(e+2)+frac{1}{8}(e+3)+frac{1}{8}(3).$$
IF you solve the equation, you get $e = 14$.
Remark: emabraced the idea from Andre Nicolas's solution.
answered Jan 20 at 8:42
Satish RamanathanSatish Ramanathan
10k31323
$endgroup$
add a comment |
$begingroup$
Let $e$ be the expected number of tosses. Start tossing. If we get a tail immediately (probability $frac{1}{2}$) then the expected number is $e+1$. If we get a head then a tail (probability $frac{1}{4}$), then the expected number is $e+2$ If we get $2$ heads then a tail, the expected number is $e+3$. Finally, if our first $3$ tosses are heads, then the expected number is $3$. Thus
$$e=frac{1}{2}(e+1)+frac{1}{4}(e+2)+frac{1}{8}(e+3)+frac{1}{8}(3).$$
IF you solve the equation, you get $e = 14$.
Remark: emabraced the idea from Andre Nicolas's solution.
answered Jan 20 at 8:42
Satish RamanathanSatish Ramanathan
10k31323
$endgroup$
add a comment |
$begingroup$
Let $e$ be the expected number of tosses. Start tossing. If we get a tail immediately (probability $frac{1}{2}$) then the expected number is $e+1$. If we get a head then a tail (probability $frac{1}{4}$), then the expected number is $e+2$ If we get $2$ heads then a tail, the expected number is $e+3$. Finally, if our first $3$ tosses are heads, then the expected number is $3$. Thus
$$e=frac{1}{2}(e+1)+frac{1}{4}(e+2)+frac{1}{8}(e+3)+frac{1}{8}(3).$$
IF you solve the equation, you get $e = 14$.
Remark: emabraced the idea from Andre Nicolas's solution.
answered Jan 20 at 8:42
Satish RamanathanSatish Ramanathan
10k31323
$endgroup$
Let $e$ be the expected number of tosses. Start tossing. If we get a tail immediately (probability $frac{1}{2}$) then the expected number is $e+1$. If we get a head then a tail (probability $frac{1}{4}$), then the expected number is $e+2$ If we get $2$ heads then a tail, the expected number is $e+3$. Finally, if our first $3$ tosses are heads, then the expected number is $3$. Thus
$$e=frac{1}{2}(e+1)+frac{1}{4}(e+2)+frac{1}{8}(e+3)+frac{1}{8}(3).$$
IF you solve the equation, you get $e = 14$.
Remark: emabraced the idea from Andre Nicolas's solution.
answered Jan 20 at 8:42
Satish RamanathanSatish Ramanathan
10k31323
answered Jan 20 at 8:42
Satish RamanathanSatish Ramanathan
10k31323
answered Jan 20 at 8:42
Satish RamanathanSatish Ramanathan
10k31323
answered Jan 20 at 8:42
Satish RamanathanSatish Ramanathan
10k31323
10k31323
add a comment |
add a comment |
$begingroup$
You can't have $P(A_n)=2^{-n}$ for $n ge 3$ because the probabilities do not sum to $1$. It is true that $P(A_3)=frac 18$ because you need $HHH$ and $P(A_4)=frac 1{16}$ because you need $THHH$, but $P(A_5)=frac 1{16}$ because you win with both $TTHHH$ and $HTHHH$. For $n ge 5, A_n$ consists of a string of $n-4$ tosses that does not have three heads in a row followed by $THHH$. If you count the probability that you can have $n-4$ tosses without three heads in sequence the chance of $A_n$ is $frac 1{16}$ of this.
answered Jan 18 at 19:20
Ross MillikanRoss Millikan
298k23198371
$endgroup$
add a comment |
$begingroup$
You can't have $P(A_n)=2^{-n}$ for $n ge 3$ because the probabilities do not sum to $1$. It is true that $P(A_3)=frac 18$ because you need $HHH$ and $P(A_4)=frac 1{16}$ because you need $THHH$, but $P(A_5)=frac 1{16}$ because you win with both $TTHHH$ and $HTHHH$. For $n ge 5, A_n$ consists of a string of $n-4$ tosses that does not have three heads in a row followed by $THHH$. If you count the probability that you can have $n-4$ tosses without three heads in sequence the chance of $A_n$ is $frac 1{16}$ of this.
answered Jan 18 at 19:20
Ross MillikanRoss Millikan
298k23198371
$endgroup$
add a comment |
$begingroup$
You can't have $P(A_n)=2^{-n}$ for $n ge 3$ because the probabilities do not sum to $1$. It is true that $P(A_3)=frac 18$ because you need $HHH$ and $P(A_4)=frac 1{16}$ because you need $THHH$, but $P(A_5)=frac 1{16}$ because you win with both $TTHHH$ and $HTHHH$. For $n ge 5, A_n$ consists of a string of $n-4$ tosses that does not have three heads in a row followed by $THHH$. If you count the probability that you can have $n-4$ tosses without three heads in sequence the chance of $A_n$ is $frac 1{16}$ of this.
answered Jan 18 at 19:20
Ross MillikanRoss Millikan
298k23198371
$endgroup$
You can't have $P(A_n)=2^{-n}$ for $n ge 3$ because the probabilities do not sum to $1$. It is true that $P(A_3)=frac 18$ because you need $HHH$ and $P(A_4)=frac 1{16}$ because you need $THHH$, but $P(A_5)=frac 1{16}$ because you win with both $TTHHH$ and $HTHHH$. For $n ge 5, A_n$ consists of a string of $n-4$ tosses that does not have three heads in a row followed by $THHH$. If you count the probability that you can have $n-4$ tosses without three heads in sequence the chance of $A_n$ is $frac 1{16}$ of this.
answered Jan 18 at 19:20
Ross MillikanRoss Millikan
298k23198371
answered Jan 18 at 19:20
Ross MillikanRoss Millikan
298k23198371
answered Jan 18 at 19:20
Ross MillikanRoss Millikan
298k23198371
answered Jan 18 at 19:20
Ross MillikanRoss Millikan
298k23198371
298k23198371
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3078630%2flet-t-be-the-number-of-tosses-required-until-three-consecutive-heads-appear-fo%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
$P(A_n) = P(T = n) = p^3(1-p)^{n-3}$, where $ngeq 3$. Here $p=0.5$. So then $E(T) = sumlimits_{n=3}^infty nP(T=n)$.
$endgroup$
– James Yang
Jan 18 at 19:19
$begingroup$
The displayed form of $A_n$ is not correct. It does not need to be all $T$-s before you get $3$ heads.
$endgroup$
– Hayk
Jan 18 at 19:21
$begingroup$
@JamesYang: That would be correct if we required $n-3$ tails followed by $3$ heads. I think we are allowed any starting string as long as the first occurrence of $HHH$ comes at the end.
$endgroup$
– Ross Millikan
Jan 18 at 19:21
$begingroup$
I see I totally missed that. Then the only other way is to use Markov chain I guess I was trying to avoid that for a simpler answer.
$endgroup$
– James Yang
Jan 18 at 19:25
$begingroup$
@JamesYang, Markov chains are not the only way. There is a straightforward approach through martingales, which gives the answer $14$ for the expected time.
$endgroup$
– Hayk
Jan 18 at 19:28