Solving $p_k=frac{1}{2}p_{k+1} + frac{1}{2}p_{k-1}$
$begingroup$
I am trying to solve the recurrence relation
$$p_k=frac{1}{2}p_{k+1} + frac{1}{2}p_{k-1}.$$
The context of this recurrence relation is as follows: if I start with $20, and I win $1 for every head and lose $1 for every tail, I obtain the above recurrence relation for $p$. I lose the overall game if I lose all my money, and win the overall game if I accumulate $100.
Now, I understand that substituting $p_k = p^k$ is the usual approach, which gives $p=1$. While clearly this is a solution, in the context of this above game something’s not right – where in my logic have I gone wrong? Thank you!
probability recurrence-relations problem-solving
$endgroup$
add a comment |
$begingroup$
I am trying to solve the recurrence relation
$$p_k=frac{1}{2}p_{k+1} + frac{1}{2}p_{k-1}.$$
The context of this recurrence relation is as follows: if I start with $20, and I win $1 for every head and lose $1 for every tail, I obtain the above recurrence relation for $p$. I lose the overall game if I lose all my money, and win the overall game if I accumulate $100.
Now, I understand that substituting $p_k = p^k$ is the usual approach, which gives $p=1$. While clearly this is a solution, in the context of this above game something’s not right – where in my logic have I gone wrong? Thank you!
probability recurrence-relations problem-solving
$endgroup$
1
$begingroup$
What do you mean by p?
$endgroup$
– Martund
Dec 20 '18 at 3:55
$begingroup$
This may help.
$endgroup$
– Jam
Dec 20 '18 at 4:04
$begingroup$
The relationship between your recurrence relation and the stated problem is not clear. What do these $p_k$'s represent?
$endgroup$
– Michael Burr
Dec 20 '18 at 4:23
add a comment |
$begingroup$
I am trying to solve the recurrence relation
$$p_k=frac{1}{2}p_{k+1} + frac{1}{2}p_{k-1}.$$
The context of this recurrence relation is as follows: if I start with $20, and I win $1 for every head and lose $1 for every tail, I obtain the above recurrence relation for $p$. I lose the overall game if I lose all my money, and win the overall game if I accumulate $100.
Now, I understand that substituting $p_k = p^k$ is the usual approach, which gives $p=1$. While clearly this is a solution, in the context of this above game something’s not right – where in my logic have I gone wrong? Thank you!
probability recurrence-relations problem-solving
$endgroup$
I am trying to solve the recurrence relation
$$p_k=frac{1}{2}p_{k+1} + frac{1}{2}p_{k-1}.$$
The context of this recurrence relation is as follows: if I start with $20, and I win $1 for every head and lose $1 for every tail, I obtain the above recurrence relation for $p$. I lose the overall game if I lose all my money, and win the overall game if I accumulate $100.
Now, I understand that substituting $p_k = p^k$ is the usual approach, which gives $p=1$. While clearly this is a solution, in the context of this above game something’s not right – where in my logic have I gone wrong? Thank you!
probability recurrence-relations problem-solving
probability recurrence-relations problem-solving
asked Dec 20 '18 at 3:51
user107224user107224
463314
463314
1
$begingroup$
What do you mean by p?
$endgroup$
– Martund
Dec 20 '18 at 3:55
$begingroup$
This may help.
$endgroup$
– Jam
Dec 20 '18 at 4:04
$begingroup$
The relationship between your recurrence relation and the stated problem is not clear. What do these $p_k$'s represent?
$endgroup$
– Michael Burr
Dec 20 '18 at 4:23
add a comment |
1
$begingroup$
What do you mean by p?
$endgroup$
– Martund
Dec 20 '18 at 3:55
$begingroup$
This may help.
$endgroup$
– Jam
Dec 20 '18 at 4:04
$begingroup$
The relationship between your recurrence relation and the stated problem is not clear. What do these $p_k$'s represent?
$endgroup$
– Michael Burr
Dec 20 '18 at 4:23
1
1
$begingroup$
What do you mean by p?
$endgroup$
– Martund
Dec 20 '18 at 3:55
$begingroup$
What do you mean by p?
$endgroup$
– Martund
Dec 20 '18 at 3:55
$begingroup$
This may help.
$endgroup$
– Jam
Dec 20 '18 at 4:04
$begingroup$
This may help.
$endgroup$
– Jam
Dec 20 '18 at 4:04
$begingroup$
The relationship between your recurrence relation and the stated problem is not clear. What do these $p_k$'s represent?
$endgroup$
– Michael Burr
Dec 20 '18 at 4:23
$begingroup$
The relationship between your recurrence relation and the stated problem is not clear. What do these $p_k$'s represent?
$endgroup$
– Michael Burr
Dec 20 '18 at 4:23
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Write
$p_k=frac{1}{2}p_{k+1} + frac{1}{2}p_{k-1}.
$
in the form
$p_{k+1}
=2p_k-p_{k-1}
$.
This has characteristic polynomial
$d^2 = 2d-1$
or
$d^2-2d+1 = 0$
or
$(d-1)^2 = 0$.
The repeated root means that
the two solutions are
$r^k$
and $kr^k$.
The $r^k$ solution gives
$r^{k+1}
=2r^k-r^{k-1}
$
or
$r^2
=2r-1
$,
so $r = 1$
as you got.
The $kr^k$ solution gives,
since $r=1$,
just $k$.
To check, if
$p_k = k$
then
$2p_k-p_{k-1}
=2k-(k-1)
=k+1
=p_{k+1}
$.
Therefore the solutions are
$1$ and $k$,
so the general solution is
$a + bk$.
$endgroup$
1
$begingroup$
Perfect answer. I'd like to add just one thing. $(d-a)^2$ itself gives $a^k$ and $ka^k$ ($a=1$ in this case). You need not put r and evaluate it separately.
$endgroup$
– Ankit Kumar
Dec 20 '18 at 5:00
$begingroup$
I forgot about the repeated root, thank you!
$endgroup$
– user107224
Dec 20 '18 at 9:47
add a comment |
$begingroup$
If $p_0$ and $p_1$ are given, then an easy proof by induction gives
$$p_n=n(p_1-p_0)+p_0.$$
$endgroup$
add a comment |
$begingroup$
A simple argument lets us avoid solving a recurrence relation.
The game is fair, so the expected amount of money you end with is equal to the money you start with. You begin with $20; you end with $100 with some unknown probability $x$, and $0 otherwise. Therefore $20 = 100x$, which yields $x = frac15$.
(Formally, we should check the hypotheses of Wald's identity to know that the expected amount of money you end with is equal to the money you start with. This means we want the number of steps in the game to be a stopping time (which it is: whether you have won or lost after $n$ games depends only on the outcomes of those $n$ games) and finite with probability $1$ (which is true in any finite Markov chain), while the bets should be bounded in addition to being fair.)
$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%2f3047133%2fsolving-p-k-frac12p-k1-frac12p-k-1%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$
Write
$p_k=frac{1}{2}p_{k+1} + frac{1}{2}p_{k-1}.
$
in the form
$p_{k+1}
=2p_k-p_{k-1}
$.
This has characteristic polynomial
$d^2 = 2d-1$
or
$d^2-2d+1 = 0$
or
$(d-1)^2 = 0$.
The repeated root means that
the two solutions are
$r^k$
and $kr^k$.
The $r^k$ solution gives
$r^{k+1}
=2r^k-r^{k-1}
$
or
$r^2
=2r-1
$,
so $r = 1$
as you got.
The $kr^k$ solution gives,
since $r=1$,
just $k$.
To check, if
$p_k = k$
then
$2p_k-p_{k-1}
=2k-(k-1)
=k+1
=p_{k+1}
$.
Therefore the solutions are
$1$ and $k$,
so the general solution is
$a + bk$.
$endgroup$
1
$begingroup$
Perfect answer. I'd like to add just one thing. $(d-a)^2$ itself gives $a^k$ and $ka^k$ ($a=1$ in this case). You need not put r and evaluate it separately.
$endgroup$
– Ankit Kumar
Dec 20 '18 at 5:00
$begingroup$
I forgot about the repeated root, thank you!
$endgroup$
– user107224
Dec 20 '18 at 9:47
add a comment |
$begingroup$
Write
$p_k=frac{1}{2}p_{k+1} + frac{1}{2}p_{k-1}.
$
in the form
$p_{k+1}
=2p_k-p_{k-1}
$.
This has characteristic polynomial
$d^2 = 2d-1$
or
$d^2-2d+1 = 0$
or
$(d-1)^2 = 0$.
The repeated root means that
the two solutions are
$r^k$
and $kr^k$.
The $r^k$ solution gives
$r^{k+1}
=2r^k-r^{k-1}
$
or
$r^2
=2r-1
$,
so $r = 1$
as you got.
The $kr^k$ solution gives,
since $r=1$,
just $k$.
To check, if
$p_k = k$
then
$2p_k-p_{k-1}
=2k-(k-1)
=k+1
=p_{k+1}
$.
Therefore the solutions are
$1$ and $k$,
so the general solution is
$a + bk$.
$endgroup$
1
$begingroup$
Perfect answer. I'd like to add just one thing. $(d-a)^2$ itself gives $a^k$ and $ka^k$ ($a=1$ in this case). You need not put r and evaluate it separately.
$endgroup$
– Ankit Kumar
Dec 20 '18 at 5:00
$begingroup$
I forgot about the repeated root, thank you!
$endgroup$
– user107224
Dec 20 '18 at 9:47
add a comment |
$begingroup$
Write
$p_k=frac{1}{2}p_{k+1} + frac{1}{2}p_{k-1}.
$
in the form
$p_{k+1}
=2p_k-p_{k-1}
$.
This has characteristic polynomial
$d^2 = 2d-1$
or
$d^2-2d+1 = 0$
or
$(d-1)^2 = 0$.
The repeated root means that
the two solutions are
$r^k$
and $kr^k$.
The $r^k$ solution gives
$r^{k+1}
=2r^k-r^{k-1}
$
or
$r^2
=2r-1
$,
so $r = 1$
as you got.
The $kr^k$ solution gives,
since $r=1$,
just $k$.
To check, if
$p_k = k$
then
$2p_k-p_{k-1}
=2k-(k-1)
=k+1
=p_{k+1}
$.
Therefore the solutions are
$1$ and $k$,
so the general solution is
$a + bk$.
$endgroup$
Write
$p_k=frac{1}{2}p_{k+1} + frac{1}{2}p_{k-1}.
$
in the form
$p_{k+1}
=2p_k-p_{k-1}
$.
This has characteristic polynomial
$d^2 = 2d-1$
or
$d^2-2d+1 = 0$
or
$(d-1)^2 = 0$.
The repeated root means that
the two solutions are
$r^k$
and $kr^k$.
The $r^k$ solution gives
$r^{k+1}
=2r^k-r^{k-1}
$
or
$r^2
=2r-1
$,
so $r = 1$
as you got.
The $kr^k$ solution gives,
since $r=1$,
just $k$.
To check, if
$p_k = k$
then
$2p_k-p_{k-1}
=2k-(k-1)
=k+1
=p_{k+1}
$.
Therefore the solutions are
$1$ and $k$,
so the general solution is
$a + bk$.
answered Dec 20 '18 at 4:17
marty cohenmarty cohen
74.5k549129
74.5k549129
1
$begingroup$
Perfect answer. I'd like to add just one thing. $(d-a)^2$ itself gives $a^k$ and $ka^k$ ($a=1$ in this case). You need not put r and evaluate it separately.
$endgroup$
– Ankit Kumar
Dec 20 '18 at 5:00
$begingroup$
I forgot about the repeated root, thank you!
$endgroup$
– user107224
Dec 20 '18 at 9:47
add a comment |
1
$begingroup$
Perfect answer. I'd like to add just one thing. $(d-a)^2$ itself gives $a^k$ and $ka^k$ ($a=1$ in this case). You need not put r and evaluate it separately.
$endgroup$
– Ankit Kumar
Dec 20 '18 at 5:00
$begingroup$
I forgot about the repeated root, thank you!
$endgroup$
– user107224
Dec 20 '18 at 9:47
1
1
$begingroup$
Perfect answer. I'd like to add just one thing. $(d-a)^2$ itself gives $a^k$ and $ka^k$ ($a=1$ in this case). You need not put r and evaluate it separately.
$endgroup$
– Ankit Kumar
Dec 20 '18 at 5:00
$begingroup$
Perfect answer. I'd like to add just one thing. $(d-a)^2$ itself gives $a^k$ and $ka^k$ ($a=1$ in this case). You need not put r and evaluate it separately.
$endgroup$
– Ankit Kumar
Dec 20 '18 at 5:00
$begingroup$
I forgot about the repeated root, thank you!
$endgroup$
– user107224
Dec 20 '18 at 9:47
$begingroup$
I forgot about the repeated root, thank you!
$endgroup$
– user107224
Dec 20 '18 at 9:47
add a comment |
$begingroup$
If $p_0$ and $p_1$ are given, then an easy proof by induction gives
$$p_n=n(p_1-p_0)+p_0.$$
$endgroup$
add a comment |
$begingroup$
If $p_0$ and $p_1$ are given, then an easy proof by induction gives
$$p_n=n(p_1-p_0)+p_0.$$
$endgroup$
add a comment |
$begingroup$
If $p_0$ and $p_1$ are given, then an easy proof by induction gives
$$p_n=n(p_1-p_0)+p_0.$$
$endgroup$
If $p_0$ and $p_1$ are given, then an easy proof by induction gives
$$p_n=n(p_1-p_0)+p_0.$$
answered Dec 20 '18 at 4:19
FredFred
48.6k11849
48.6k11849
add a comment |
add a comment |
$begingroup$
A simple argument lets us avoid solving a recurrence relation.
The game is fair, so the expected amount of money you end with is equal to the money you start with. You begin with $20; you end with $100 with some unknown probability $x$, and $0 otherwise. Therefore $20 = 100x$, which yields $x = frac15$.
(Formally, we should check the hypotheses of Wald's identity to know that the expected amount of money you end with is equal to the money you start with. This means we want the number of steps in the game to be a stopping time (which it is: whether you have won or lost after $n$ games depends only on the outcomes of those $n$ games) and finite with probability $1$ (which is true in any finite Markov chain), while the bets should be bounded in addition to being fair.)
$endgroup$
add a comment |
$begingroup$
A simple argument lets us avoid solving a recurrence relation.
The game is fair, so the expected amount of money you end with is equal to the money you start with. You begin with $20; you end with $100 with some unknown probability $x$, and $0 otherwise. Therefore $20 = 100x$, which yields $x = frac15$.
(Formally, we should check the hypotheses of Wald's identity to know that the expected amount of money you end with is equal to the money you start with. This means we want the number of steps in the game to be a stopping time (which it is: whether you have won or lost after $n$ games depends only on the outcomes of those $n$ games) and finite with probability $1$ (which is true in any finite Markov chain), while the bets should be bounded in addition to being fair.)
$endgroup$
add a comment |
$begingroup$
A simple argument lets us avoid solving a recurrence relation.
The game is fair, so the expected amount of money you end with is equal to the money you start with. You begin with $20; you end with $100 with some unknown probability $x$, and $0 otherwise. Therefore $20 = 100x$, which yields $x = frac15$.
(Formally, we should check the hypotheses of Wald's identity to know that the expected amount of money you end with is equal to the money you start with. This means we want the number of steps in the game to be a stopping time (which it is: whether you have won or lost after $n$ games depends only on the outcomes of those $n$ games) and finite with probability $1$ (which is true in any finite Markov chain), while the bets should be bounded in addition to being fair.)
$endgroup$
A simple argument lets us avoid solving a recurrence relation.
The game is fair, so the expected amount of money you end with is equal to the money you start with. You begin with $20; you end with $100 with some unknown probability $x$, and $0 otherwise. Therefore $20 = 100x$, which yields $x = frac15$.
(Formally, we should check the hypotheses of Wald's identity to know that the expected amount of money you end with is equal to the money you start with. This means we want the number of steps in the game to be a stopping time (which it is: whether you have won or lost after $n$ games depends only on the outcomes of those $n$ games) and finite with probability $1$ (which is true in any finite Markov chain), while the bets should be bounded in addition to being fair.)
answered Dec 20 '18 at 4:45
Misha LavrovMisha Lavrov
47.8k657107
47.8k657107
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%2f3047133%2fsolving-p-k-frac12p-k1-frac12p-k-1%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
1
$begingroup$
What do you mean by p?
$endgroup$
– Martund
Dec 20 '18 at 3:55
$begingroup$
This may help.
$endgroup$
– Jam
Dec 20 '18 at 4:04
$begingroup$
The relationship between your recurrence relation and the stated problem is not clear. What do these $p_k$'s represent?
$endgroup$
– Michael Burr
Dec 20 '18 at 4:23