Showing that simple random walks on two graphs have the same type
Question
Let $G$ be a connected infinite graph of bounded degree (which means that there exists $K>0$ such that $text{deg}(v)leq K$ for all vertices $v$ in G). Let $G_k$ be the graph obtained from $G$ by adding an edge $xy$ if it is possible to go from $x$ to $y$ in at most $k$ steps. Using electric network arguments show that simple random walk on $G_k$ is recurrent iff simple random walk on $G$ is recurrent (i.e. both random walks have the same type)
The above problem is from "Random Walks and Electric Networks" by Doyle and Snell.
My attempt
I believe I have been able to show one direction. Namely, suppose that $G$ is transient. Since $G$ can be embedded in $G_k$, by Raleigh's monotonicity law, it is the case that
$$
R_{text{Eff}}(G_k)leq R_{text{Eff}}(G)<infty
$$
where $R_{text{Eff}}$ is the effective resistance. Since $G$ is transient, $ R_{text{Eff}}(G)<infty$ and hence so is $G_k$.
For the converse, I am trying to show that if $G_k$ is transient then so is $G$. I tried to use the result that states that $G$ is transient iff there exists a unit flow from a vertex $v$ to infinity with finite energy. To this end, starting with such a flow in $G_k$, I tried to manipulate the flow in $G_k$ to get the flow in $G$ but I don't know what to do with the flow on the "short-cut" edges of $G_k$. Any help is appreciated.
Methods not involving electrical networks are okay too but electrical network methods are preferred.
probability probability-theory markov-chains random-walk network-flow
asked Dec 4 '18 at 1:54
Foobaz JohnFoobaz John
21.4k41351
add a comment |
Question
Let $G$ be a connected infinite graph of bounded degree (which means that there exists $K>0$ such that $text{deg}(v)leq K$ for all vertices $v$ in G). Let $G_k$ be the graph obtained from $G$ by adding an edge $xy$ if it is possible to go from $x$ to $y$ in at most $k$ steps. Using electric network arguments show that simple random walk on $G_k$ is recurrent iff simple random walk on $G$ is recurrent (i.e. both random walks have the same type)
The above problem is from "Random Walks and Electric Networks" by Doyle and Snell.
My attempt
I believe I have been able to show one direction. Namely, suppose that $G$ is transient. Since $G$ can be embedded in $G_k$, by Raleigh's monotonicity law, it is the case that
$$
R_{text{Eff}}(G_k)leq R_{text{Eff}}(G)<infty
$$
where $R_{text{Eff}}$ is the effective resistance. Since $G$ is transient, $ R_{text{Eff}}(G)<infty$ and hence so is $G_k$.
For the converse, I am trying to show that if $G_k$ is transient then so is $G$. I tried to use the result that states that $G$ is transient iff there exists a unit flow from a vertex $v$ to infinity with finite energy. To this end, starting with such a flow in $G_k$, I tried to manipulate the flow in $G_k$ to get the flow in $G$ but I don't know what to do with the flow on the "short-cut" edges of $G_k$. Any help is appreciated.
Methods not involving electrical networks are okay too but electrical network methods are preferred.
probability probability-theory markov-chains random-walk network-flow
asked Dec 4 '18 at 1:54
Foobaz JohnFoobaz John
21.4k41351
add a comment |
Question
Let $G$ be a connected infinite graph of bounded degree (which means that there exists $K>0$ such that $text{deg}(v)leq K$ for all vertices $v$ in G). Let $G_k$ be the graph obtained from $G$ by adding an edge $xy$ if it is possible to go from $x$ to $y$ in at most $k$ steps. Using electric network arguments show that simple random walk on $G_k$ is recurrent iff simple random walk on $G$ is recurrent (i.e. both random walks have the same type)
The above problem is from "Random Walks and Electric Networks" by Doyle and Snell.
My attempt
I believe I have been able to show one direction. Namely, suppose that $G$ is transient. Since $G$ can be embedded in $G_k$, by Raleigh's monotonicity law, it is the case that
$$
R_{text{Eff}}(G_k)leq R_{text{Eff}}(G)<infty
$$
where $R_{text{Eff}}$ is the effective resistance. Since $G$ is transient, $ R_{text{Eff}}(G)<infty$ and hence so is $G_k$.
For the converse, I am trying to show that if $G_k$ is transient then so is $G$. I tried to use the result that states that $G$ is transient iff there exists a unit flow from a vertex $v$ to infinity with finite energy. To this end, starting with such a flow in $G_k$, I tried to manipulate the flow in $G_k$ to get the flow in $G$ but I don't know what to do with the flow on the "short-cut" edges of $G_k$. Any help is appreciated.
Methods not involving electrical networks are okay too but electrical network methods are preferred.
probability probability-theory markov-chains random-walk network-flow
asked Dec 4 '18 at 1:54
Foobaz JohnFoobaz John
21.4k41351
Question
Let $G$ be a connected infinite graph of bounded degree (which means that there exists $K>0$ such that $text{deg}(v)leq K$ for all vertices $v$ in G). Let $G_k$ be the graph obtained from $G$ by adding an edge $xy$ if it is possible to go from $x$ to $y$ in at most $k$ steps. Using electric network arguments show that simple random walk on $G_k$ is recurrent iff simple random walk on $G$ is recurrent (i.e. both random walks have the same type)
The above problem is from "Random Walks and Electric Networks" by Doyle and Snell.
My attempt
I believe I have been able to show one direction. Namely, suppose that $G$ is transient. Since $G$ can be embedded in $G_k$, by Raleigh's monotonicity law, it is the case that
$$
R_{text{Eff}}(G_k)leq R_{text{Eff}}(G)<infty
$$
where $R_{text{Eff}}$ is the effective resistance. Since $G$ is transient, $ R_{text{Eff}}(G)<infty$ and hence so is $G_k$.
For the converse, I am trying to show that if $G_k$ is transient then so is $G$. I tried to use the result that states that $G$ is transient iff there exists a unit flow from a vertex $v$ to infinity with finite energy. To this end, starting with such a flow in $G_k$, I tried to manipulate the flow in $G_k$ to get the flow in $G$ but I don't know what to do with the flow on the "short-cut" edges of $G_k$. Any help is appreciated.
Methods not involving electrical networks are okay too but electrical network methods are preferred.
probability probability-theory markov-chains random-walk network-flow
probability probability-theory markov-chains random-walk network-flow
asked Dec 4 '18 at 1:54
Foobaz JohnFoobaz John
21.4k41351
asked Dec 4 '18 at 1:54
Foobaz JohnFoobaz John
21.4k41351
asked Dec 4 '18 at 1:54
Foobaz JohnFoobaz John
21.4k41351
asked Dec 4 '18 at 1:54
Foobaz JohnFoobaz John
21.4k41351
asked Dec 4 '18 at 1:54
Foobaz JohnFoobaz John
21.4k41351
21.4k41351
add a comment |
add a comment |
0
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%2f3025020%2fshowing-that-simple-random-walks-on-two-graphs-have-the-same-type%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
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%2f3025020%2fshowing-that-simple-random-walks-on-two-graphs-have-the-same-type%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
