Random walk on ${0,1,…,k}$, find the average gain in 10 000 steps












2














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







share|cite|improve this question
























  • 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
















2














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







share|cite|improve this question
























  • 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














2












2








2


1





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







share|cite|improve this question















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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 8 at 17:13

























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


















  • 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















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
});


}
});














draft saved

draft discarded


















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
















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







-

Popular posts from this blog

Bressuire

Image
.mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid ...
Read more

Cabo Verde

Image
  Nota: Cabo-verdiano redireciona para este artigo. Para a língua falada em Cabo Verde, veja crioulo cabo-verdiano. Para outros significados, veja Cabo Verde (desambiguação). Coordenadas: 14° 55' N 23° 31' O Cabo Verde República de Cabo Verde Bandeira Brasão de Armas Lema: Unidade, Trabalho, Progresso Hino nacional: Cântico da Liberdade Gentílico: cabo-verdiano [ 1 ] Capital Praia 14° 55' N 23° 31' O Cidade mais populosa Praia Língua oficial Português Governo República unitária semipresidencialista [ 2 ]  - Presidente Jorge Carlos Fonseca  - Primeiro-ministro Ulisses Correia e Silva História    - Descoberta 1460   - Independência 00 • de Portugal 5 de Julho de 1975   - Multipartidarismo 13 de Janeiro de 1990  Área    - Total 4 033 km² (146.º)  - Água (%) 0,08 População    - Estimativa para 2017 560 899 [ 3 ] hab. (173.º) ...
Read more

Gyllenstierna

Image
.mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid ...
Read more