Probability that First $s$ Heads in a Row Occurs After $n$ Flips
$begingroup$
Flip a coin repeatedly. Let $E_s$ be the number of coin flips it takes before seeing $s$ heads in a row. What is $P(E_s=n)$? Specifically, I am concerned with $P(E_4=E_3+k)$ (specifically for $k=1,9$) but to calculate this I find that
$$begin{aligned}
P(E_4=E_3+k) &= sum_{n=3}^{infty}P(E_3=n;land; E_4=n+k) \
&= sum_{n=3}^{infty}P(E_4=n+k;|; E_3=n)P(E_3=n) \
&= sum_{n=3}^{infty}left(begin{cases}1/2& k=1 \
P(E_4=k-1)& kge 4 \
0 & 1<k<4
end{cases}right)P(E_3=n) \
&= begin{cases}1/2& k=1 \
P(E_4=k-1)& kge 4 \
0 & 1<k<4
end{cases}
end{aligned}$$
where on the last line since $E_sin [s,infty]$ so $1=P(E_s=infty)+sum_{n=s}^{infty}P(E_s=n)=sum_{n=s}^{infty}P(E_s=n)$. Thus, we are left having to calculate $P(E_4=k-1)$. Is the work for my specific case correct? And if so how do we finish the problem, or is there a method that avoid direct calculation?
probability
asked Dec 2 '18 at 15:50
Will FisherWill Fisher
4,0331032
$endgroup$
add a comment |
$begingroup$
Flip a coin repeatedly. Let $E_s$ be the number of coin flips it takes before seeing $s$ heads in a row. What is $P(E_s=n)$? Specifically, I am concerned with $P(E_4=E_3+k)$ (specifically for $k=1,9$) but to calculate this I find that
$$begin{aligned}
P(E_4=E_3+k) &= sum_{n=3}^{infty}P(E_3=n;land; E_4=n+k) \
&= sum_{n=3}^{infty}P(E_4=n+k;|; E_3=n)P(E_3=n) \
&= sum_{n=3}^{infty}left(begin{cases}1/2& k=1 \
P(E_4=k-1)& kge 4 \
0 & 1<k<4
end{cases}right)P(E_3=n) \
&= begin{cases}1/2& k=1 \
P(E_4=k-1)& kge 4 \
0 & 1<k<4
end{cases}
end{aligned}$$
where on the last line since $E_sin [s,infty]$ so $1=P(E_s=infty)+sum_{n=s}^{infty}P(E_s=n)=sum_{n=s}^{infty}P(E_s=n)$. Thus, we are left having to calculate $P(E_4=k-1)$. Is the work for my specific case correct? And if so how do we finish the problem, or is there a method that avoid direct calculation?
probability
asked Dec 2 '18 at 15:50
Will FisherWill Fisher
4,0331032
$endgroup$
add a comment |
$begingroup$
Flip a coin repeatedly. Let $E_s$ be the number of coin flips it takes before seeing $s$ heads in a row. What is $P(E_s=n)$? Specifically, I am concerned with $P(E_4=E_3+k)$ (specifically for $k=1,9$) but to calculate this I find that
$$begin{aligned}
P(E_4=E_3+k) &= sum_{n=3}^{infty}P(E_3=n;land; E_4=n+k) \
&= sum_{n=3}^{infty}P(E_4=n+k;|; E_3=n)P(E_3=n) \
&= sum_{n=3}^{infty}left(begin{cases}1/2& k=1 \
P(E_4=k-1)& kge 4 \
0 & 1<k<4
end{cases}right)P(E_3=n) \
&= begin{cases}1/2& k=1 \
P(E_4=k-1)& kge 4 \
0 & 1<k<4
end{cases}
end{aligned}$$
where on the last line since $E_sin [s,infty]$ so $1=P(E_s=infty)+sum_{n=s}^{infty}P(E_s=n)=sum_{n=s}^{infty}P(E_s=n)$. Thus, we are left having to calculate $P(E_4=k-1)$. Is the work for my specific case correct? And if so how do we finish the problem, or is there a method that avoid direct calculation?
probability
asked Dec 2 '18 at 15:50
Will FisherWill Fisher
4,0331032
$endgroup$
Flip a coin repeatedly. Let $E_s$ be the number of coin flips it takes before seeing $s$ heads in a row. What is $P(E_s=n)$? Specifically, I am concerned with $P(E_4=E_3+k)$ (specifically for $k=1,9$) but to calculate this I find that
$$begin{aligned}
P(E_4=E_3+k) &= sum_{n=3}^{infty}P(E_3=n;land; E_4=n+k) \
&= sum_{n=3}^{infty}P(E_4=n+k;|; E_3=n)P(E_3=n) \
&= sum_{n=3}^{infty}left(begin{cases}1/2& k=1 \
P(E_4=k-1)& kge 4 \
0 & 1<k<4
end{cases}right)P(E_3=n) \
&= begin{cases}1/2& k=1 \
P(E_4=k-1)& kge 4 \
0 & 1<k<4
end{cases}
end{aligned}$$
where on the last line since $E_sin [s,infty]$ so $1=P(E_s=infty)+sum_{n=s}^{infty}P(E_s=n)=sum_{n=s}^{infty}P(E_s=n)$. Thus, we are left having to calculate $P(E_4=k-1)$. Is the work for my specific case correct? And if so how do we finish the problem, or is there a method that avoid direct calculation?
probability
probability
asked Dec 2 '18 at 15:50
Will FisherWill Fisher
4,0331032
asked Dec 2 '18 at 15:50
Will FisherWill Fisher
4,0331032
edited Dec 2 '18 at 16:35
Will Fisher
asked Dec 2 '18 at 15:50
Will FisherWill Fisher
4,0331032
asked Dec 2 '18 at 15:50
Will FisherWill Fisher
4,0331032
asked Dec 2 '18 at 15:50
Will FisherWill Fisher
4,0331032
4,0331032
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
EDIT: The answer below isn't really an answer, as it failed to address the "in a row" component. See the comments for details.
So there are a total of $2^n$ possible sequences of flipping a fair coin $n$ times, and of those there are $n-1choose s-1$ that both contain exactly $s$ heads and end with a head (with the convention that binomial coefficients that don't make sense are all equal to $0$). Thus, $P(E_s = n)={n-1choose s-1}/2^n$ (you can verify that this statement is true by summing up all of these probabilities to show that you get back $1$).
If you need help with the specific problem, comment and let me know, but presumably this is what the doctor ordered.
answered Dec 2 '18 at 16:17
BlarglFlargBlarglFlarg
2134
$endgroup$
$begingroup$
I think the OP is asking for the first occurrence of $s$ heads in a row isn't he?
$endgroup$
– saulspatz
Dec 2 '18 at 16:25
$begingroup$
@saulspatz I wan't clear on that matter; the title references heads in a row, but the body only specifies "seeing $s$ heads". I assume that he will tell me which one he actually wants.
$endgroup$
– BlarglFlarg
Dec 2 '18 at 16:26
$begingroup$
My bad I just realized the two weren't consistent. I was intending on heads in a row if you have an idea on that.
$endgroup$
– Will Fisher
Dec 2 '18 at 16:37
$begingroup$
@WillFisher I do have an idea on how to pin down these probabilities, but it might take me a while to edit the answer completely. Basically you want to do a count of strings that avoid the forbidden subword of HH...H until the very end. The standard way of doing this that I know is via the Gouldan-Jackson cluster method. The two papers I have linked in this comment have good descriptions of it. arxiv.org/pdf/0810.5113.pdf sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/gj.pdf
$endgroup$
– BlarglFlarg
Dec 2 '18 at 16:48
$begingroup$
@BlarglFlarg Okay I'll take a look. The problem comes off a pretty simple exam so it maybe that calculating $P(E_4=E_3+k)$ can be done in a simpler way that computing the exact values of $P(E_s=n)$. I would also be fine with just a calculation of $P(E_4=8)$ and a verification of my calculation to $P(E_4=E_3+9)$.
$endgroup$
– Will Fisher
Dec 2 '18 at 16:51
|
show 2 more comments
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%2f3022791%2fprobability-that-first-s-heads-in-a-row-occurs-after-n-flips%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
EDIT: The answer below isn't really an answer, as it failed to address the "in a row" component. See the comments for details.
So there are a total of $2^n$ possible sequences of flipping a fair coin $n$ times, and of those there are $n-1choose s-1$ that both contain exactly $s$ heads and end with a head (with the convention that binomial coefficients that don't make sense are all equal to $0$). Thus, $P(E_s = n)={n-1choose s-1}/2^n$ (you can verify that this statement is true by summing up all of these probabilities to show that you get back $1$).
If you need help with the specific problem, comment and let me know, but presumably this is what the doctor ordered.
answered Dec 2 '18 at 16:17
BlarglFlargBlarglFlarg
2134
$endgroup$
$begingroup$
I think the OP is asking for the first occurrence of $s$ heads in a row isn't he?
$endgroup$
– saulspatz
Dec 2 '18 at 16:25
$begingroup$
@saulspatz I wan't clear on that matter; the title references heads in a row, but the body only specifies "seeing $s$ heads". I assume that he will tell me which one he actually wants.
$endgroup$
– BlarglFlarg
Dec 2 '18 at 16:26
$begingroup$
My bad I just realized the two weren't consistent. I was intending on heads in a row if you have an idea on that.
$endgroup$
– Will Fisher
Dec 2 '18 at 16:37
$begingroup$
@WillFisher I do have an idea on how to pin down these probabilities, but it might take me a while to edit the answer completely. Basically you want to do a count of strings that avoid the forbidden subword of HH...H until the very end. The standard way of doing this that I know is via the Gouldan-Jackson cluster method. The two papers I have linked in this comment have good descriptions of it. arxiv.org/pdf/0810.5113.pdf sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/gj.pdf
$endgroup$
– BlarglFlarg
Dec 2 '18 at 16:48
$begingroup$
@BlarglFlarg Okay I'll take a look. The problem comes off a pretty simple exam so it maybe that calculating $P(E_4=E_3+k)$ can be done in a simpler way that computing the exact values of $P(E_s=n)$. I would also be fine with just a calculation of $P(E_4=8)$ and a verification of my calculation to $P(E_4=E_3+9)$.
$endgroup$
– Will Fisher
Dec 2 '18 at 16:51
|
show 2 more comments
$begingroup$
EDIT: The answer below isn't really an answer, as it failed to address the "in a row" component. See the comments for details.
So there are a total of $2^n$ possible sequences of flipping a fair coin $n$ times, and of those there are $n-1choose s-1$ that both contain exactly $s$ heads and end with a head (with the convention that binomial coefficients that don't make sense are all equal to $0$). Thus, $P(E_s = n)={n-1choose s-1}/2^n$ (you can verify that this statement is true by summing up all of these probabilities to show that you get back $1$).
If you need help with the specific problem, comment and let me know, but presumably this is what the doctor ordered.
answered Dec 2 '18 at 16:17
BlarglFlargBlarglFlarg
2134
$endgroup$
$begingroup$
I think the OP is asking for the first occurrence of $s$ heads in a row isn't he?
$endgroup$
– saulspatz
Dec 2 '18 at 16:25
$begingroup$
@saulspatz I wan't clear on that matter; the title references heads in a row, but the body only specifies "seeing $s$ heads". I assume that he will tell me which one he actually wants.
$endgroup$
– BlarglFlarg
Dec 2 '18 at 16:26
$begingroup$
My bad I just realized the two weren't consistent. I was intending on heads in a row if you have an idea on that.
$endgroup$
– Will Fisher
Dec 2 '18 at 16:37
$begingroup$
@WillFisher I do have an idea on how to pin down these probabilities, but it might take me a while to edit the answer completely. Basically you want to do a count of strings that avoid the forbidden subword of HH...H until the very end. The standard way of doing this that I know is via the Gouldan-Jackson cluster method. The two papers I have linked in this comment have good descriptions of it. arxiv.org/pdf/0810.5113.pdf sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/gj.pdf
$endgroup$
– BlarglFlarg
Dec 2 '18 at 16:48
$begingroup$
@BlarglFlarg Okay I'll take a look. The problem comes off a pretty simple exam so it maybe that calculating $P(E_4=E_3+k)$ can be done in a simpler way that computing the exact values of $P(E_s=n)$. I would also be fine with just a calculation of $P(E_4=8)$ and a verification of my calculation to $P(E_4=E_3+9)$.
$endgroup$
– Will Fisher
Dec 2 '18 at 16:51
|
show 2 more comments
$begingroup$
EDIT: The answer below isn't really an answer, as it failed to address the "in a row" component. See the comments for details.
So there are a total of $2^n$ possible sequences of flipping a fair coin $n$ times, and of those there are $n-1choose s-1$ that both contain exactly $s$ heads and end with a head (with the convention that binomial coefficients that don't make sense are all equal to $0$). Thus, $P(E_s = n)={n-1choose s-1}/2^n$ (you can verify that this statement is true by summing up all of these probabilities to show that you get back $1$).
If you need help with the specific problem, comment and let me know, but presumably this is what the doctor ordered.
answered Dec 2 '18 at 16:17
BlarglFlargBlarglFlarg
2134
$endgroup$
EDIT: The answer below isn't really an answer, as it failed to address the "in a row" component. See the comments for details.
So there are a total of $2^n$ possible sequences of flipping a fair coin $n$ times, and of those there are $n-1choose s-1$ that both contain exactly $s$ heads and end with a head (with the convention that binomial coefficients that don't make sense are all equal to $0$). Thus, $P(E_s = n)={n-1choose s-1}/2^n$ (you can verify that this statement is true by summing up all of these probabilities to show that you get back $1$).
If you need help with the specific problem, comment and let me know, but presumably this is what the doctor ordered.
answered Dec 2 '18 at 16:17
BlarglFlargBlarglFlarg
2134
edited Dec 2 '18 at 16:58
answered Dec 2 '18 at 16:17
BlarglFlargBlarglFlarg
2134
answered Dec 2 '18 at 16:17
BlarglFlargBlarglFlarg
2134
answered Dec 2 '18 at 16:17
BlarglFlargBlarglFlarg
2134
2134
$begingroup$
I think the OP is asking for the first occurrence of $s$ heads in a row isn't he?
$endgroup$
– saulspatz
Dec 2 '18 at 16:25
$begingroup$
@saulspatz I wan't clear on that matter; the title references heads in a row, but the body only specifies "seeing $s$ heads". I assume that he will tell me which one he actually wants.
$endgroup$
– BlarglFlarg
Dec 2 '18 at 16:26
$begingroup$
My bad I just realized the two weren't consistent. I was intending on heads in a row if you have an idea on that.
$endgroup$
– Will Fisher
Dec 2 '18 at 16:37
$begingroup$
@WillFisher I do have an idea on how to pin down these probabilities, but it might take me a while to edit the answer completely. Basically you want to do a count of strings that avoid the forbidden subword of HH...H until the very end. The standard way of doing this that I know is via the Gouldan-Jackson cluster method. The two papers I have linked in this comment have good descriptions of it. arxiv.org/pdf/0810.5113.pdf sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/gj.pdf
$endgroup$
– BlarglFlarg
Dec 2 '18 at 16:48
$begingroup$
@BlarglFlarg Okay I'll take a look. The problem comes off a pretty simple exam so it maybe that calculating $P(E_4=E_3+k)$ can be done in a simpler way that computing the exact values of $P(E_s=n)$. I would also be fine with just a calculation of $P(E_4=8)$ and a verification of my calculation to $P(E_4=E_3+9)$.
$endgroup$
– Will Fisher
Dec 2 '18 at 16:51
|
show 2 more comments
$begingroup$
I think the OP is asking for the first occurrence of $s$ heads in a row isn't he?
$endgroup$
– saulspatz
Dec 2 '18 at 16:25
$begingroup$
@saulspatz I wan't clear on that matter; the title references heads in a row, but the body only specifies "seeing $s$ heads". I assume that he will tell me which one he actually wants.
$endgroup$
– BlarglFlarg
Dec 2 '18 at 16:26
$begingroup$
My bad I just realized the two weren't consistent. I was intending on heads in a row if you have an idea on that.
$endgroup$
– Will Fisher
Dec 2 '18 at 16:37
$begingroup$
@WillFisher I do have an idea on how to pin down these probabilities, but it might take me a while to edit the answer completely. Basically you want to do a count of strings that avoid the forbidden subword of HH...H until the very end. The standard way of doing this that I know is via the Gouldan-Jackson cluster method. The two papers I have linked in this comment have good descriptions of it. arxiv.org/pdf/0810.5113.pdf sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/gj.pdf
$endgroup$
– BlarglFlarg
Dec 2 '18 at 16:48
$begingroup$
@BlarglFlarg Okay I'll take a look. The problem comes off a pretty simple exam so it maybe that calculating $P(E_4=E_3+k)$ can be done in a simpler way that computing the exact values of $P(E_s=n)$. I would also be fine with just a calculation of $P(E_4=8)$ and a verification of my calculation to $P(E_4=E_3+9)$.
$endgroup$
– Will Fisher
Dec 2 '18 at 16:51
$begingroup$
I think the OP is asking for the first occurrence of $s$ heads in a row isn't he?
$endgroup$
– saulspatz
Dec 2 '18 at 16:25
$begingroup$
I think the OP is asking for the first occurrence of $s$ heads in a row isn't he?
$endgroup$
– saulspatz
Dec 2 '18 at 16:25
$begingroup$
@saulspatz I wan't clear on that matter; the title references heads in a row, but the body only specifies "seeing $s$ heads". I assume that he will tell me which one he actually wants.
$endgroup$
– BlarglFlarg
Dec 2 '18 at 16:26
$begingroup$
@saulspatz I wan't clear on that matter; the title references heads in a row, but the body only specifies "seeing $s$ heads". I assume that he will tell me which one he actually wants.
$endgroup$
– BlarglFlarg
Dec 2 '18 at 16:26
$begingroup$
My bad I just realized the two weren't consistent. I was intending on heads in a row if you have an idea on that.
$endgroup$
– Will Fisher
Dec 2 '18 at 16:37
$begingroup$
My bad I just realized the two weren't consistent. I was intending on heads in a row if you have an idea on that.
$endgroup$
– Will Fisher
Dec 2 '18 at 16:37
$begingroup$
@WillFisher I do have an idea on how to pin down these probabilities, but it might take me a while to edit the answer completely. Basically you want to do a count of strings that avoid the forbidden subword of HH...H until the very end. The standard way of doing this that I know is via the Gouldan-Jackson cluster method. The two papers I have linked in this comment have good descriptions of it. arxiv.org/pdf/0810.5113.pdf sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/gj.pdf
$endgroup$
– BlarglFlarg
Dec 2 '18 at 16:48
$begingroup$
@WillFisher I do have an idea on how to pin down these probabilities, but it might take me a while to edit the answer completely. Basically you want to do a count of strings that avoid the forbidden subword of HH...H until the very end. The standard way of doing this that I know is via the Gouldan-Jackson cluster method. The two papers I have linked in this comment have good descriptions of it. arxiv.org/pdf/0810.5113.pdf sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/gj.pdf
$endgroup$
– BlarglFlarg
Dec 2 '18 at 16:48
$begingroup$
@BlarglFlarg Okay I'll take a look. The problem comes off a pretty simple exam so it maybe that calculating $P(E_4=E_3+k)$ can be done in a simpler way that computing the exact values of $P(E_s=n)$. I would also be fine with just a calculation of $P(E_4=8)$ and a verification of my calculation to $P(E_4=E_3+9)$.
$endgroup$
– Will Fisher
Dec 2 '18 at 16:51
$begingroup$
@BlarglFlarg Okay I'll take a look. The problem comes off a pretty simple exam so it maybe that calculating $P(E_4=E_3+k)$ can be done in a simpler way that computing the exact values of $P(E_s=n)$. I would also be fine with just a calculation of $P(E_4=8)$ and a verification of my calculation to $P(E_4=E_3+9)$.
$endgroup$
– Will Fisher
Dec 2 '18 at 16:51
|
show 2 more comments
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%2f3022791%2fprobability-that-first-s-heads-in-a-row-occurs-after-n-flips%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
