Random walk on ${0,1,…,k}$, find the average gain in 10 000 steps
I have the following problem which I can't seem to figure out. The problem is as follows.
Consider simple random walk on {0, 1, ... , k} with reflecting
boundaries at 0 and k, that is, random walk on the path from 0 to k. A
random walker earns $k every time the walk reaches 0 or k, but loses
$1 at each internal vertex (from 1 to k − 1). In 10,000 steps of the
walk, how much, on average, will be gained?
I attempt to solve this by introducing a function $r(x) := begin{cases} -1, ;; xin {1,...,k-1} \ k, ;; x in {0,k}end{cases}$. The random walk is clearly a markov chain, which I'll denote $X_0,X_1,...$. The average gain is then simply $frac{1}{n}sum_{k=1}^nr(X_k)$. Here $n = 10 000$.
I have access to a solution to this problem. The person finds the same transition matrix as me for the chain, which simply is defined by letting $P(X_1 = 1 | X_0 = 0) = 1$, $P(X_1 = k-1 | X_0 = k) = 1$ and e.g. $P(X_1 = 2 | X_0 = 1) = 1/2$ and $P(X_1 = 0 | X_0 = 1) = 1/2$ and so on. So there is no problem there. In this solution, however, the person uses the law of large numbers for ergodic Markov chains, i.e. $frac{1}{n}sum_{k=1}^nr(X_k) approx E[r(X)]$ with $X$ distributed with the stationary distrubtion of this Markov chain.
So the problem is that I don't understand how we can use the law of large numbers of ergodic Markov chains in this situation, since I don't see how the Markov chain in this assignment could possibly be ergodic. The chain is clearly irreducible, but when drawing the transition graph for the chain, I find the period of the chain to be 2 thus not a-periodic, and hence not ergodic.
If the chain were ergodic, then there would be no problem since we then simply can find the stationary distribution to the chain and use the law of large numbers for ergodic markov chains and calculate $E[r(X)]$.
So my question is, is the chain above ergodic or not? If it is, how can one see this? If not, maybe there is still a way to use (some version) of law of large numbers to solve the problem in, more or less, the same way (even though the chain is not ergodic)?
Thanks!
probability probability-theory markov-chains markov-process random-walk
asked Dec 8 at 16:59
tarkovsky123
33610
|
show 1 more comment
I have the following problem which I can't seem to figure out. The problem is as follows.
Consider simple random walk on {0, 1, ... , k} with reflecting
boundaries at 0 and k, that is, random walk on the path from 0 to k. A
random walker earns $k every time the walk reaches 0 or k, but loses
$1 at each internal vertex (from 1 to k − 1). In 10,000 steps of the
walk, how much, on average, will be gained?
I attempt to solve this by introducing a function $r(x) := begin{cases} -1, ;; xin {1,...,k-1} \ k, ;; x in {0,k}end{cases}$. The random walk is clearly a markov chain, which I'll denote $X_0,X_1,...$. The average gain is then simply $frac{1}{n}sum_{k=1}^nr(X_k)$. Here $n = 10 000$.
I have access to a solution to this problem. The person finds the same transition matrix as me for the chain, which simply is defined by letting $P(X_1 = 1 | X_0 = 0) = 1$, $P(X_1 = k-1 | X_0 = k) = 1$ and e.g. $P(X_1 = 2 | X_0 = 1) = 1/2$ and $P(X_1 = 0 | X_0 = 1) = 1/2$ and so on. So there is no problem there. In this solution, however, the person uses the law of large numbers for ergodic Markov chains, i.e. $frac{1}{n}sum_{k=1}^nr(X_k) approx E[r(X)]$ with $X$ distributed with the stationary distrubtion of this Markov chain.
So the problem is that I don't understand how we can use the law of large numbers of ergodic Markov chains in this situation, since I don't see how the Markov chain in this assignment could possibly be ergodic. The chain is clearly irreducible, but when drawing the transition graph for the chain, I find the period of the chain to be 2 thus not a-periodic, and hence not ergodic.
If the chain were ergodic, then there would be no problem since we then simply can find the stationary distribution to the chain and use the law of large numbers for ergodic markov chains and calculate $E[r(X)]$.
So my question is, is the chain above ergodic or not? If it is, how can one see this? If not, maybe there is still a way to use (some version) of law of large numbers to solve the problem in, more or less, the same way (even though the chain is not ergodic)?
Thanks!
probability probability-theory markov-chains markov-process random-walk
asked Dec 8 at 16:59
tarkovsky123
33610
If the Markov chain is irreducible and has finitely many states, then it is ergodic. Aperiodicity has nothing to do with this (it is relatede to the stronger property of mixing).
– D. Thomine
Dec 8 at 17:14
Aha. Ok interesting. My text book define a (finite) chain to be ergodic if it is aperiodic and irreducible.
– tarkovsky123
Dec 8 at 17:24
@D.Thomine It is true that an irreducible Markov chain on finitely many states is positive recurrent, but ergodic is usually defined as positive recurrent and aperiodic.
– Math1000
Dec 8 at 22:49
@Math1000: by people who don't know what ergodic means (which is, alas, too frequent - even Wikipedia uses the wrong definition, I should fix it). Conterpoint: a previous answer of mine.
– D. Thomine
Dec 9 at 9:01
And, in order to show that this is not just me: here are a couple of notes using the definition without aperiodicity.
– D. Thomine
Dec 9 at 9:02
|
show 1 more comment
I have the following problem which I can't seem to figure out. The problem is as follows.
Consider simple random walk on {0, 1, ... , k} with reflecting
boundaries at 0 and k, that is, random walk on the path from 0 to k. A
random walker earns $k every time the walk reaches 0 or k, but loses
$1 at each internal vertex (from 1 to k − 1). In 10,000 steps of the
walk, how much, on average, will be gained?
I attempt to solve this by introducing a function $r(x) := begin{cases} -1, ;; xin {1,...,k-1} \ k, ;; x in {0,k}end{cases}$. The random walk is clearly a markov chain, which I'll denote $X_0,X_1,...$. The average gain is then simply $frac{1}{n}sum_{k=1}^nr(X_k)$. Here $n = 10 000$.
I have access to a solution to this problem. The person finds the same transition matrix as me for the chain, which simply is defined by letting $P(X_1 = 1 | X_0 = 0) = 1$, $P(X_1 = k-1 | X_0 = k) = 1$ and e.g. $P(X_1 = 2 | X_0 = 1) = 1/2$ and $P(X_1 = 0 | X_0 = 1) = 1/2$ and so on. So there is no problem there. In this solution, however, the person uses the law of large numbers for ergodic Markov chains, i.e. $frac{1}{n}sum_{k=1}^nr(X_k) approx E[r(X)]$ with $X$ distributed with the stationary distrubtion of this Markov chain.
So the problem is that I don't understand how we can use the law of large numbers of ergodic Markov chains in this situation, since I don't see how the Markov chain in this assignment could possibly be ergodic. The chain is clearly irreducible, but when drawing the transition graph for the chain, I find the period of the chain to be 2 thus not a-periodic, and hence not ergodic.
If the chain were ergodic, then there would be no problem since we then simply can find the stationary distribution to the chain and use the law of large numbers for ergodic markov chains and calculate $E[r(X)]$.
So my question is, is the chain above ergodic or not? If it is, how can one see this? If not, maybe there is still a way to use (some version) of law of large numbers to solve the problem in, more or less, the same way (even though the chain is not ergodic)?
Thanks!
probability probability-theory markov-chains markov-process random-walk
asked Dec 8 at 16:59
tarkovsky123
33610
I have the following problem which I can't seem to figure out. The problem is as follows.
Consider simple random walk on {0, 1, ... , k} with reflecting
boundaries at 0 and k, that is, random walk on the path from 0 to k. A
random walker earns $k every time the walk reaches 0 or k, but loses
$1 at each internal vertex (from 1 to k − 1). In 10,000 steps of the
walk, how much, on average, will be gained?
I attempt to solve this by introducing a function $r(x) := begin{cases} -1, ;; xin {1,...,k-1} \ k, ;; x in {0,k}end{cases}$. The random walk is clearly a markov chain, which I'll denote $X_0,X_1,...$. The average gain is then simply $frac{1}{n}sum_{k=1}^nr(X_k)$. Here $n = 10 000$.
I have access to a solution to this problem. The person finds the same transition matrix as me for the chain, which simply is defined by letting $P(X_1 = 1 | X_0 = 0) = 1$, $P(X_1 = k-1 | X_0 = k) = 1$ and e.g. $P(X_1 = 2 | X_0 = 1) = 1/2$ and $P(X_1 = 0 | X_0 = 1) = 1/2$ and so on. So there is no problem there. In this solution, however, the person uses the law of large numbers for ergodic Markov chains, i.e. $frac{1}{n}sum_{k=1}^nr(X_k) approx E[r(X)]$ with $X$ distributed with the stationary distrubtion of this Markov chain.
So the problem is that I don't understand how we can use the law of large numbers of ergodic Markov chains in this situation, since I don't see how the Markov chain in this assignment could possibly be ergodic. The chain is clearly irreducible, but when drawing the transition graph for the chain, I find the period of the chain to be 2 thus not a-periodic, and hence not ergodic.
If the chain were ergodic, then there would be no problem since we then simply can find the stationary distribution to the chain and use the law of large numbers for ergodic markov chains and calculate $E[r(X)]$.
So my question is, is the chain above ergodic or not? If it is, how can one see this? If not, maybe there is still a way to use (some version) of law of large numbers to solve the problem in, more or less, the same way (even though the chain is not ergodic)?
Thanks!
probability probability-theory markov-chains markov-process random-walk
probability probability-theory markov-chains markov-process random-walk
asked Dec 8 at 16:59
tarkovsky123
33610
asked Dec 8 at 16:59
tarkovsky123
33610
edited Dec 8 at 17:13
asked Dec 8 at 16:59
tarkovsky123
33610
asked Dec 8 at 16:59
tarkovsky123
33610
asked Dec 8 at 16:59
tarkovsky123
33610
33610
If the Markov chain is irreducible and has finitely many states, then it is ergodic. Aperiodicity has nothing to do with this (it is relatede to the stronger property of mixing).
– D. Thomine
Dec 8 at 17:14
Aha. Ok interesting. My text book define a (finite) chain to be ergodic if it is aperiodic and irreducible.
– tarkovsky123
Dec 8 at 17:24
@D.Thomine It is true that an irreducible Markov chain on finitely many states is positive recurrent, but ergodic is usually defined as positive recurrent and aperiodic.
– Math1000
Dec 8 at 22:49
@Math1000: by people who don't know what ergodic means (which is, alas, too frequent - even Wikipedia uses the wrong definition, I should fix it). Conterpoint: a previous answer of mine.
– D. Thomine
Dec 9 at 9:01
And, in order to show that this is not just me: here are a couple of notes using the definition without aperiodicity.
– D. Thomine
Dec 9 at 9:02
|
show 1 more comment
If the Markov chain is irreducible and has finitely many states, then it is ergodic. Aperiodicity has nothing to do with this (it is relatede to the stronger property of mixing).
– D. Thomine
Dec 8 at 17:14
Aha. Ok interesting. My text book define a (finite) chain to be ergodic if it is aperiodic and irreducible.
– tarkovsky123
Dec 8 at 17:24
@D.Thomine It is true that an irreducible Markov chain on finitely many states is positive recurrent, but ergodic is usually defined as positive recurrent and aperiodic.
– Math1000
Dec 8 at 22:49
@Math1000: by people who don't know what ergodic means (which is, alas, too frequent - even Wikipedia uses the wrong definition, I should fix it). Conterpoint: a previous answer of mine.
– D. Thomine
Dec 9 at 9:01
And, in order to show that this is not just me: here are a couple of notes using the definition without aperiodicity.
– D. Thomine
Dec 9 at 9:02
If the Markov chain is irreducible and has finitely many states, then it is ergodic. Aperiodicity has nothing to do with this (it is relatede to the stronger property of mixing).
– D. Thomine
Dec 8 at 17:14
If the Markov chain is irreducible and has finitely many states, then it is ergodic. Aperiodicity has nothing to do with this (it is relatede to the stronger property of mixing).
– D. Thomine
Dec 8 at 17:14
Aha. Ok interesting. My text book define a (finite) chain to be ergodic if it is aperiodic and irreducible.
– tarkovsky123
Dec 8 at 17:24
Aha. Ok interesting. My text book define a (finite) chain to be ergodic if it is aperiodic and irreducible.
– tarkovsky123
Dec 8 at 17:24
@D.Thomine It is true that an irreducible Markov chain on finitely many states is positive recurrent, but ergodic is usually defined as positive recurrent and aperiodic.
– Math1000
Dec 8 at 22:49
@D.Thomine It is true that an irreducible Markov chain on finitely many states is positive recurrent, but ergodic is usually defined as positive recurrent and aperiodic.
– Math1000
Dec 8 at 22:49
@Math1000: by people who don't know what ergodic means (which is, alas, too frequent - even Wikipedia uses the wrong definition, I should fix it). Conterpoint: a previous answer of mine.
– D. Thomine
Dec 9 at 9:01
@Math1000: by people who don't know what ergodic means (which is, alas, too frequent - even Wikipedia uses the wrong definition, I should fix it). Conterpoint: a previous answer of mine.
– D. Thomine
Dec 9 at 9:01
And, in order to show that this is not just me: here are a couple of notes using the definition without aperiodicity.
– D. Thomine
Dec 9 at 9:02
And, in order to show that this is not just me: here are a couple of notes using the definition without aperiodicity.
– D. Thomine
Dec 9 at 9:02
|
show 1 more comment
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%2f3031348%2frandom-walk-on-0-1-k-find-the-average-gain-in-10-000-steps%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
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%2f3031348%2frandom-walk-on-0-1-k-find-the-average-gain-in-10-000-steps%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
If the Markov chain is irreducible and has finitely many states, then it is ergodic. Aperiodicity has nothing to do with this (it is relatede to the stronger property of mixing).
– D. Thomine
Dec 8 at 17:14
Aha. Ok interesting. My text book define a (finite) chain to be ergodic if it is aperiodic and irreducible.
– tarkovsky123
Dec 8 at 17:24
@D.Thomine It is true that an irreducible Markov chain on finitely many states is positive recurrent, but ergodic is usually defined as positive recurrent and aperiodic.
– Math1000
Dec 8 at 22:49
@Math1000: by people who don't know what ergodic means (which is, alas, too frequent - even Wikipedia uses the wrong definition, I should fix it). Conterpoint: a previous answer of mine.
– D. Thomine
Dec 9 at 9:01
And, in order to show that this is not just me: here are a couple of notes using the definition without aperiodicity.
– D. Thomine
Dec 9 at 9:02