(a) A biased one-dimensional walk takes a step with probability and a step with…

PHYSICS · Subjective · Fermi University Physics · Mathematical Methods for Physics · Probability, statistics and stochastic methods · Probability, statistics and stochastic methods

Error, Chance and the Machine, Ch Random walks and Markov chains

Problem

(a) A biased one-dimensional walk takes a step +1+1 with probability p=0.6p=0.6 and a step −1-1 with probability q=0.4q=0.4, independently at every step. Its single-step characteristic function is λ(θ)=⟨eiθX⟩=p eiθ+q e−iθ\lambda(\theta) = \langle e^{i\theta X}\rangle = p\,e^{i\theta} + q\,e^{-i\theta}. Using Pn(x)=12π∫−ππe−ixθλ(θ)n dθP_n(x) = \frac{1}{2\pi}\int_{-\pi}^{\pi} e^{-ix\theta}\lambda(\theta)^n\,\mathrm{d}\theta find P4(0)P_4(0), the probability of being back at the origin after 44 steps. (b) A two-state chain has transition matrix P=(0.950.050.100.90).\mathsf{P} = \begin{pmatrix} 0.95 & 0.05 \\ 0.10 & 0.90\end{pmatrix}. Find its stationary distribution π\boldsymbol\pi. Use the trace of P\mathsf{P} to find its second eigenvalue λ2\lambda_2, and give the spectral gap and the relaxation time trelt_{\rm rel} in steps. (c) For the same two-state chain let An=1A_n=1 when the chain is in state 1 at step nn and An=0A_n=0 otherwise. Show that ⟨An+1−π1∣Xn⟩=λ2(An−π1)\langle A_{n+1}-\pi_1\mid X_n\rangle=\lambda_2(A_n-\pi_1), and deduce that in equilibrium ρ(k)=λ2k\rho(k)=\lambda_2^k. Hence find the integrated autocorrelation time τint\tau_{\rm int}, and the factor by which the error bar of the fraction of a long run spent in state 1 exceeds the naive one.

Browse the problem library