Expected value of the number of steps in a walk around the rectangle.
$begingroup$
We have a rectangle $ABCD$.
The walk starts at $A$. Let $X$ be the time required to visit all the vertexes. (We independently go to the adjacent vertex with probability 1/2).
Calculate $EX$.
Some of the calculation I made
$$E|X|=EX=int_0^infty P(X>t)dt=int_0^infty 1-P(X<=t)dt$$
but I have literally hardly any idea on how to calculate $P(X<=t)$. This excercise is ahead of my program at the uni yet, but I would like to know how to compute it.
probability probability-distributions random-walk geometric-probability
asked Dec 6 '18 at 13:08
ryszard egginkryszard eggink
341110
$endgroup$
add a comment |
$begingroup$
We have a rectangle $ABCD$.
The walk starts at $A$. Let $X$ be the time required to visit all the vertexes. (We independently go to the adjacent vertex with probability 1/2).
Calculate $EX$.
Some of the calculation I made
$$E|X|=EX=int_0^infty P(X>t)dt=int_0^infty 1-P(X<=t)dt$$
but I have literally hardly any idea on how to calculate $P(X<=t)$. This excercise is ahead of my program at the uni yet, but I would like to know how to compute it.
probability probability-distributions random-walk geometric-probability
asked Dec 6 '18 at 13:08
ryszard egginkryszard eggink
341110
$endgroup$
$begingroup$
Have you learned about Markov chains yet?
$endgroup$
– saulspatz
Dec 6 '18 at 13:36
$begingroup$
Not yet. But is it neccessary to know a lot of theory to do this?
$endgroup$
– ryszard eggink
Dec 6 '18 at 13:43
$begingroup$
It's a finite-state absorbing Markov chain, so that's certainly one way to do it. I don't see offhand how to do it without that machinery. Wile there's a large theory of Markov chains, very little of it is need for this problem.
$endgroup$
– saulspatz
Dec 6 '18 at 13:51
add a comment |
$begingroup$
We have a rectangle $ABCD$.
The walk starts at $A$. Let $X$ be the time required to visit all the vertexes. (We independently go to the adjacent vertex with probability 1/2).
Calculate $EX$.
Some of the calculation I made
$$E|X|=EX=int_0^infty P(X>t)dt=int_0^infty 1-P(X<=t)dt$$
but I have literally hardly any idea on how to calculate $P(X<=t)$. This excercise is ahead of my program at the uni yet, but I would like to know how to compute it.
probability probability-distributions random-walk geometric-probability
asked Dec 6 '18 at 13:08
ryszard egginkryszard eggink
341110
$endgroup$
We have a rectangle $ABCD$.
The walk starts at $A$. Let $X$ be the time required to visit all the vertexes. (We independently go to the adjacent vertex with probability 1/2).
Calculate $EX$.
Some of the calculation I made
$$E|X|=EX=int_0^infty P(X>t)dt=int_0^infty 1-P(X<=t)dt$$
but I have literally hardly any idea on how to calculate $P(X<=t)$. This excercise is ahead of my program at the uni yet, but I would like to know how to compute it.
probability probability-distributions random-walk geometric-probability
probability probability-distributions random-walk geometric-probability
asked Dec 6 '18 at 13:08
ryszard egginkryszard eggink
341110
asked Dec 6 '18 at 13:08
ryszard egginkryszard eggink
341110
asked Dec 6 '18 at 13:08
ryszard egginkryszard eggink
341110
asked Dec 6 '18 at 13:08
ryszard egginkryszard eggink
341110
asked Dec 6 '18 at 13:08
ryszard egginkryszard eggink
341110
341110
$begingroup$
Have you learned about Markov chains yet?
$endgroup$
– saulspatz
Dec 6 '18 at 13:36
$begingroup$
Not yet. But is it neccessary to know a lot of theory to do this?
$endgroup$
– ryszard eggink
Dec 6 '18 at 13:43
$begingroup$
It's a finite-state absorbing Markov chain, so that's certainly one way to do it. I don't see offhand how to do it without that machinery. Wile there's a large theory of Markov chains, very little of it is need for this problem.
$endgroup$
– saulspatz
Dec 6 '18 at 13:51
add a comment |
$begingroup$
Have you learned about Markov chains yet?
$endgroup$
– saulspatz
Dec 6 '18 at 13:36
$begingroup$
Not yet. But is it neccessary to know a lot of theory to do this?
$endgroup$
– ryszard eggink
Dec 6 '18 at 13:43
$begingroup$
It's a finite-state absorbing Markov chain, so that's certainly one way to do it. I don't see offhand how to do it without that machinery. Wile there's a large theory of Markov chains, very little of it is need for this problem.
$endgroup$
– saulspatz
Dec 6 '18 at 13:51
$begingroup$
Have you learned about Markov chains yet?
$endgroup$
– saulspatz
Dec 6 '18 at 13:36
$begingroup$
Have you learned about Markov chains yet?
$endgroup$
– saulspatz
Dec 6 '18 at 13:36
$begingroup$
Not yet. But is it neccessary to know a lot of theory to do this?
$endgroup$
– ryszard eggink
Dec 6 '18 at 13:43
$begingroup$
Not yet. But is it neccessary to know a lot of theory to do this?
$endgroup$
– ryszard eggink
Dec 6 '18 at 13:43
$begingroup$
It's a finite-state absorbing Markov chain, so that's certainly one way to do it. I don't see offhand how to do it without that machinery. Wile there's a large theory of Markov chains, very little of it is need for this problem.
$endgroup$
– saulspatz
Dec 6 '18 at 13:51
$begingroup$
It's a finite-state absorbing Markov chain, so that's certainly one way to do it. I don't see offhand how to do it without that machinery. Wile there's a large theory of Markov chains, very little of it is need for this problem.
$endgroup$
– saulspatz
Dec 6 '18 at 13:51
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The system can be in one of $5$ states.
State $1:$ we have visited one vertex
State $2:$ we have visited two adjacent vertices
State $3:$ we have visited three vertices and we are at one of the vertices on the ends.
State $4:$ we have visited three vertices and we are at the middle vertex
State $5$: we have visited all vertices
Let $E(i)$ be the expected number of steps remaining to visit all vertices if we are presently in state $i,$ for $i=1,2,3,4,5.$ We start having visited one vertex, so we want to compute E(1). We have $$
begin{align}
E(1)&=1+E(2)\
E(2)&=1+frac12E(2)+frac12E(3)\
E(3)&=1+frac12E(4)+frac12E(5)\
E(4)&=1+E(3)\
E(5)&=0
end{align}$$
Solve the system; $E(1)$ is the answer. If we don't say that vertex A has been visited at the start, but only count a transition to a vertex as a visit to that vertex, then the answer is $1+E(1).$
answered Dec 6 '18 at 14:10
saulspatzsaulspatz
14.6k21329
$endgroup$
add a comment |
$begingroup$
A standard result worth remembering about the symmetric random walk to the nearest neighbours on the integer line, is that the mean number of steps needed to reach $i$ or $j>i$ starting from some $k$ between $i$ and $j$, is $(j-k)(k-i)$.
In particular, the mean number of steps needed to reach $0$ or $n+1$ starting from $1$ is $n$.
To apply this to your problem, consider $t_k$ the mean number of steps needed to visit $k$ vertices, then $t_1=0$, $t_2-t_1=1$ (both obvious), and, more interestingly, $t_3-t_2=2$ and $t_4-t_3=3$. Thus, the mean number of steps needed to visit at least once every vertex of the rectangle is $$t_4=3+2+1=6$$
answered Dec 6 '18 at 14:03
DidDid
247k23223460
$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%2f3028469%2fexpected-value-of-the-number-of-steps-in-a-walk-around-the-rectangle%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The system can be in one of $5$ states.
State $1:$ we have visited one vertex
State $2:$ we have visited two adjacent vertices
State $3:$ we have visited three vertices and we are at one of the vertices on the ends.
State $4:$ we have visited three vertices and we are at the middle vertex
State $5$: we have visited all vertices
Let $E(i)$ be the expected number of steps remaining to visit all vertices if we are presently in state $i,$ for $i=1,2,3,4,5.$ We start having visited one vertex, so we want to compute E(1). We have $$
begin{align}
E(1)&=1+E(2)\
E(2)&=1+frac12E(2)+frac12E(3)\
E(3)&=1+frac12E(4)+frac12E(5)\
E(4)&=1+E(3)\
E(5)&=0
end{align}$$
Solve the system; $E(1)$ is the answer. If we don't say that vertex A has been visited at the start, but only count a transition to a vertex as a visit to that vertex, then the answer is $1+E(1).$
answered Dec 6 '18 at 14:10
saulspatzsaulspatz
14.6k21329
$endgroup$
add a comment |
$begingroup$
The system can be in one of $5$ states.
State $1:$ we have visited one vertex
State $2:$ we have visited two adjacent vertices
State $3:$ we have visited three vertices and we are at one of the vertices on the ends.
State $4:$ we have visited three vertices and we are at the middle vertex
State $5$: we have visited all vertices
Let $E(i)$ be the expected number of steps remaining to visit all vertices if we are presently in state $i,$ for $i=1,2,3,4,5.$ We start having visited one vertex, so we want to compute E(1). We have $$
begin{align}
E(1)&=1+E(2)\
E(2)&=1+frac12E(2)+frac12E(3)\
E(3)&=1+frac12E(4)+frac12E(5)\
E(4)&=1+E(3)\
E(5)&=0
end{align}$$
Solve the system; $E(1)$ is the answer. If we don't say that vertex A has been visited at the start, but only count a transition to a vertex as a visit to that vertex, then the answer is $1+E(1).$
answered Dec 6 '18 at 14:10
saulspatzsaulspatz
14.6k21329
$endgroup$
add a comment |
$begingroup$
The system can be in one of $5$ states.
State $1:$ we have visited one vertex
State $2:$ we have visited two adjacent vertices
State $3:$ we have visited three vertices and we are at one of the vertices on the ends.
State $4:$ we have visited three vertices and we are at the middle vertex
State $5$: we have visited all vertices
Let $E(i)$ be the expected number of steps remaining to visit all vertices if we are presently in state $i,$ for $i=1,2,3,4,5.$ We start having visited one vertex, so we want to compute E(1). We have $$
begin{align}
E(1)&=1+E(2)\
E(2)&=1+frac12E(2)+frac12E(3)\
E(3)&=1+frac12E(4)+frac12E(5)\
E(4)&=1+E(3)\
E(5)&=0
end{align}$$
Solve the system; $E(1)$ is the answer. If we don't say that vertex A has been visited at the start, but only count a transition to a vertex as a visit to that vertex, then the answer is $1+E(1).$
answered Dec 6 '18 at 14:10
saulspatzsaulspatz
14.6k21329
$endgroup$
The system can be in one of $5$ states.
State $1:$ we have visited one vertex
State $2:$ we have visited two adjacent vertices
State $3:$ we have visited three vertices and we are at one of the vertices on the ends.
State $4:$ we have visited three vertices and we are at the middle vertex
State $5$: we have visited all vertices
Let $E(i)$ be the expected number of steps remaining to visit all vertices if we are presently in state $i,$ for $i=1,2,3,4,5.$ We start having visited one vertex, so we want to compute E(1). We have $$
begin{align}
E(1)&=1+E(2)\
E(2)&=1+frac12E(2)+frac12E(3)\
E(3)&=1+frac12E(4)+frac12E(5)\
E(4)&=1+E(3)\
E(5)&=0
end{align}$$
Solve the system; $E(1)$ is the answer. If we don't say that vertex A has been visited at the start, but only count a transition to a vertex as a visit to that vertex, then the answer is $1+E(1).$
answered Dec 6 '18 at 14:10
saulspatzsaulspatz
14.6k21329
edited Dec 27 '18 at 15:50
answered Dec 6 '18 at 14:10
saulspatzsaulspatz
14.6k21329
answered Dec 6 '18 at 14:10
saulspatzsaulspatz
14.6k21329
answered Dec 6 '18 at 14:10
saulspatzsaulspatz
14.6k21329
14.6k21329
add a comment |
add a comment |
$begingroup$
A standard result worth remembering about the symmetric random walk to the nearest neighbours on the integer line, is that the mean number of steps needed to reach $i$ or $j>i$ starting from some $k$ between $i$ and $j$, is $(j-k)(k-i)$.
In particular, the mean number of steps needed to reach $0$ or $n+1$ starting from $1$ is $n$.
To apply this to your problem, consider $t_k$ the mean number of steps needed to visit $k$ vertices, then $t_1=0$, $t_2-t_1=1$ (both obvious), and, more interestingly, $t_3-t_2=2$ and $t_4-t_3=3$. Thus, the mean number of steps needed to visit at least once every vertex of the rectangle is $$t_4=3+2+1=6$$
answered Dec 6 '18 at 14:03
DidDid
247k23223460
$endgroup$
add a comment |
$begingroup$
A standard result worth remembering about the symmetric random walk to the nearest neighbours on the integer line, is that the mean number of steps needed to reach $i$ or $j>i$ starting from some $k$ between $i$ and $j$, is $(j-k)(k-i)$.
In particular, the mean number of steps needed to reach $0$ or $n+1$ starting from $1$ is $n$.
To apply this to your problem, consider $t_k$ the mean number of steps needed to visit $k$ vertices, then $t_1=0$, $t_2-t_1=1$ (both obvious), and, more interestingly, $t_3-t_2=2$ and $t_4-t_3=3$. Thus, the mean number of steps needed to visit at least once every vertex of the rectangle is $$t_4=3+2+1=6$$
answered Dec 6 '18 at 14:03
DidDid
247k23223460
$endgroup$
add a comment |
$begingroup$
A standard result worth remembering about the symmetric random walk to the nearest neighbours on the integer line, is that the mean number of steps needed to reach $i$ or $j>i$ starting from some $k$ between $i$ and $j$, is $(j-k)(k-i)$.
In particular, the mean number of steps needed to reach $0$ or $n+1$ starting from $1$ is $n$.
To apply this to your problem, consider $t_k$ the mean number of steps needed to visit $k$ vertices, then $t_1=0$, $t_2-t_1=1$ (both obvious), and, more interestingly, $t_3-t_2=2$ and $t_4-t_3=3$. Thus, the mean number of steps needed to visit at least once every vertex of the rectangle is $$t_4=3+2+1=6$$
answered Dec 6 '18 at 14:03
DidDid
247k23223460
$endgroup$
A standard result worth remembering about the symmetric random walk to the nearest neighbours on the integer line, is that the mean number of steps needed to reach $i$ or $j>i$ starting from some $k$ between $i$ and $j$, is $(j-k)(k-i)$.
In particular, the mean number of steps needed to reach $0$ or $n+1$ starting from $1$ is $n$.
To apply this to your problem, consider $t_k$ the mean number of steps needed to visit $k$ vertices, then $t_1=0$, $t_2-t_1=1$ (both obvious), and, more interestingly, $t_3-t_2=2$ and $t_4-t_3=3$. Thus, the mean number of steps needed to visit at least once every vertex of the rectangle is $$t_4=3+2+1=6$$
answered Dec 6 '18 at 14:03
DidDid
247k23223460
answered Dec 6 '18 at 14:03
DidDid
247k23223460
answered Dec 6 '18 at 14:03
DidDid
247k23223460
answered Dec 6 '18 at 14:03
DidDid
247k23223460
247k23223460
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%2f3028469%2fexpected-value-of-the-number-of-steps-in-a-walk-around-the-rectangle%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$
Have you learned about Markov chains yet?
$endgroup$
– saulspatz
Dec 6 '18 at 13:36
$begingroup$
Not yet. But is it neccessary to know a lot of theory to do this?
$endgroup$
– ryszard eggink
Dec 6 '18 at 13:43
$begingroup$
It's a finite-state absorbing Markov chain, so that's certainly one way to do it. I don't see offhand how to do it without that machinery. Wile there's a large theory of Markov chains, very little of it is need for this problem.
$endgroup$
– saulspatz
Dec 6 '18 at 13:51