Effective conductance is symmetric












1














Given a network $G$, and states $x$, and $y$, I want to show that




$mathscr{C}(x leftrightarrow y) = mathscr{C}(yleftrightarrow x)$




I know that $ mathscr{C}(x leftrightarrow y) = pi(x)P(xrightarrow y) $, and so intuitively I can see that the answer can follow from something that is analogous to $pi(u)p(u,v) = pi(v)p(v,u)$, but I was curious if there is an easy, formal, way to see this.



Edit: The transition matrix, $P$, is $pi$-reversible






probability probability-theory graph-theory random-walk network







share|cite|improve this question
























  • What do you assume about the transition matrix $P$?
    – Ian
    Dec 5 '18 at 17:21












  • I don't assume anything in particular, I'm asking after I saw this mentioned in this answer: math.stackexchange.com/a/2250538/82654
    – jackson5
    Dec 5 '18 at 17:23










  • So are you assuming reversibility? This is the type of assumption I had in mind.
    – Ian
    Dec 5 '18 at 17:25










  • Yes. $P$ is reversible wrt to $pi$. Sorry, I was under the assumption that random walks on networks were always reversible.
    – jackson5
    Dec 5 '18 at 17:27






  • 1




    Just to make sure I undertand your notation, by $P(x to y)$ you mean the probability that, starting from $x$, a random walk hits $y$ before returning to $x$?
    – Misha Lavrov
    Dec 5 '18 at 18:59
















1














Given a network $G$, and states $x$, and $y$, I want to show that




$mathscr{C}(x leftrightarrow y) = mathscr{C}(yleftrightarrow x)$




I know that $ mathscr{C}(x leftrightarrow y) = pi(x)P(xrightarrow y) $, and so intuitively I can see that the answer can follow from something that is analogous to $pi(u)p(u,v) = pi(v)p(v,u)$, but I was curious if there is an easy, formal, way to see this.



Edit: The transition matrix, $P$, is $pi$-reversible






probability probability-theory graph-theory random-walk network







share|cite|improve this question
























  • What do you assume about the transition matrix $P$?
    – Ian
    Dec 5 '18 at 17:21












  • I don't assume anything in particular, I'm asking after I saw this mentioned in this answer: math.stackexchange.com/a/2250538/82654
    – jackson5
    Dec 5 '18 at 17:23










  • So are you assuming reversibility? This is the type of assumption I had in mind.
    – Ian
    Dec 5 '18 at 17:25










  • Yes. $P$ is reversible wrt to $pi$. Sorry, I was under the assumption that random walks on networks were always reversible.
    – jackson5
    Dec 5 '18 at 17:27






  • 1




    Just to make sure I undertand your notation, by $P(x to y)$ you mean the probability that, starting from $x$, a random walk hits $y$ before returning to $x$?
    – Misha Lavrov
    Dec 5 '18 at 18:59














1












1








1







Given a network $G$, and states $x$, and $y$, I want to show that




$mathscr{C}(x leftrightarrow y) = mathscr{C}(yleftrightarrow x)$




I know that $ mathscr{C}(x leftrightarrow y) = pi(x)P(xrightarrow y) $, and so intuitively I can see that the answer can follow from something that is analogous to $pi(u)p(u,v) = pi(v)p(v,u)$, but I was curious if there is an easy, formal, way to see this.



Edit: The transition matrix, $P$, is $pi$-reversible






probability probability-theory graph-theory random-walk network







share|cite|improve this question















Given a network $G$, and states $x$, and $y$, I want to show that




$mathscr{C}(x leftrightarrow y) = mathscr{C}(yleftrightarrow x)$




I know that $ mathscr{C}(x leftrightarrow y) = pi(x)P(xrightarrow y) $, and so intuitively I can see that the answer can follow from something that is analogous to $pi(u)p(u,v) = pi(v)p(v,u)$, but I was curious if there is an easy, formal, way to see this.



Edit: The transition matrix, $P$, is $pi$-reversible






probability probability-theory graph-theory random-walk network




probability probability-theory graph-theory random-walk network






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 5 '18 at 17:27







jackson5

















asked Dec 5 '18 at 17:17









jackson5jackson5

606512




606512












  • What do you assume about the transition matrix $P$?
    – Ian
    Dec 5 '18 at 17:21












  • I don't assume anything in particular, I'm asking after I saw this mentioned in this answer: math.stackexchange.com/a/2250538/82654
    – jackson5
    Dec 5 '18 at 17:23










  • So are you assuming reversibility? This is the type of assumption I had in mind.
    – Ian
    Dec 5 '18 at 17:25










  • Yes. $P$ is reversible wrt to $pi$. Sorry, I was under the assumption that random walks on networks were always reversible.
    – jackson5
    Dec 5 '18 at 17:27






  • 1




    Just to make sure I undertand your notation, by $P(x to y)$ you mean the probability that, starting from $x$, a random walk hits $y$ before returning to $x$?
    – Misha Lavrov
    Dec 5 '18 at 18:59


















  • What do you assume about the transition matrix $P$?
    – Ian
    Dec 5 '18 at 17:21












  • I don't assume anything in particular, I'm asking after I saw this mentioned in this answer: math.stackexchange.com/a/2250538/82654
    – jackson5
    Dec 5 '18 at 17:23










  • So are you assuming reversibility? This is the type of assumption I had in mind.
    – Ian
    Dec 5 '18 at 17:25










  • Yes. $P$ is reversible wrt to $pi$. Sorry, I was under the assumption that random walks on networks were always reversible.
    – jackson5
    Dec 5 '18 at 17:27






  • 1




    Just to make sure I undertand your notation, by $P(x to y)$ you mean the probability that, starting from $x$, a random walk hits $y$ before returning to $x$?
    – Misha Lavrov
    Dec 5 '18 at 18:59
















What do you assume about the transition matrix $P$?
– Ian
Dec 5 '18 at 17:21






What do you assume about the transition matrix $P$?
– Ian
Dec 5 '18 at 17:21














I don't assume anything in particular, I'm asking after I saw this mentioned in this answer: math.stackexchange.com/a/2250538/82654
– jackson5
Dec 5 '18 at 17:23




I don't assume anything in particular, I'm asking after I saw this mentioned in this answer: math.stackexchange.com/a/2250538/82654
– jackson5
Dec 5 '18 at 17:23












So are you assuming reversibility? This is the type of assumption I had in mind.
– Ian
Dec 5 '18 at 17:25




So are you assuming reversibility? This is the type of assumption I had in mind.
– Ian
Dec 5 '18 at 17:25












Yes. $P$ is reversible wrt to $pi$. Sorry, I was under the assumption that random walks on networks were always reversible.
– jackson5
Dec 5 '18 at 17:27




Yes. $P$ is reversible wrt to $pi$. Sorry, I was under the assumption that random walks on networks were always reversible.
– jackson5
Dec 5 '18 at 17:27




1




1




Just to make sure I undertand your notation, by $P(x to y)$ you mean the probability that, starting from $x$, a random walk hits $y$ before returning to $x$?
– Misha Lavrov
Dec 5 '18 at 18:59




Just to make sure I undertand your notation, by $P(x to y)$ you mean the probability that, starting from $x$, a random walk hits $y$ before returning to $x$?
– Misha Lavrov
Dec 5 '18 at 18:59










1 Answer
1






active

oldest

votes


















2














We can find the effective conductance in terms of $H(x,y) + H(y,x)$, where $H(x,y)$ is the hitting time: the expected number of steps to reach $y$ starting from $x$. This quantity is symmetric, and therefore effective conductance is symmetric.




We can think of $H(x,y) + H(y,x)$ as the expected number of steps, starting from $x$, until we reach $y$ and we return to $x$. Informally, this should be the average length of an excursion out of $x$ (a random walk that starts at $x$ and ends when it returns to $x$) multiplied by the average number of excursions we need until one of them passes through $y$.



To actually manipulate expected values in this vaguely sketchy fashion, we need to use Wald's identity.



Take an infinite random walk starting at $x$ and let $mathbf X_1, mathbf X_2, mathbf X_3$ be the numbers of steps between visits to $x$ (the lengths of the excursions out of $x$.) Let $mathbf T$ be the index of the first excursion that visits $y$. Then
$$
H(x,y) + H(y,x) = mathbb E[mathbf X_1 + mathbf X_2 + dots + mathbf X_{mathbf T}].
$$
By Wald's identity, $H(x,y) + H(y,x) = mathbb E[mathbf X_1] cdot mathbb E[mathbf T]$. It's a well-known fact that $mathbb E[mathbf X_1] = frac{1}{pi(x)}$. (If you don't know this fact, it also has a proof using Wald's identity.) Meanwhile, $mathbb E[mathbf T] = frac{1}{P(x to y)}$, since $P(x to y)$ is the probability that an excursion out of $x$ visits $y$, so $mathbf T$ is just a geometric random variable for that probability.



Therefore
$$H(x,y) + H(y,x) = frac{1}{pi(x)} cdot frac{1}{P(xto y)} = frac{1}{mathscr{C}(x leftrightarrow y)}$$
and since $frac{1}{H(x,y) + H(y,x)}$ is symmetric in $x$ and $y$, so is effective conductance.






share|cite|improve this answer





















    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%2f3027368%2feffective-conductance-is-symmetric%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    2














    We can find the effective conductance in terms of $H(x,y) + H(y,x)$, where $H(x,y)$ is the hitting time: the expected number of steps to reach $y$ starting from $x$. This quantity is symmetric, and therefore effective conductance is symmetric.




    We can think of $H(x,y) + H(y,x)$ as the expected number of steps, starting from $x$, until we reach $y$ and we return to $x$. Informally, this should be the average length of an excursion out of $x$ (a random walk that starts at $x$ and ends when it returns to $x$) multiplied by the average number of excursions we need until one of them passes through $y$.



    To actually manipulate expected values in this vaguely sketchy fashion, we need to use Wald's identity.



    Take an infinite random walk starting at $x$ and let $mathbf X_1, mathbf X_2, mathbf X_3$ be the numbers of steps between visits to $x$ (the lengths of the excursions out of $x$.) Let $mathbf T$ be the index of the first excursion that visits $y$. Then
    $$
    H(x,y) + H(y,x) = mathbb E[mathbf X_1 + mathbf X_2 + dots + mathbf X_{mathbf T}].
    $$
    By Wald's identity, $H(x,y) + H(y,x) = mathbb E[mathbf X_1] cdot mathbb E[mathbf T]$. It's a well-known fact that $mathbb E[mathbf X_1] = frac{1}{pi(x)}$. (If you don't know this fact, it also has a proof using Wald's identity.) Meanwhile, $mathbb E[mathbf T] = frac{1}{P(x to y)}$, since $P(x to y)$ is the probability that an excursion out of $x$ visits $y$, so $mathbf T$ is just a geometric random variable for that probability.



    Therefore
    $$H(x,y) + H(y,x) = frac{1}{pi(x)} cdot frac{1}{P(xto y)} = frac{1}{mathscr{C}(x leftrightarrow y)}$$
    and since $frac{1}{H(x,y) + H(y,x)}$ is symmetric in $x$ and $y$, so is effective conductance.






    share|cite|improve this answer


























      2














      We can find the effective conductance in terms of $H(x,y) + H(y,x)$, where $H(x,y)$ is the hitting time: the expected number of steps to reach $y$ starting from $x$. This quantity is symmetric, and therefore effective conductance is symmetric.




      We can think of $H(x,y) + H(y,x)$ as the expected number of steps, starting from $x$, until we reach $y$ and we return to $x$. Informally, this should be the average length of an excursion out of $x$ (a random walk that starts at $x$ and ends when it returns to $x$) multiplied by the average number of excursions we need until one of them passes through $y$.



      To actually manipulate expected values in this vaguely sketchy fashion, we need to use Wald's identity.



      Take an infinite random walk starting at $x$ and let $mathbf X_1, mathbf X_2, mathbf X_3$ be the numbers of steps between visits to $x$ (the lengths of the excursions out of $x$.) Let $mathbf T$ be the index of the first excursion that visits $y$. Then
      $$
      H(x,y) + H(y,x) = mathbb E[mathbf X_1 + mathbf X_2 + dots + mathbf X_{mathbf T}].
      $$
      By Wald's identity, $H(x,y) + H(y,x) = mathbb E[mathbf X_1] cdot mathbb E[mathbf T]$. It's a well-known fact that $mathbb E[mathbf X_1] = frac{1}{pi(x)}$. (If you don't know this fact, it also has a proof using Wald's identity.) Meanwhile, $mathbb E[mathbf T] = frac{1}{P(x to y)}$, since $P(x to y)$ is the probability that an excursion out of $x$ visits $y$, so $mathbf T$ is just a geometric random variable for that probability.



      Therefore
      $$H(x,y) + H(y,x) = frac{1}{pi(x)} cdot frac{1}{P(xto y)} = frac{1}{mathscr{C}(x leftrightarrow y)}$$
      and since $frac{1}{H(x,y) + H(y,x)}$ is symmetric in $x$ and $y$, so is effective conductance.






      share|cite|improve this answer
























        2












        2








        2






        We can find the effective conductance in terms of $H(x,y) + H(y,x)$, where $H(x,y)$ is the hitting time: the expected number of steps to reach $y$ starting from $x$. This quantity is symmetric, and therefore effective conductance is symmetric.




        We can think of $H(x,y) + H(y,x)$ as the expected number of steps, starting from $x$, until we reach $y$ and we return to $x$. Informally, this should be the average length of an excursion out of $x$ (a random walk that starts at $x$ and ends when it returns to $x$) multiplied by the average number of excursions we need until one of them passes through $y$.



        To actually manipulate expected values in this vaguely sketchy fashion, we need to use Wald's identity.



        Take an infinite random walk starting at $x$ and let $mathbf X_1, mathbf X_2, mathbf X_3$ be the numbers of steps between visits to $x$ (the lengths of the excursions out of $x$.) Let $mathbf T$ be the index of the first excursion that visits $y$. Then
        $$
        H(x,y) + H(y,x) = mathbb E[mathbf X_1 + mathbf X_2 + dots + mathbf X_{mathbf T}].
        $$
        By Wald's identity, $H(x,y) + H(y,x) = mathbb E[mathbf X_1] cdot mathbb E[mathbf T]$. It's a well-known fact that $mathbb E[mathbf X_1] = frac{1}{pi(x)}$. (If you don't know this fact, it also has a proof using Wald's identity.) Meanwhile, $mathbb E[mathbf T] = frac{1}{P(x to y)}$, since $P(x to y)$ is the probability that an excursion out of $x$ visits $y$, so $mathbf T$ is just a geometric random variable for that probability.



        Therefore
        $$H(x,y) + H(y,x) = frac{1}{pi(x)} cdot frac{1}{P(xto y)} = frac{1}{mathscr{C}(x leftrightarrow y)}$$
        and since $frac{1}{H(x,y) + H(y,x)}$ is symmetric in $x$ and $y$, so is effective conductance.






        share|cite|improve this answer












        We can find the effective conductance in terms of $H(x,y) + H(y,x)$, where $H(x,y)$ is the hitting time: the expected number of steps to reach $y$ starting from $x$. This quantity is symmetric, and therefore effective conductance is symmetric.




        We can think of $H(x,y) + H(y,x)$ as the expected number of steps, starting from $x$, until we reach $y$ and we return to $x$. Informally, this should be the average length of an excursion out of $x$ (a random walk that starts at $x$ and ends when it returns to $x$) multiplied by the average number of excursions we need until one of them passes through $y$.



        To actually manipulate expected values in this vaguely sketchy fashion, we need to use Wald's identity.



        Take an infinite random walk starting at $x$ and let $mathbf X_1, mathbf X_2, mathbf X_3$ be the numbers of steps between visits to $x$ (the lengths of the excursions out of $x$.) Let $mathbf T$ be the index of the first excursion that visits $y$. Then
        $$
        H(x,y) + H(y,x) = mathbb E[mathbf X_1 + mathbf X_2 + dots + mathbf X_{mathbf T}].
        $$
        By Wald's identity, $H(x,y) + H(y,x) = mathbb E[mathbf X_1] cdot mathbb E[mathbf T]$. It's a well-known fact that $mathbb E[mathbf X_1] = frac{1}{pi(x)}$. (If you don't know this fact, it also has a proof using Wald's identity.) Meanwhile, $mathbb E[mathbf T] = frac{1}{P(x to y)}$, since $P(x to y)$ is the probability that an excursion out of $x$ visits $y$, so $mathbf T$ is just a geometric random variable for that probability.



        Therefore
        $$H(x,y) + H(y,x) = frac{1}{pi(x)} cdot frac{1}{P(xto y)} = frac{1}{mathscr{C}(x leftrightarrow y)}$$
        and since $frac{1}{H(x,y) + H(y,x)}$ is symmetric in $x$ and $y$, so is effective conductance.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Dec 5 '18 at 19:09









        Misha LavrovMisha Lavrov

        44.3k555106




        44.3k555106






























            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.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3027368%2feffective-conductance-is-symmetric%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

            Berounka

            Image
            Berounka.mw-parser-output .entete.map{background-image:url("//upload.wikimedia.org/wikipedia/commons/7/7a/Picto_infobox_map.png")} Caractéristiques Longueur 139  km Bassin 8 861  km 2 Bassin collecteur Elbe Débit moyen ? Cours Source Confluence de la Mže et de la Radbuza · Localisation Pilsen · Altitude 305  m · Coordonnées 49° 45′ 13″ N, 13° 23′ 24″ E Confluence Vltava · Localisation Prague · Altitude 187  m · Coordonnées 49° 59′ 43″ N, 14° 24′ 04″ E Géographie Pays traversés   République tchèque modifier   La Berounka est une rivière de la République tchèque. Elle porte le nom de Mže depuis sa source en Allemagne près de la frontière jusqu'à sa confluence avec la Radbuza à Plzeň. Elle continue ensuite sous le nom de Berounka jusqu'à sa confluence avec la Vltava, près de Prague. La rivière est une destination prisée pour les amateurs de canoë, qui appréc...
            Read more

            Sphinx de Gizeh

            Image
            Pour les articles homonymes, voir Sphinx. Sphinx de Gizeh.mw-parser-output .entete.egypte-antique{background-image:url("//upload.wikimedia.org/wikipedia/commons/c/cc/Picto_infobox_ancient_Egypt.png")} Site d'Égypte antique Le visage du sphinx de Gizeh. Noms en arabe أبو الهول , Abou al-Hôl Localisation Région Basse-Égypte Coordonnées 29° 58′ 31″ nord, 31° 08′ 16″ est Géolocalisation sur la carte : Égypte Sphinx de Gizeh modifier   Le sphinx de Gizeh est la statue thérianthrope qui se dresse devant les grandes pyramides du plateau de Gizeh, en Basse-Égypte. Sculpture monumentale monolithique la plus grande du monde [ 1 ] avec 73,5 mètres de longueur, 14 mètres de largeur et 20,22 mètres de hauteur, elle représente un sphinx couchant. Réalisée vers -2500, elle serait attribuée à Djédefrê, l'un des pharaons de la IV e  dynastie, représentant son père le pharaon Khéops. Sommaire 1 Étymologie 2 Desc...
            Read more

            Different font size/position of beamer's navigation symbols template's content depending on regular/plain...

            Image
            3 Let's suppose I'd like to divert the navigation symbols template (e.g. in order replace them by the frame numbers, see this bug report ;) I would be facing troubles regarding the font size/position, depending on regular/plain frames, as shown by the following MCE. How could I get rid of these troubles? documentclass{beamer} usetheme{PaloAlto} setbeamertemplate{navigation symbols}{insertframenumber/inserttotalframenumber} begin{document} begin{frame} frametitle{A regular frame} end{frame} begin{frame}[plain] frametitle{A plain frame} end{frame} end{document} beamer header-footer share | improve this question asked Dec 10 '18 a...
            Read more