Using a gamblers race to approximate $pi$
Imagine two wealthy gamblers start tossing their own separate fair coins, winning 1$ on heads and losing 1$ on tails. Both start at 0$ and have infinite bank balances. Both of them want to get to k$. What is the probability that they will both reach their targets on the same toss?
Based on this question we see that the answers to all such questions take the form $A+frac{B}{pi}$. Here, we're strictly focusing on draws. First, we know that the stopping time (probability he'll reach his target first time on toss $2t+k$) for any one gambler is given by:
$$a_k(t) = frac{k}{k+t}frac{{2t+k-1 choose t}}{2^{2t+k}}$$
Now, the probability of an overall draw is simply the probability both will reach their target on toss $2t+k$, summed over all possible values of $t$.
$$D_k = sumlimits_{t=0}^{infty} left(frac{k}{k+t}frac{{2t+k-1 choose t}}{2^{2t+k}}right)^2$$
Mathematica can't find a nice closed form expression for the summation above (if you can, I'll be very impressed indeed). However, plugging various values of $k$ in we find that the answer always takes the form:
$$D_k = frac{E_k}{F_k pi} - G_k$$
Where $E_k$, $F_k$ and $G_k$ are all integers. Plugging the first few values of $G_k$ (calculated using Mathematica) into OEIS, I got the sequence A002002. This means that:
$$G_k = sumlimits_{l=0}^{k-1} {k choose l+1} {k+l choose l}$$
However, I haven't been able to find corresponding expressions for $E_k$ and $F_k$. Can anyone help with this? We can use it to get an expression for $pi$ since $D_{infty} = 0$
Here are the first few expressions for $D_k$.
$$D_1 = frac{4}{pi}-1$$
$$D_2 = frac{16}{pi}-5$$
$$D_3 = frac{236}{3 pi}-25$$
$$D_4 = frac{1216}{3 pi} - 129$$
$$D_5 = frac{32092}{15 pi} - 681$$
$$D_6 = frac{172144}{15 pi} - 3653$$
$$D_7 = frac{1307924}{21 pi} - 19825$$
$$D_8 = frac{7161088}{21 pi} - 108545$$
$$D_9 = frac{592194476}{315 pi} - 598417$$
$$D_{10} = frac{3282949168}{315 pi} - 3317445$$
$$D_{11} = frac{40221561524}{693 pi} - 18474633$$
$$D_{12} = frac{224841634624}{693 pi} - 103274625$$
Unfortunately, Mathematica gives up providing nice expressions in terms of $pi$, $D_{13}$ onwards.
The idea is courtesy /u/boyobo on this reddit thread.
probability combinatorics summation binomial-coefficients pi
asked Jan 1 at 22:45
Rohit Pandey
1,175921
|
show 3 more comments
Imagine two wealthy gamblers start tossing their own separate fair coins, winning 1$ on heads and losing 1$ on tails. Both start at 0$ and have infinite bank balances. Both of them want to get to k$. What is the probability that they will both reach their targets on the same toss?
Based on this question we see that the answers to all such questions take the form $A+frac{B}{pi}$. Here, we're strictly focusing on draws. First, we know that the stopping time (probability he'll reach his target first time on toss $2t+k$) for any one gambler is given by:
$$a_k(t) = frac{k}{k+t}frac{{2t+k-1 choose t}}{2^{2t+k}}$$
Now, the probability of an overall draw is simply the probability both will reach their target on toss $2t+k$, summed over all possible values of $t$.
$$D_k = sumlimits_{t=0}^{infty} left(frac{k}{k+t}frac{{2t+k-1 choose t}}{2^{2t+k}}right)^2$$
Mathematica can't find a nice closed form expression for the summation above (if you can, I'll be very impressed indeed). However, plugging various values of $k$ in we find that the answer always takes the form:
$$D_k = frac{E_k}{F_k pi} - G_k$$
Where $E_k$, $F_k$ and $G_k$ are all integers. Plugging the first few values of $G_k$ (calculated using Mathematica) into OEIS, I got the sequence A002002. This means that:
$$G_k = sumlimits_{l=0}^{k-1} {k choose l+1} {k+l choose l}$$
However, I haven't been able to find corresponding expressions for $E_k$ and $F_k$. Can anyone help with this? We can use it to get an expression for $pi$ since $D_{infty} = 0$
Here are the first few expressions for $D_k$.
$$D_1 = frac{4}{pi}-1$$
$$D_2 = frac{16}{pi}-5$$
$$D_3 = frac{236}{3 pi}-25$$
$$D_4 = frac{1216}{3 pi} - 129$$
$$D_5 = frac{32092}{15 pi} - 681$$
$$D_6 = frac{172144}{15 pi} - 3653$$
$$D_7 = frac{1307924}{21 pi} - 19825$$
$$D_8 = frac{7161088}{21 pi} - 108545$$
$$D_9 = frac{592194476}{315 pi} - 598417$$
$$D_{10} = frac{3282949168}{315 pi} - 3317445$$
$$D_{11} = frac{40221561524}{693 pi} - 18474633$$
$$D_{12} = frac{224841634624}{693 pi} - 103274625$$
Unfortunately, Mathematica gives up providing nice expressions in terms of $pi$, $D_{13}$ onwards.
The idea is courtesy /u/boyobo on this reddit thread.
probability combinatorics summation binomial-coefficients pi
asked Jan 1 at 22:45
Rohit Pandey
1,175921
2
My instinct is that having $E_k$ and $F_k$ in their lowest form is causing you to lose some common factors; either you should treat $E_k/F_k$ as a single variable or there are factors that should be found. Assuming that $236/16$ is in fact equal to $E_3/E_2$, the factors won't be large. This is, of course, speculation and purely based on my intuition - I can't find any pattern by doing so, but maybe someone else can.
– Spitemaster
Jan 2 at 18:24
2
Concur with @Spitemaster; the $F_k$ denominator almost definitely should have a $k!$ component, if you look at how the prime factors 3, 5, 7, and 11 enter.
– Jeremy Dover
Jan 2 at 19:55
Is there an online encyclopedia for non-integer sequences as well? Maybe the fractions $E_k/F_k$ follow some pattern.
– Rohit Pandey
Jan 2 at 20:02
1
I’m afraid that an encyclopedia of non-integer sequences is not-online but an appendix to The Book, in which, according to Paul Erdős, God had written down the best and most elegant proofs for mathematical theorems. :-) But even being restricted to integer these I have a hope to adapt for $F_k$ one of the first sequences at this query. I guess that a knowledge of $F_{13}$ can help to choose a right way.
– Alex Ravsky
2 days ago
1
Thanks Alex. Also for the note about the blog. Sadly, Mathematica gives up on providing a nice expression in terms of $pi$ for n=13 (does that up to 12). It spits out "HypergeometricFPQ[{13/2,13/2,7,7},{1,14,14},1]/67108864" when I plug 13 in. The numerical answer is 1.89455e-3.
– Rohit Pandey
2 days ago
|
show 3 more comments
Imagine two wealthy gamblers start tossing their own separate fair coins, winning 1$ on heads and losing 1$ on tails. Both start at 0$ and have infinite bank balances. Both of them want to get to k$. What is the probability that they will both reach their targets on the same toss?
Based on this question we see that the answers to all such questions take the form $A+frac{B}{pi}$. Here, we're strictly focusing on draws. First, we know that the stopping time (probability he'll reach his target first time on toss $2t+k$) for any one gambler is given by:
$$a_k(t) = frac{k}{k+t}frac{{2t+k-1 choose t}}{2^{2t+k}}$$
Now, the probability of an overall draw is simply the probability both will reach their target on toss $2t+k$, summed over all possible values of $t$.
$$D_k = sumlimits_{t=0}^{infty} left(frac{k}{k+t}frac{{2t+k-1 choose t}}{2^{2t+k}}right)^2$$
Mathematica can't find a nice closed form expression for the summation above (if you can, I'll be very impressed indeed). However, plugging various values of $k$ in we find that the answer always takes the form:
$$D_k = frac{E_k}{F_k pi} - G_k$$
Where $E_k$, $F_k$ and $G_k$ are all integers. Plugging the first few values of $G_k$ (calculated using Mathematica) into OEIS, I got the sequence A002002. This means that:
$$G_k = sumlimits_{l=0}^{k-1} {k choose l+1} {k+l choose l}$$
However, I haven't been able to find corresponding expressions for $E_k$ and $F_k$. Can anyone help with this? We can use it to get an expression for $pi$ since $D_{infty} = 0$
Here are the first few expressions for $D_k$.
$$D_1 = frac{4}{pi}-1$$
$$D_2 = frac{16}{pi}-5$$
$$D_3 = frac{236}{3 pi}-25$$
$$D_4 = frac{1216}{3 pi} - 129$$
$$D_5 = frac{32092}{15 pi} - 681$$
$$D_6 = frac{172144}{15 pi} - 3653$$
$$D_7 = frac{1307924}{21 pi} - 19825$$
$$D_8 = frac{7161088}{21 pi} - 108545$$
$$D_9 = frac{592194476}{315 pi} - 598417$$
$$D_{10} = frac{3282949168}{315 pi} - 3317445$$
$$D_{11} = frac{40221561524}{693 pi} - 18474633$$
$$D_{12} = frac{224841634624}{693 pi} - 103274625$$
Unfortunately, Mathematica gives up providing nice expressions in terms of $pi$, $D_{13}$ onwards.
The idea is courtesy /u/boyobo on this reddit thread.
probability combinatorics summation binomial-coefficients pi
asked Jan 1 at 22:45
Rohit Pandey
1,175921
Imagine two wealthy gamblers start tossing their own separate fair coins, winning 1$ on heads and losing 1$ on tails. Both start at 0$ and have infinite bank balances. Both of them want to get to k$. What is the probability that they will both reach their targets on the same toss?
Based on this question we see that the answers to all such questions take the form $A+frac{B}{pi}$. Here, we're strictly focusing on draws. First, we know that the stopping time (probability he'll reach his target first time on toss $2t+k$) for any one gambler is given by:
$$a_k(t) = frac{k}{k+t}frac{{2t+k-1 choose t}}{2^{2t+k}}$$
Now, the probability of an overall draw is simply the probability both will reach their target on toss $2t+k$, summed over all possible values of $t$.
$$D_k = sumlimits_{t=0}^{infty} left(frac{k}{k+t}frac{{2t+k-1 choose t}}{2^{2t+k}}right)^2$$
Mathematica can't find a nice closed form expression for the summation above (if you can, I'll be very impressed indeed). However, plugging various values of $k$ in we find that the answer always takes the form:
$$D_k = frac{E_k}{F_k pi} - G_k$$
Where $E_k$, $F_k$ and $G_k$ are all integers. Plugging the first few values of $G_k$ (calculated using Mathematica) into OEIS, I got the sequence A002002. This means that:
$$G_k = sumlimits_{l=0}^{k-1} {k choose l+1} {k+l choose l}$$
However, I haven't been able to find corresponding expressions for $E_k$ and $F_k$. Can anyone help with this? We can use it to get an expression for $pi$ since $D_{infty} = 0$
Here are the first few expressions for $D_k$.
$$D_1 = frac{4}{pi}-1$$
$$D_2 = frac{16}{pi}-5$$
$$D_3 = frac{236}{3 pi}-25$$
$$D_4 = frac{1216}{3 pi} - 129$$
$$D_5 = frac{32092}{15 pi} - 681$$
$$D_6 = frac{172144}{15 pi} - 3653$$
$$D_7 = frac{1307924}{21 pi} - 19825$$
$$D_8 = frac{7161088}{21 pi} - 108545$$
$$D_9 = frac{592194476}{315 pi} - 598417$$
$$D_{10} = frac{3282949168}{315 pi} - 3317445$$
$$D_{11} = frac{40221561524}{693 pi} - 18474633$$
$$D_{12} = frac{224841634624}{693 pi} - 103274625$$
Unfortunately, Mathematica gives up providing nice expressions in terms of $pi$, $D_{13}$ onwards.
The idea is courtesy /u/boyobo on this reddit thread.
probability combinatorics summation binomial-coefficients pi
probability combinatorics summation binomial-coefficients pi
asked Jan 1 at 22:45
Rohit Pandey
1,175921
asked Jan 1 at 22:45
Rohit Pandey
1,175921
edited 2 days ago
asked Jan 1 at 22:45
Rohit Pandey
1,175921
asked Jan 1 at 22:45
Rohit Pandey
1,175921
asked Jan 1 at 22:45
Rohit Pandey
1,175921
1,175921
2
My instinct is that having $E_k$ and $F_k$ in their lowest form is causing you to lose some common factors; either you should treat $E_k/F_k$ as a single variable or there are factors that should be found. Assuming that $236/16$ is in fact equal to $E_3/E_2$, the factors won't be large. This is, of course, speculation and purely based on my intuition - I can't find any pattern by doing so, but maybe someone else can.
– Spitemaster
Jan 2 at 18:24
2
Concur with @Spitemaster; the $F_k$ denominator almost definitely should have a $k!$ component, if you look at how the prime factors 3, 5, 7, and 11 enter.
– Jeremy Dover
Jan 2 at 19:55
Is there an online encyclopedia for non-integer sequences as well? Maybe the fractions $E_k/F_k$ follow some pattern.
– Rohit Pandey
Jan 2 at 20:02
1
I’m afraid that an encyclopedia of non-integer sequences is not-online but an appendix to The Book, in which, according to Paul Erdős, God had written down the best and most elegant proofs for mathematical theorems. :-) But even being restricted to integer these I have a hope to adapt for $F_k$ one of the first sequences at this query. I guess that a knowledge of $F_{13}$ can help to choose a right way.
– Alex Ravsky
2 days ago
1
Thanks Alex. Also for the note about the blog. Sadly, Mathematica gives up on providing a nice expression in terms of $pi$ for n=13 (does that up to 12). It spits out "HypergeometricFPQ[{13/2,13/2,7,7},{1,14,14},1]/67108864" when I plug 13 in. The numerical answer is 1.89455e-3.
– Rohit Pandey
2 days ago
|
show 3 more comments
2
My instinct is that having $E_k$ and $F_k$ in their lowest form is causing you to lose some common factors; either you should treat $E_k/F_k$ as a single variable or there are factors that should be found. Assuming that $236/16$ is in fact equal to $E_3/E_2$, the factors won't be large. This is, of course, speculation and purely based on my intuition - I can't find any pattern by doing so, but maybe someone else can.
– Spitemaster
Jan 2 at 18:24
2
Concur with @Spitemaster; the $F_k$ denominator almost definitely should have a $k!$ component, if you look at how the prime factors 3, 5, 7, and 11 enter.
– Jeremy Dover
Jan 2 at 19:55
Is there an online encyclopedia for non-integer sequences as well? Maybe the fractions $E_k/F_k$ follow some pattern.
– Rohit Pandey
Jan 2 at 20:02
1
I’m afraid that an encyclopedia of non-integer sequences is not-online but an appendix to The Book, in which, according to Paul Erdős, God had written down the best and most elegant proofs for mathematical theorems. :-) But even being restricted to integer these I have a hope to adapt for $F_k$ one of the first sequences at this query. I guess that a knowledge of $F_{13}$ can help to choose a right way.
– Alex Ravsky
2 days ago
1
Thanks Alex. Also for the note about the blog. Sadly, Mathematica gives up on providing a nice expression in terms of $pi$ for n=13 (does that up to 12). It spits out "HypergeometricFPQ[{13/2,13/2,7,7},{1,14,14},1]/67108864" when I plug 13 in. The numerical answer is 1.89455e-3.
– Rohit Pandey
2 days ago
2
2
My instinct is that having $E_k$ and $F_k$ in their lowest form is causing you to lose some common factors; either you should treat $E_k/F_k$ as a single variable or there are factors that should be found. Assuming that $236/16$ is in fact equal to $E_3/E_2$, the factors won't be large. This is, of course, speculation and purely based on my intuition - I can't find any pattern by doing so, but maybe someone else can.
– Spitemaster
Jan 2 at 18:24
My instinct is that having $E_k$ and $F_k$ in their lowest form is causing you to lose some common factors; either you should treat $E_k/F_k$ as a single variable or there are factors that should be found. Assuming that $236/16$ is in fact equal to $E_3/E_2$, the factors won't be large. This is, of course, speculation and purely based on my intuition - I can't find any pattern by doing so, but maybe someone else can.
– Spitemaster
Jan 2 at 18:24
2
2
Concur with @Spitemaster; the $F_k$ denominator almost definitely should have a $k!$ component, if you look at how the prime factors 3, 5, 7, and 11 enter.
– Jeremy Dover
Jan 2 at 19:55
Concur with @Spitemaster; the $F_k$ denominator almost definitely should have a $k!$ component, if you look at how the prime factors 3, 5, 7, and 11 enter.
– Jeremy Dover
Jan 2 at 19:55
Is there an online encyclopedia for non-integer sequences as well? Maybe the fractions $E_k/F_k$ follow some pattern.
– Rohit Pandey
Jan 2 at 20:02
Is there an online encyclopedia for non-integer sequences as well? Maybe the fractions $E_k/F_k$ follow some pattern.
– Rohit Pandey
Jan 2 at 20:02
1
1
I’m afraid that an encyclopedia of non-integer sequences is not-online but an appendix to The Book, in which, according to Paul Erdős, God had written down the best and most elegant proofs for mathematical theorems. :-) But even being restricted to integer these I have a hope to adapt for $F_k$ one of the first sequences at this query. I guess that a knowledge of $F_{13}$ can help to choose a right way.
– Alex Ravsky
2 days ago
I’m afraid that an encyclopedia of non-integer sequences is not-online but an appendix to The Book, in which, according to Paul Erdős, God had written down the best and most elegant proofs for mathematical theorems. :-) But even being restricted to integer these I have a hope to adapt for $F_k$ one of the first sequences at this query. I guess that a knowledge of $F_{13}$ can help to choose a right way.
– Alex Ravsky
2 days ago
1
1
Thanks Alex. Also for the note about the blog. Sadly, Mathematica gives up on providing a nice expression in terms of $pi$ for n=13 (does that up to 12). It spits out "HypergeometricFPQ[{13/2,13/2,7,7},{1,14,14},1]/67108864" when I plug 13 in. The numerical answer is 1.89455e-3.
– Rohit Pandey
2 days ago
Thanks Alex. Also for the note about the blog. Sadly, Mathematica gives up on providing a nice expression in terms of $pi$ for n=13 (does that up to 12). It spits out "HypergeometricFPQ[{13/2,13/2,7,7},{1,14,14},1]/67108864" when I plug 13 in. The numerical answer is 1.89455e-3.
– Rohit Pandey
2 days ago
|
show 3 more comments
0
active
oldest
votes
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%2f3058952%2fusing-a-gamblers-race-to-approximate-pi%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3058952%2fusing-a-gamblers-race-to-approximate-pi%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
My instinct is that having $E_k$ and $F_k$ in their lowest form is causing you to lose some common factors; either you should treat $E_k/F_k$ as a single variable or there are factors that should be found. Assuming that $236/16$ is in fact equal to $E_3/E_2$, the factors won't be large. This is, of course, speculation and purely based on my intuition - I can't find any pattern by doing so, but maybe someone else can.
– Spitemaster
Jan 2 at 18:24
2
Concur with @Spitemaster; the $F_k$ denominator almost definitely should have a $k!$ component, if you look at how the prime factors 3, 5, 7, and 11 enter.
– Jeremy Dover
Jan 2 at 19:55
Is there an online encyclopedia for non-integer sequences as well? Maybe the fractions $E_k/F_k$ follow some pattern.
– Rohit Pandey
Jan 2 at 20:02
1
I’m afraid that an encyclopedia of non-integer sequences is not-online but an appendix to The Book, in which, according to Paul Erdős, God had written down the best and most elegant proofs for mathematical theorems. :-) But even being restricted to integer these I have a hope to adapt for $F_k$ one of the first sequences at this query. I guess that a knowledge of $F_{13}$ can help to choose a right way.
– Alex Ravsky
2 days ago
1
Thanks Alex. Also for the note about the blog. Sadly, Mathematica gives up on providing a nice expression in terms of $pi$ for n=13 (does that up to 12). It spits out "HypergeometricFPQ[{13/2,13/2,7,7},{1,14,14},1]/67108864" when I plug 13 in. The numerical answer is 1.89455e-3.
– Rohit Pandey
2 days ago