Stochastic process consisting both coding and proof, and some computation for constructing a transition matrix
Oscar Albert
Oct6_ClassNotes.pdf
Recall : =
Enpected total number of steps before entering a state of interest can be computed as - the row nuns of matric :
M -- CI -QJ "
where Q is appropriately chosen .
Went : Suppose we have more than I recurrent= class I say k of them ) : { R , . . . . , Rz }.
Question : What is the probability that the MC
eventually ends up in a particular int class ÷ say in Rs ?
- Assume , all recurrent classes have only singletons
{ rj } . = Rj ; it j z k .
- Assume ; there are '
s '
transient states :
ht. . . . . , its } .
Define Nti , nj ).
= P' { chain starting .
in state
ti eventually ends up in recurrent state nj }
.
( after some n steps ).
i. e . dlti , rj ) - - P4Xn= ng .
"
eventually:/ Xo - ti } -
Clearly 21mi , rj ) =. P4Xn=rj i ' l Xo # ri } = O for it y
'
d l ri , rj ) =L for i- j
d ( ti , rj )=P4xn=ry . eventually IX. = ti }.
= Tf, Phxn -
rj eventually IX , - k, Xo - ti }
PLXEKI Xo - ti }
a r¥phXn=rj eventually IX.i. k } Phx , -- klxo - ti 's.--
Find : d Iti , nj ) -- If .si?lkihj)pltis&. The State space I = It , . . . . ., its } U - { or , } N { ra ! -. -
T .
'a'in:÷:3 : :c: i. I .
d.Lti , rj) = ⑧
=
pig .
dlksrj ) pl ti , k ). go
+. E .
& ( k , rj ) pl ti , k ).
R -E { r, i . ., Sir ? -
= pl ti, Nj ) .
i. Nti , ej) - I .¥£ , Piti . til. t putting?✓
Col . of Roon Q pertaining A pertaining to tj to tj
Example : Random walk my Abs . Boundaries. T
.
:÷÷÷÷÷÷:÷ :pO O 42 O 42 ° 42 O Yz O - -
S . Q .
M= LI - Q) "
iii: : "
::S us . ;Y.
" " E )'14 314 -
= A .
ph Absorption in scanner slate 0 when we start air transient state 33 - ¥ .
= d. ( 3,0 ).
= P 4 Xn -- o. eventually 1×0=33}. = him Pn
.
( 3,0 ) .
now
Recall from pages 18-19 : (Example 2 ). ⑥ . - - .
I .
3/4 42
'
son .÷¥q:)
×
leni pm ( 3,0 ). = I neo 44.
Example : RW on tetrahedron my an absorbing .
=
Vertex .
• 4. 4. 1 . U O O
ii. it :÷:÷÷÷ :p. •
'b Yz 43 O ' Z m -
S. Q .
M = ( I - Q ) "
I 2 3 .
"
÷: "
¥: :¥d 4 .
i. Ms --
'
31.7, ] Example : 2 absorbing vertices . =
Say 4 , 3 are absorbing .
Write P in canonical form , . compute Ms .
3 4 .
Ms. = '
z [ 'k
'
EyYz Yz .
Enample : RW on a finite graph . ---
Hee example 5- of page 12 in tent ) .
Recoil : A finite , simple . , undirected graph . is
a - finite collection of vertices ( nodes ? V.f::::.÷÷.IE- I 4Finite edges . Undirected p-
a
N vs . avoids - self loops .
•I o.n-m.nhtipkeodg.es . .→ i -
Def : A graph is connected if there is a path I
.
if length I . or more edges . of - the (4) distinct parvis of nodes .
- bine venter v is a "
state " wi the state space .
Can we find the prop - of twine that a random walled on the graph spends mi rester v ?
Or .
can we find This .
Claims : The invariant prob . Talk DCI. Ze .
Ploof : suppose there are N vertices (nodes).
Since I P ' = F '
where Tt -- [Auditing . . . -stuff -
we know :
¥2 ,
Alvis . plviilj) = A- lug . ). So
÷A-
EI pcvi , vj ). = µ .
> O . if "ing .
= o - otherwise -
i. A- Lvj ) = [ .
it wi ) plllisvj ).⑦ " """i Is.Irs -- fans .
= [ .
Thi ) . * I - devil.vii. Vi"si
y U
.
= ft . edges that contain Vi = dali ? -
Total # edges in graph . e -
because Alvi) -- Prop . of time a random
walker spends in Vester xi
" '
Alvy . ) = -2 .
A Wi ) * I
Yi : Vinny . devi )
.
= I -2 .
dl * I ki : Vinay
.
e - dcvi ) .
= -2 I 2 e .
Hi : Vin Vy ' Tg
= dlvj ). because we are summing over - -
each Vi that has an edgeze - with Vg
-
*H@ * ¥÷
Is. find Ettii ? = tati , & " I
