Transcription
Random Walks and Electrical NetworksElectrical Network Calculations in Random Walks inRandom EnvironmentsJonathon PetersonSchool of MathematicsUniversity of MinnesotaFebruary 4, 2008Jonathon Peterson2/4/20081 / 23
Random Walks and Electrical NetworksMuch of this talk is based on the book Random Walks and ElectricNetworks by Peter G. Doyle and J. Laurie Snell.Free download available athttp://arxiv.org/abs/math/0001057Some of the graphics in this talk are also from this book.Jonathon Peterson2/4/20082 / 23
Random Walks and Electrical NetworksOutline1Markov Chains2Electrical Networks and Reversible Markov Chains3Probability Calculations Electrical Calculations4Simple Random Walks5Random Walks in Random EnvironmentsJonathon Peterson2/4/20083 / 23
Random Walks and Electrical NetworksMarkov ChainsMarkov ChainsMarkov chain: a random process Xn with short term memory.Movement governed by transition probabilities:P(Xn 1 y Xn x) px,yExample: t 0tttt1234 t5 p0,0 1pi,i 1 pi,i 1 1/2if i 1, 2, 3, or 4p5,5 1Jonathon Peterson2/4/20084 / 23
Random Walks and Electrical NetworksMarkov ChainsMarkov ChainsMarkov chain: a random process Xn with short term memory.Movement governed by transition probabilities:P(Xn 1 y Xn x) px,yExample: t 0tttt1234 t5 p0,0 1pi,i 1 pi,i 1 1/2if i 1, 2, 3, or 4p5,5 1Jonathon Peterson2/4/20084 / 23
Random Walks and Electrical NetworksMarkov ChainsMarkov ChainsMarkov chain: a random process Xn with short term memory.Movement governed by transition probabilities:P(Xn 1 y Xn x) px,yExample: t 0tttt1234 t5 p0,0 1pi,i 1 pi,i 1 1/2if i 1, 2, 3, or 4p5,5 1Jonathon Peterson2/4/20084 / 23
Random Walks and Electrical NetworksMarkov ChainsExamplesPopulation models: Xn size of population on day n.Stock market: Xn price of stock on day n.Spread of disease: Xn subset of population infected on day n.{}{A}u@@@@@u{B}u@@@@@u{A, B}Jonathon Peterson2/4/20085 / 23
Random Walks and Electrical NetworksMarkov ChainsExamplesPopulation models: Xn size of population on day n.Stock market: Xn price of stock on day n.Spread of disease: Xn subset of population infected on day n.{}{A}u@@@@@u{B}u@@@@@u{A, B}Jonathon Peterson2/4/20085 / 23
Random Walks and Electrical NetworksMarkov ChainsExamplesPopulation models: Xn size of population on day n.Stock market: Xn price of stock on day n.Spread of disease: Xn subset of population infected on day n.{}{A}u@@@@@u{B}u@@@@@u{A, B}Jonathon Peterson2/4/20085 / 23
Random Walks and Electrical NetworksElectrical Networks and Reversible Markov ChainsElectrical NetworksRx,y resistance of the edge from x to y.Cx,y R1x,y conductance of the edge from x to y.PCx y Cx,y . Total conductance at x.Jonathon Peterson2/4/20086 / 23
Random Walks and Electrical NetworksElectrical Networks and Reversible Markov ChainsReversible Markov ChainsGiven an electrical network, let px,y Cx,yCx .Example: pb,c 1/3 and pb,d 2/3.These Markov chains are called reversible Markov chains.When is a Markov chain reversible?Jonathon Peterson2/4/20087 / 23
Random Walks and Electrical NetworksElectrical Networks and Reversible Markov ChainsReversible Markov ChainsGiven an electrical network, let px,y Cx,yCx .Example: pb,c 1/3 and pb,d 2/3.These Markov chains are called reversible Markov chains.When is a Markov chain reversible?Jonathon Peterson2/4/20087 / 23
Random Walks and Electrical NetworksElectrical Networks and Reversible Markov ChainsReversible Markov ChainsGiven an electrical network, let px,y Cx,yCx .Example: pb,c 1/3 and pb,d 2/3.These Markov chains are called reversible Markov chains.When is a Markov chain reversible?Jonathon Peterson2/4/20087 / 23
Random Walks and Electrical NetworksElectrical Networks and Reversible Markov ChainsReversible Markov ChainsGiven an electrical network, let px,y Cx,yCx .Example: pb,c 1/3 and pb,d 2/3.These Markov chains are called reversible Markov chains.When is a Markov chain reversible?Jonathon Peterson2/4/20087 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageHitting ProbabilitiesHitting times: Ty : inf{n 0 : Xn y}.We want to calculate hitting probabilities:h(x) : P(Ta Tb X0 x) P x (Ta Tb ).Obviously h(a) 1 and h(b) 0.For x 6 a, bXXh(x) px,y P y (Ta Tb ) px,y h(y)yyh(x) is a harmonic function.Jonathon Peterson2/4/20088 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageHitting ProbabilitiesHitting times: Ty : inf{n 0 : Xn y}.We want to calculate hitting probabilities:h(x) : P(Ta Tb X0 x) P x (Ta Tb ).Obviously h(a) 1 and h(b) 0.For x 6 a, bXXh(x) px,y P y (Ta Tb ) px,y h(y)yyh(x) is a harmonic function.Jonathon Peterson2/4/20088 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageHitting ProbabilitiesHitting times: Ty : inf{n 0 : Xn y}.We want to calculate hitting probabilities:h(x) : P(Ta Tb X0 x) P x (Ta Tb ).Obviously h(a) 1 and h(b) 0.For x 6 a, bXXh(x) px,y P y (Ta Tb ) px,y h(y)yyh(x) is a harmonic function.Jonathon Peterson2/4/20088 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageHitting ProbabilitiesHitting times: Ty : inf{n 0 : Xn y}.We want to calculate hitting probabilities:h(x) : P(Ta Tb X0 x) P x (Ta Tb ).Obviously h(a) 1 and h(b) 0.For x 6 a, bXXh(x) px,y P y (Ta Tb ) px,y h(y)yyh(x) is a harmonic function.Jonathon Peterson2/4/20088 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageHarmonic FunctionsGraph G with edge weights px,y .Subset of vertices B called the boundary.h(x) is (G, B, p)-harmonic ifXh(x) px,y h(y ) for all x / B.yTheorem (Maximum (Minimum) Principle)If h(x) is (G, B, p)-harmonic, then h(x) takes on its maximum (andminimum) values on the boundary.Jonathon Peterson2/4/20089 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageHarmonic FunctionsGraph G with edge weights px,y .Subset of vertices B called the boundary.h(x) is (G, B, p)-harmonic ifXh(x) px,y h(y ) for all x / B.yTheorem (Maximum (Minimum) Principle)If h(x) is (G, B, p)-harmonic, then h(x) takes on its maximum (andminimum) values on the boundary.Jonathon Peterson2/4/20089 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageHarmonic FunctionsAn easy consequence of the Maximum Principle is:Theorem (Uniqueness Principle)If h(x) and v (x) are both (G, B, p)-harmonic functions with h(x) v (x)for all boundary points x B, then v (x) u(x) for all x.Proof.u(x) h(x) v (x) is also (G, B, p)-harmonic.u(x) 0 for all x B.By the Maximum (and minimum) principle, u(x) 0 for all x.h(x) P(Ta Tb X0 x) is the unique (G, {a, b}, p)-harmonicfunction with boundary values h(a) 1 and h(b) 0.Jonathon Peterson2/4/200810 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageHarmonic FunctionsAn easy consequence of the Maximum Principle is:Theorem (Uniqueness Principle)If h(x) and v (x) are both (G, B, p)-harmonic functions with h(x) v (x)for all boundary points x B, then v (x) u(x) for all x.Proof.u(x) h(x) v (x) is also (G, B, p)-harmonic.u(x) 0 for all x B.By the Maximum (and minimum) principle, u(x) 0 for all x.h(x) P(Ta Tb X0 x) is the unique (G, {a, b}, p)-harmonicfunction with boundary values h(a) 1 and h(b) 0.Jonathon Peterson2/4/200810 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageHarmonic FunctionsAn easy consequence of the Maximum Principle is:Theorem (Uniqueness Principle)If h(x) and v (x) are both (G, B, p)-harmonic functions with h(x) v (x)for all boundary points x B, then v (x) u(x) for all x.Proof.u(x) h(x) v (x) is also (G, B, p)-harmonic.u(x) 0 for all x B.By the Maximum (and minimum) principle, u(x) 0 for all x.h(x) P(Ta Tb X0 x) is the unique (G, {a, b}, p)-harmonicfunction with boundary values h(a) 1 and h(b) 0.Jonathon Peterson2/4/200810 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageHarmonic FunctionsAn easy consequence of the Maximum Principle is:Theorem (Uniqueness Principle)If h(x) and v (x) are both (G, B, p)-harmonic functions with h(x) v (x)for all boundary points x B, then v (x) u(x) for all x.Proof.u(x) h(x) v (x) is also (G, B, p)-harmonic.u(x) 0 for all x B.By the Maximum (and minimum) principle, u(x) 0 for all x.h(x) P(Ta Tb X0 x) is the unique (G, {a, b}, p)-harmonicfunction with boundary values h(a) 1 and h(b) 0.Jonathon Peterson2/4/200810 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageHarmonic FunctionsAn easy consequence of the Maximum Principle is:Theorem (Uniqueness Principle)If h(x) and v (x) are both (G, B, p)-harmonic functions with h(x) v (x)for all boundary points x B, then v (x) u(x) for all x.Proof.u(x) h(x) v (x) is also (G, B, p)-harmonic.u(x) 0 for all x B.By the Maximum (and minimum) principle, u(x) 0 for all x.h(x) P(Ta Tb X0 x) is the unique (G, {a, b}, p)-harmonicfunction with boundary values h(a) 1 and h(b) 0.Jonathon Peterson2/4/200810 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageVoltageConnect a 1V battery to nodes a and b.ix,y is the current from x to y .v (x) is the voltage at node x. v (a) 1 and v (b) 0.Ohm’s Law: ix,y (v (x) v (y ))Cx,y .PKirchoff’s Current Law: y ix,y 0, for x 6 a, b.Jonathon Peterson2/4/200811 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageVoltageConnect a 1V battery to nodes a and b.ix,y is the current from x to y .v (x) is the voltage at node x. v (a) 1 and v (b) 0.Ohm’s Law: ix,y (v (x) v (y ))Cx,y .PKirchoff’s Current Law: y ix,y 0, for x 6 a, b.Jonathon Peterson2/4/200811 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageVoltageConnect a 1V battery to nodes a and b.ix,y is the current from x to y .v (x) is the voltage at node x. v (a) 1 and v (b) 0.Ohm’s Law: ix,y (v (x) v (y ))Cx,y .PKirchoff’s Current Law: y ix,y 0, for x 6 a, b.Jonathon Peterson2/4/200811 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageVoltageFor x / {a, b},X0 ix,y(Kirchoff’s Law)y X(v (x) v (y))Cx,y(Ohm’s Law)y v (x)Cx Xv (y )Cx,y .yThereforev (x) X Cx,yyCxv (y), x / {a, b},and so voltage is a harmonic function.Jonathon Peterson2/4/200812 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageVoltageFor x / {a, b},X0 ix,y(Kirchoff’s Law)y X(v (x) v (y))Cx,y(Ohm’s Law)y v (x)Cx Xv (y )Cx,y .yThereforev (x) X Cx,yyCxv (y), x / {a, b},and so voltage is a harmonic function.Jonathon Peterson2/4/200812 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageHitting Probabilities and VoltageFor a Markov chain with transition probabilities px,y Cx,yCxh(x) P x (Ta Tb ) v (x).Jonathon Peterson2/4/200813 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageExample: Hitting Probabilities on an Intervali is the total current flowing through the circuit.R(x y) is the effective resistance between x and y.1is the effective conductance between x and y .C(x y ) R(x y)By Ohm’s Law: v (x) v (x) v (b) iR(x b).Since v (a) 1 this gives i 1R(a b) ,and thereforeP x (Ta Tb ) v (x) Jonathon PetersonR(x b)R(a b)2/4/200814 / 23
Random Walks and Electrical NetworksHitting Probabilities and VoltageExample: Hitting Probabilities on an Intervali is the total current flowing through the circuit.R(x y) is the effective resistance between x and y.1is the effective conductance between x and y .C(x y ) R(x y)By Ohm’s Law: v (x) v (x) v (b) iR(x b).Since v (a) 1 this gives i 1R(a b) ,and thereforeP x (Ta Tb ) v (x) Jonathon PetersonR(x b)R(a b)2/4/200814 / 23
Random Walks and Electrical NetworksRandom Walk CalculationsSimple Symmetric Random Walkpi,i 1 pi,i 1 121 Ohm resistors at every edge.s1ss 1s 1 s1s1ss 1s0P 0 (Tr T ) rR(0 ) .R(r )r P 0 (Tr ) lim P 0 (Tr T ) lim 1.r Simple symmetric random walk is recurrent.Jonathon Peterson2/4/200815 / 23
Random Walks and Electrical NetworksRandom Walk CalculationsSimple Symmetric Random Walkpi,i 1 pi,i 1 121 Ohm resistors at every edge.s1ss 1s 1 s1s1ss 1s0P 0 (Tr T ) rR(0 ) .R(r )r P 0 (Tr ) lim P 0 (Tr T ) lim 1.r Simple symmetric random walk is recurrent.Jonathon Peterson2/4/200815 / 23
Random Walks and Electrical NetworksRandom Walk CalculationsSimple Symmetric Random Walkpi,i 1 pi,i 1 121 Ohm resistors at every edge.s1ss 1s 1 s1s1ss 1s0P 0 (Tr T ) rR(0 ) .R(r )r P 0 (Tr ) lim P 0 (Tr T ) lim 1.r Simple symmetric random walk is recurrent.Jonathon Peterson2/4/200815 / 23
Random Walks and Electrical NetworksRandom Walk CalculationsSimple Symmetric Random Walkpi,i 1 pi,i 1 121 Ohm resistors at every edge.s1ss 1s 1 s1s1ss 1s0P 0 (Tr T ) rR(0 ) .R(r )r P 0 (Tr ) lim P 0 (Tr T ) lim 1.r Simple symmetric random walk is recurrent.Jonathon Peterson2/4/200815 / 23
Random Walks and Electrical NetworksRandom Walk CalculationsSimple Asymmetric Random WalkLet12 ω 1.pi,i 1 ωsss Define ρ : ss10If R0,1 1, then ω Thus C1,2 sand pi,i 1 1 ωω1 ω ,1 ωωsssrC1,21 C1,2 .or equivalently R1,2 1 ωω . 1.Jonathon Peterson2/4/200816 / 23
Random Walks and Electrical NetworksRandom Walk CalculationsSimple Asymmetric Random WalkLet12 ω 1.pi,i 1 ωsss Define ρ : ss10If R0,1 1, then ω Thus C1,2 sand pi,i 1 1 ωω1 ω ,1 ωωsssrC1,21 C1,2 .or equivalently R1,2 1 ωω . 1.Jonathon Peterson2/4/200816 / 23
Random Walks and Electrical NetworksRandom Walk CalculationsSimple Asymmetric Random WalkLet12 ω 1, ρ sρ s1 ωω 1.s ρ 2 s ρ 1 s s1ρs0Then R(0 r ) 1 ρ · · · ρr 1 r1 ρr1 ρ .and R(0 ) ρ 1 ρ 2 · · · ρ Therefore R(r ) s ρr 1 sρ 11 ρ .ρ ρr1 ρ .ρ 1 1. ρ ρrP 0 (Tr ) lim P 0 (Tr T ) lim 1 ρr ρ 1.r r ρ ρrSimple asymmetric random walk is transient.P 0 (T ) lim P 0 (T Tr ) limJonathon Peterson2/4/200817 / 23
Random Walks and Electrical NetworksRandom Walk CalculationsSimple Asymmetric Random WalkLet12 ω 1, ρ sρ s1 ωω 1.s ρ 2 s ρ 1 s s1ρs0Then R(0 r ) 1 ρ · · · ρr 1 r1 ρr1 ρ .and R(0 ) ρ 1 ρ 2 · · · ρ Therefore R(r ) s ρr 1 sρ 11 ρ .ρ ρr1 ρ .ρ 1 1. ρ ρrP 0 (Tr ) lim P 0 (Tr T ) lim 1 ρr ρ 1.r r ρ ρrSimple asymmetric random walk is transient.P 0 (T ) lim P 0 (T Tr ) limJonathon Peterson2/4/200817 / 23
Random Walks and Electrical NetworksRandom Walk CalculationsSimple Asymmetric Random WalkLet12 ω 1, ρ sρ s1 ωω 1.s ρ 2 s ρ 1 s s1ρs0Then R(0 r ) 1 ρ · · · ρr 1 r1 ρr1 ρ .and R(0 ) ρ 1 ρ 2 · · · ρ Therefore R(r ) s ρr 1 sρ 11 ρ .ρ ρr1 ρ .ρ 1 1. ρ ρrP 0 (Tr ) lim P 0 (Tr T ) lim 1 ρr ρ 1.r r ρ ρrSimple asymmetric random walk is transient.P 0 (T ) lim P 0 (T Tr ) limJonathon Peterson2/4/200817 / 23
Random Walks and Electrical NetworksRandom Walk CalculationsSimple Asymmetric Random WalkLet12 ω 1, ρ sρ s1 ωω 1.s ρ 2 s ρ 1 s s1ρs0Then R(0 r ) 1 ρ · · · ρr 1 r1 ρr1 ρ .and R(0 ) ρ 1 ρ 2 · · · ρ Therefore R(r ) s ρr 1 sρ 11 ρ .ρ ρr1 ρ .ρ 1 1. ρ ρrP 0 (Tr ) lim P 0 (Tr T ) lim 1 ρr ρ 1.r r ρ ρrSimple asymmetric random walk is transient.P 0 (T ) lim P 0 (T Tr ) limJonathon Peterson2/4/200817 / 23
Random Walks and Electrical NetworksRandom Walk CalculationsSimple Asymmetric Random WalkLet12 ω 1, ρ sρ s1 ωω 1.s ρ 2 s ρ 1 s s1ρs0Then R(0 r ) 1 ρ · · · ρr 1 r1 ρr1 ρ .and R(0 ) ρ 1 ρ 2 · · · ρ Therefore R(r ) s ρr 1 sρ 11 ρ .ρ ρr1 ρ .ρ 1 1. ρ ρrP 0 (Tr ) lim P 0 (Tr T ) lim 1 ρr ρ 1.r r ρ ρrSimple asymmetric random walk is transient.P 0 (T ) lim P 0 (T Tr ) limJonathon Peterson2/4/200817 / 23
Random Walks and Electrical NetworksRandom Walk CalculationsSimple Asymmetric Random WalkLet12 ω 1, ρ sρ s1 ωω 1.s ρ 2 s ρ 1 s s1ρs0Then R(0 r ) 1 ρ · · · ρr 1 r1 ρr1 ρ .and R(0 ) ρ 1 ρ 2 · · · ρ Therefore R(r ) s ρr 1 sρ 11 ρ .ρ ρr1 ρ .ρ 1 1. ρ ρrP 0 (Tr ) lim P 0 (Tr T ) lim 1 ρr ρ 1.r r ρ ρrSimple asymmetric random walk is transient.P 0 (T ) lim P 0 (T Tr ) limJonathon Peterson2/4/200817 / 23
Random Walks and Electrical NetworksRandom Walks in Random EnvironmentsRWRE ModelFirst pick Random Environment: i.i.d. sequence ωx , x Z.Then run markov chain with px,x 1 ωx and px,x 1 1 ωxQuestion: When is a RWRE transient to ?- When P 0 (X1 1) 21 ?Jonathon Peterson2/4/200818 / 23
Random Walks and Electrical NetworksRandom Walks in Random EnvironmentsRWRE ModelFirst pick Random Environment: i.i.d. sequence ωx , x Z.Then run markov chain with px,x 1 ωx and px,x 1 1 ωxQuestion: When is a RWRE transient to ?- When P 0 (X1 1) 21 ?Jonathon Peterson2/4/200818 / 23
Random Walks and Electrical NetworksRandom Walks in Random EnvironmentsRWRE ModelFirst pick Random Environment: i.i.d. sequence ωx , x Z.Then run markov chain with px,x 1 ωx and px,x 1 1 ωxQuestion: When is a RWRE transient to ?- When P 0 (X1 1) 12 ?Jonathon Peterson2/4/200818 / 23
Random Walks and Electrical NetworksRandom Walks in Random EnvironmentsRWRE ModelFirst pick Random Environment: i.i.d. sequence ωx , x Z.Then run markov chain with px,x 1 ωx and px,x 1 1 ωxQuestion: When is a RWRE transient to ?- When P 0 (X1 1) 12 ?Jonathon Peterson2/4/200818 / 23
Random Walks and Electrical NetworksRandom Walks in Random EnvironmentsElectrical Network for RWRE ModelGiven a random environment, defineρx : (ρ0 ρ 1 · · · ρ 1 ) 1ss s(ρ0 ρ 1 ) 1 ρ 10s1 ωx.ωxρ1 ρ2 · · · ρr 1s1sρ1ss0srR(0 ) 1 ρ1 ρ1 ρ2 ρ1 ρ2 ρ3 · · · 1R(0 ) ρ 1 (ρ0 ρ 1 ρ 2 ) 1 · · ·0 (ρ0 ρ 1 )Guess: RWRE is transient to if E(ρ) 1.Jonathon Peterson2/4/200819 / 23
Random Walks and Electrical NetworksRandom Walks in Random EnvironmentsElectrical Network for RWRE ModelGiven a random environment, defineρx : (ρ0 ρ 1 · · · ρ 1 ) 1ss s(ρ0 ρ 1 ) 1 ρ 10s1 ωx.ωxρ1 ρ2 · · · ρr 1s1sρ1ss0srR(0 ) 1 ρ1 ρ1 ρ2 ρ1 ρ2 ρ3 · · · 1R(0 ) ρ 1 (ρ0 ρ 1 ρ 2 ) 1 · · ·0 (ρ0 ρ 1 )Guess: RWRE is transient to if E(ρ) 1.Jonathon Peterson2/4/200819 / 23
Random Walks and Electrical NetworksRandom Walks in Random EnvironmentsElectrical Network for RWRE ModelGiven a random environment, defineρx : (ρ0 ρ 1 · · · ρ 1 ) 1ss s(ρ0 ρ 1 ) 1 ρ 10s1 ωx.ωxρ1 ρ2 · · · ρr 1s1sρ1ss0srR(0 ) 1 ρ1 ρ1 ρ2 ρ1 ρ2 ρ3 · · · 1R(0 ) ρ 1 (ρ0 ρ 1 ρ 2 ) 1 · · ·0 (ρ0 ρ 1 )Guess: RWRE is transient to if E(ρ) 1.Jonathon Peterson2/4/200819 / 23
Random Walks and Electrical NetworksRandom Walks in Random EnvironmentsTransience/Recurrence Criteria for RWREWant R(0 ) 1 ρ1 ρ1 ρ2 ρ1 ρ2 ρ3 · · · .ρ1 ρ2 · · · ρn elog(ρ1 ρ2 ···ρn ) ePni 11 e( nlog ρiPni 1log ρi )n eE(log ρ0 )n(Law of Large Numbers)Theorem (Solomon ’75)(a)EP (log ρ0 ) 0 lim Xn (b)EP (log ρ0 ) 0 lim Xn (c)EP (log ρ0 ) 0 Xn is recurrentn n Jonathon Peterson2/4/200820 / 23
Random Walks and Electrical NetworksRandom Walks in Random EnvironmentsTransience/Recurrence Criteria for RWREWant R(0 ) 1 ρ1 ρ1 ρ2 ρ1 ρ2 ρ3 · · · .ρ1 ρ2 · · · ρn elog(ρ1 ρ2 ···ρn ) ePni 11 e( nlog ρiPni 1log ρi )n eE(log ρ0 )n(Law of Large Numbers)Theorem (Solomon ’75)(a)EP (log ρ0 ) 0 lim Xn (b)EP (log ρ0 ) 0 lim Xn (c)EP (log ρ0 ) 0 Xn is recurrentn n Jonathon Peterson2/4/200820 / 23
Random Walks and Electrical NetworksRandom Walks in Random EnvironmentsExample:Suppose the distribution on environments is: 31P ω0 .39 and P ω0 .6143Then311191P(X1 1) .39 .61 ,432402and Eρ0 .391 3/43/4 .611 1/31/3 27 1.20However,EP (log ρ0 ) 0.00563901 0and so the RWRE is transient to .Jonathon Peterson2/4/200821 / 23
Random Walks and Electrical NetworksRandom Walks in Random EnvironmentsExample:Suppose the distribution on environments is: 31P ω0 .39 and P ω0 .6143Then311191P(X1 1) .39 .61 ,432402and Eρ0 .391 3/43/4 .611 1/31/3 27 1.20However,EP (log ρ0 ) 0.00563901 0and so the RWRE is transient to .Jonathon Peterson2/4/200821 / 23
Random Walks and Electrical NetworksRandom Walks in Random EnvironmentsExample:Suppose the distribution on environments is: 31P ω0 .39 and P ω0 .6143Then311191P(X1 1) .39 .61 ,432402and Eρ0 .391 3/43/4 .611 1/31/3 27 1.20However,EP (log ρ0 ) 0.00563901 0and so the RWRE is transient to .Jonathon Peterson2/4/200821 / 23
Random Walks and Electrical NetworksRandom Walks in Random EnvironmentsOther Strange Behavior of RWRETransience with zero speed:Can have limn Xn but limn Xnn 0.Non-Gaussian Limiting Distributions:For simple random walk, always have Z xXn nv12 e t /2 dtlim P x Φ(x) n σ n2π For RWRE, can have examples where Xn nvlim P x Fs (x),n n1/swhere Fs is a totally asymmetric stable distribution of index s (1, 2).Jonathon Peterson2/4/200822 / 23
Random Walks and Electrical NetworksRandom Walks in Random EnvironmentsOther Strange Behavior of RWRETransience with zero speed:Can have limn Xn but limn Xnn 0.Non-Gaussian Limiting Distributions:For simple random walk, always have Z xXn nv12 e t /2 dtlim P x Φ(x) n σ n2π For RWRE, can have examples where Xn nvlim P x Fs (x),n n1/swhere Fs is a totally asymmetric stable distribution of index s (1, 2).Jonathon Peterson2/4/200822 / 23
Random Walks and Electrical NetworksReferencesReferences1. Peter G. Doyle and J. Laurie Snell, Random walks and electric networks.Carus Mathematical Monographs, 22. Mathematical Association of America,Washington DC, 1984Free download available at http://arxiv.org/abs/math/00010572. O. Zeitouni, Random walks in random environment in Lecture Notes inMathematics 1837, Springer, Berlin (2004).Jonathon Peterson2/4/200823 / 23
Random Walks and Electrical Networks . Jonathon Peterson School of Mathematics University of Minnesota February 4, 2008 Jonathon Peterson 2/4/2008 1 / 23. Random Walks and Electrical Networks Much of this talk is based on the book Random Walks and Electric Networks by Peter G. Doyle and J. Laurie Snell.
