Gambler’s Ruin in finite time - solve by Markov chains?
$begingroup$
Consider the Gambler's Ruin Problem: an infinite Markov process of steps with binary outcomes of plus or minus, each of equal probability. At each step of the process there may be a play of the game.
At each play of the game starting with step 1, the gambler's initial fortune, B, increases by one unit with probability 1/2 or decreases by one unit with probability 1/2. The game ends at step N or sooner (after fewer plays) if the gambler's profit first reaches a Target of +A or a Ruin (total loss) of -B units anytime during the process (which continues beyond N steps).
There are three profit outcomes after step N:
-B, +A, or Neither.
Ruin is defined by profit reaching -B for the first time during N plays without first reaching +A.
Success is defined by profit reaching +A for the first time during N plays without first reaching -B.
Problem: What is the probability of a. Ruin or b. Success or c. Neither, in terms of A, B, N?
I cannot solve this except by path-counting. Can a.,b.,c. be solved in a closed form by Markov chains?
This problem is also called a random walk of a particle in finite time with two absorbing barriers.
probability
asked Jan 2 at 16:24
artbenisartbenis
112
$endgroup$
add a comment |
$begingroup$
Consider the Gambler's Ruin Problem: an infinite Markov process of steps with binary outcomes of plus or minus, each of equal probability. At each step of the process there may be a play of the game.
At each play of the game starting with step 1, the gambler's initial fortune, B, increases by one unit with probability 1/2 or decreases by one unit with probability 1/2. The game ends at step N or sooner (after fewer plays) if the gambler's profit first reaches a Target of +A or a Ruin (total loss) of -B units anytime during the process (which continues beyond N steps).
There are three profit outcomes after step N:
-B, +A, or Neither.
Ruin is defined by profit reaching -B for the first time during N plays without first reaching +A.
Success is defined by profit reaching +A for the first time during N plays without first reaching -B.
Problem: What is the probability of a. Ruin or b. Success or c. Neither, in terms of A, B, N?
I cannot solve this except by path-counting. Can a.,b.,c. be solved in a closed form by Markov chains?
This problem is also called a random walk of a particle in finite time with two absorbing barriers.
probability
asked Jan 2 at 16:24
artbenisartbenis
112
$endgroup$
$begingroup$
He will be ruined
$endgroup$
– AkatsukiMaliki
Jan 2 at 17:10
$begingroup$
@AkatsukiMaliki. Not so. For example with A = B= N=2, P of Neither = 1/2.
$endgroup$
– artbenis
Jan 2 at 18:04
add a comment |
$begingroup$
Consider the Gambler's Ruin Problem: an infinite Markov process of steps with binary outcomes of plus or minus, each of equal probability. At each step of the process there may be a play of the game.
At each play of the game starting with step 1, the gambler's initial fortune, B, increases by one unit with probability 1/2 or decreases by one unit with probability 1/2. The game ends at step N or sooner (after fewer plays) if the gambler's profit first reaches a Target of +A or a Ruin (total loss) of -B units anytime during the process (which continues beyond N steps).
There are three profit outcomes after step N:
-B, +A, or Neither.
Ruin is defined by profit reaching -B for the first time during N plays without first reaching +A.
Success is defined by profit reaching +A for the first time during N plays without first reaching -B.
Problem: What is the probability of a. Ruin or b. Success or c. Neither, in terms of A, B, N?
I cannot solve this except by path-counting. Can a.,b.,c. be solved in a closed form by Markov chains?
This problem is also called a random walk of a particle in finite time with two absorbing barriers.
probability
asked Jan 2 at 16:24
artbenisartbenis
112
$endgroup$
Consider the Gambler's Ruin Problem: an infinite Markov process of steps with binary outcomes of plus or minus, each of equal probability. At each step of the process there may be a play of the game.
At each play of the game starting with step 1, the gambler's initial fortune, B, increases by one unit with probability 1/2 or decreases by one unit with probability 1/2. The game ends at step N or sooner (after fewer plays) if the gambler's profit first reaches a Target of +A or a Ruin (total loss) of -B units anytime during the process (which continues beyond N steps).
There are three profit outcomes after step N:
-B, +A, or Neither.
Ruin is defined by profit reaching -B for the first time during N plays without first reaching +A.
Success is defined by profit reaching +A for the first time during N plays without first reaching -B.
Problem: What is the probability of a. Ruin or b. Success or c. Neither, in terms of A, B, N?
I cannot solve this except by path-counting. Can a.,b.,c. be solved in a closed form by Markov chains?
This problem is also called a random walk of a particle in finite time with two absorbing barriers.
probability
probability
asked Jan 2 at 16:24
artbenisartbenis
112
asked Jan 2 at 16:24
artbenisartbenis
112
edited Jan 2 at 18:16
artbenis
asked Jan 2 at 16:24
artbenisartbenis
112
asked Jan 2 at 16:24
artbenisartbenis
112
asked Jan 2 at 16:24
artbenisartbenis
112
112
$begingroup$
He will be ruined
$endgroup$
– AkatsukiMaliki
Jan 2 at 17:10
$begingroup$
@AkatsukiMaliki. Not so. For example with A = B= N=2, P of Neither = 1/2.
$endgroup$
– artbenis
Jan 2 at 18:04
add a comment |
$begingroup$
He will be ruined
$endgroup$
– AkatsukiMaliki
Jan 2 at 17:10
$begingroup$
@AkatsukiMaliki. Not so. For example with A = B= N=2, P of Neither = 1/2.
$endgroup$
– artbenis
Jan 2 at 18:04
$begingroup$
He will be ruined
$endgroup$
– AkatsukiMaliki
Jan 2 at 17:10
$begingroup$
He will be ruined
$endgroup$
– AkatsukiMaliki
Jan 2 at 17:10
$begingroup$
@AkatsukiMaliki. Not so. For example with A = B= N=2, P of Neither = 1/2.
$endgroup$
– artbenis
Jan 2 at 18:04
$begingroup$
@AkatsukiMaliki. Not so. For example with A = B= N=2, P of Neither = 1/2.
$endgroup$
– artbenis
Jan 2 at 18:04
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Would leave as comment, but too long:
Since each path corresponds to a 0-1 bit string on Length $N$, you must implicitly compute the sum of binomial coefficients to determine your final probabilities. I think this is what you are already doing (my interpretation of path counting?). Unfortunately, summing binomial coefficients is infeasible for large values of $N$, so this is the best you are going to be able to do. For large $N$, Determining exact values for the sum of binomial coefficients is not possible (It would make my research a lot easier if it was :)), we only know of good approximations (again, this is assuming N is very large, otherwise you can just sum up the binomial coefficients you're interested in via some math program). Depending on the relationship between $N$ $B$ and $A$, you may be able to find asymptotically tight bounds for the desired probabilities. I would recommend checking out Stirling's approximation, Entropy bounds for binomial coefficients, and related literature. This may be a useful resource if you are interested in the "large N" regime.
EDIT: As a side note, this does not become feasible even when the probability of win/loss is not 1/2. In this regime, you can still get useful bounds using KL-Divergence based estimates of binomial coefficients. This generalizes the entropy bounds mentioned earlier (See this math stack post if you are interested).
answered Jan 2 at 18:17
mm8511mm8511
538210
$endgroup$
$begingroup$
Thanks for your reply. A quick point on your reference to very large N values: then there are well-known closed form solutions to a., b., and c. they are a. B/( A+ B) , b. A/(A + B) , c. zero.
$endgroup$
– artbenis
Jan 3 at 19:13
$begingroup$
There are also approximate solutions for them e.g. for c. (A+B - 3)/N.
$endgroup$
– artbenis
Jan 3 at 19:21
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%2f3059671%2fgambler-s-ruin-in-finite-time-solve-by-markov-chains%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$
Would leave as comment, but too long:
Since each path corresponds to a 0-1 bit string on Length $N$, you must implicitly compute the sum of binomial coefficients to determine your final probabilities. I think this is what you are already doing (my interpretation of path counting?). Unfortunately, summing binomial coefficients is infeasible for large values of $N$, so this is the best you are going to be able to do. For large $N$, Determining exact values for the sum of binomial coefficients is not possible (It would make my research a lot easier if it was :)), we only know of good approximations (again, this is assuming N is very large, otherwise you can just sum up the binomial coefficients you're interested in via some math program). Depending on the relationship between $N$ $B$ and $A$, you may be able to find asymptotically tight bounds for the desired probabilities. I would recommend checking out Stirling's approximation, Entropy bounds for binomial coefficients, and related literature. This may be a useful resource if you are interested in the "large N" regime.
EDIT: As a side note, this does not become feasible even when the probability of win/loss is not 1/2. In this regime, you can still get useful bounds using KL-Divergence based estimates of binomial coefficients. This generalizes the entropy bounds mentioned earlier (See this math stack post if you are interested).
answered Jan 2 at 18:17
mm8511mm8511
538210
$endgroup$
$begingroup$
Thanks for your reply. A quick point on your reference to very large N values: then there are well-known closed form solutions to a., b., and c. they are a. B/( A+ B) , b. A/(A + B) , c. zero.
$endgroup$
– artbenis
Jan 3 at 19:13
$begingroup$
There are also approximate solutions for them e.g. for c. (A+B - 3)/N.
$endgroup$
– artbenis
Jan 3 at 19:21
add a comment |
$begingroup$
Would leave as comment, but too long:
Since each path corresponds to a 0-1 bit string on Length $N$, you must implicitly compute the sum of binomial coefficients to determine your final probabilities. I think this is what you are already doing (my interpretation of path counting?). Unfortunately, summing binomial coefficients is infeasible for large values of $N$, so this is the best you are going to be able to do. For large $N$, Determining exact values for the sum of binomial coefficients is not possible (It would make my research a lot easier if it was :)), we only know of good approximations (again, this is assuming N is very large, otherwise you can just sum up the binomial coefficients you're interested in via some math program). Depending on the relationship between $N$ $B$ and $A$, you may be able to find asymptotically tight bounds for the desired probabilities. I would recommend checking out Stirling's approximation, Entropy bounds for binomial coefficients, and related literature. This may be a useful resource if you are interested in the "large N" regime.
EDIT: As a side note, this does not become feasible even when the probability of win/loss is not 1/2. In this regime, you can still get useful bounds using KL-Divergence based estimates of binomial coefficients. This generalizes the entropy bounds mentioned earlier (See this math stack post if you are interested).
answered Jan 2 at 18:17
mm8511mm8511
538210
$endgroup$
$begingroup$
Thanks for your reply. A quick point on your reference to very large N values: then there are well-known closed form solutions to a., b., and c. they are a. B/( A+ B) , b. A/(A + B) , c. zero.
$endgroup$
– artbenis
Jan 3 at 19:13
$begingroup$
There are also approximate solutions for them e.g. for c. (A+B - 3)/N.
$endgroup$
– artbenis
Jan 3 at 19:21
add a comment |
$begingroup$
Would leave as comment, but too long:
Since each path corresponds to a 0-1 bit string on Length $N$, you must implicitly compute the sum of binomial coefficients to determine your final probabilities. I think this is what you are already doing (my interpretation of path counting?). Unfortunately, summing binomial coefficients is infeasible for large values of $N$, so this is the best you are going to be able to do. For large $N$, Determining exact values for the sum of binomial coefficients is not possible (It would make my research a lot easier if it was :)), we only know of good approximations (again, this is assuming N is very large, otherwise you can just sum up the binomial coefficients you're interested in via some math program). Depending on the relationship between $N$ $B$ and $A$, you may be able to find asymptotically tight bounds for the desired probabilities. I would recommend checking out Stirling's approximation, Entropy bounds for binomial coefficients, and related literature. This may be a useful resource if you are interested in the "large N" regime.
EDIT: As a side note, this does not become feasible even when the probability of win/loss is not 1/2. In this regime, you can still get useful bounds using KL-Divergence based estimates of binomial coefficients. This generalizes the entropy bounds mentioned earlier (See this math stack post if you are interested).
answered Jan 2 at 18:17
mm8511mm8511
538210
$endgroup$
Would leave as comment, but too long:
Since each path corresponds to a 0-1 bit string on Length $N$, you must implicitly compute the sum of binomial coefficients to determine your final probabilities. I think this is what you are already doing (my interpretation of path counting?). Unfortunately, summing binomial coefficients is infeasible for large values of $N$, so this is the best you are going to be able to do. For large $N$, Determining exact values for the sum of binomial coefficients is not possible (It would make my research a lot easier if it was :)), we only know of good approximations (again, this is assuming N is very large, otherwise you can just sum up the binomial coefficients you're interested in via some math program). Depending on the relationship between $N$ $B$ and $A$, you may be able to find asymptotically tight bounds for the desired probabilities. I would recommend checking out Stirling's approximation, Entropy bounds for binomial coefficients, and related literature. This may be a useful resource if you are interested in the "large N" regime.
EDIT: As a side note, this does not become feasible even when the probability of win/loss is not 1/2. In this regime, you can still get useful bounds using KL-Divergence based estimates of binomial coefficients. This generalizes the entropy bounds mentioned earlier (See this math stack post if you are interested).
answered Jan 2 at 18:17
mm8511mm8511
538210
edited Jan 2 at 18:22
answered Jan 2 at 18:17
mm8511mm8511
538210
answered Jan 2 at 18:17
mm8511mm8511
538210
answered Jan 2 at 18:17
mm8511mm8511
538210
538210
$begingroup$
Thanks for your reply. A quick point on your reference to very large N values: then there are well-known closed form solutions to a., b., and c. they are a. B/( A+ B) , b. A/(A + B) , c. zero.
$endgroup$
– artbenis
Jan 3 at 19:13
$begingroup$
There are also approximate solutions for them e.g. for c. (A+B - 3)/N.
$endgroup$
– artbenis
Jan 3 at 19:21
add a comment |
$begingroup$
Thanks for your reply. A quick point on your reference to very large N values: then there are well-known closed form solutions to a., b., and c. they are a. B/( A+ B) , b. A/(A + B) , c. zero.
$endgroup$
– artbenis
Jan 3 at 19:13
$begingroup$
There are also approximate solutions for them e.g. for c. (A+B - 3)/N.
$endgroup$
– artbenis
Jan 3 at 19:21
$begingroup$
Thanks for your reply. A quick point on your reference to very large N values: then there are well-known closed form solutions to a., b., and c. they are a. B/( A+ B) , b. A/(A + B) , c. zero.
$endgroup$
– artbenis
Jan 3 at 19:13
$begingroup$
Thanks for your reply. A quick point on your reference to very large N values: then there are well-known closed form solutions to a., b., and c. they are a. B/( A+ B) , b. A/(A + B) , c. zero.
$endgroup$
– artbenis
Jan 3 at 19:13
$begingroup$
There are also approximate solutions for them e.g. for c. (A+B - 3)/N.
$endgroup$
– artbenis
Jan 3 at 19:21
$begingroup$
There are also approximate solutions for them e.g. for c. (A+B - 3)/N.
$endgroup$
– artbenis
Jan 3 at 19:21
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%2f3059671%2fgambler-s-ruin-in-finite-time-solve-by-markov-chains%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
$begingroup$
He will be ruined
$endgroup$
– AkatsukiMaliki
Jan 2 at 17:10
$begingroup$
@AkatsukiMaliki. Not so. For example with A = B= N=2, P of Neither = 1/2.
$endgroup$
– artbenis
Jan 2 at 18:04