Random Walks Flashcards
What is a random walk and what can it be interpreted as
A random walk is a sum of RVs sum i =1 to n Xi
Can be interpreted as a particle moving around
What is the definition of a simple random walk
Definition of a simple random walk is:
W = Wn, starts at a in Z,
W0 = a
Wn = a + X1 +…+Xn = Wn-1 + Xn
What is (Xn)n in N in simple random walks definition
(Xn)n in N is a sequence of i.i.d RVs s,t P(Xn=1) = p and P(Xn = -1) = 1-p
What does law of Wn depend on and how is it denoted
Law of Wn depends on parameters p (bias) and a, initial position
Denoted by P, Pa, (P^p)a
What is probability that W returns to 0/hits 0
Probability that W returns to 0/hits 0 is:
Define H [Wn = 0 for some n >=1) , xi = Pi(H)
If I = 0, x0 is prob that W started at 0 and returns, if not prob eventually hit 0
How do we compute xi
We compute xi by :
xi = Pi(H) = Pi(H, X1 = 1) + Pi(H, X1 = -1) (law of total prob)
= p* Pi(H|X1 = 1) + (1-p)*Pi(H|X1 = -1)
Eventually obtain x2 = x1^2 , and xi = x1^i
If Wn is a SRW with p >= 0.5, what is Pi(H)
Pi(H) (eventually hi 0) = ((1-p)/p)^i for all I >= 1 and 1 if I <=1
How do we compute x0 and escape probability
Compute x0 and escape probability by:
x0 = px1 + (1-p)x-1 = p* (1-p)/p + (1-p)*1 = 2(1-p)
P(H^C) = 1 - x0 = 2p-1
What is gambler’s ruin
Ambler’s ruin is when gambler is playing game where they bet £1 and if they win they get £1 and lose £1 if they don’t, probability p to win
What is Pk(Tn < T0) for p =/ 0.5 and 0 <= k <= N
Pk(Tn < T0) for =/ 0.5 and 0 <= k <= N is
(1 - ((1-p)/p)^k)/ (1 - ((1-p)/p)^N
What is Pk(Tn < T0) if p = 0.5
If Pk(Tn < T0) = k/N if p = 0.5 e.g take N = 2k then Pk(T2k < T0) = 0.5
