b) Consider a symmetric random walk on the integers {0, +1, 12, ...}. This Markov chain is a sequence {X } where {Xn+1 = Xn + 1} = p, P{Xn+1 = Xn -1} = q, where p + q = 1. Suppose the chain starts at the origin Xo = 0. i) Derive the probability P(X2n = 0}. ii) Using the Stirling formula n! ~ Vann (2)" , determine whether the origin is a recurrent or transient state. Hint: Being recurrent requires _n P(X2n = 0} = co, while being transient requires En P(Xzn = 0}