{"id":9025,"date":"2016-10-08T20:33:22","date_gmt":"2016-10-08T18:33:22","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=9025"},"modified":"2025-01-10T21:58:02","modified_gmt":"2025-01-10T20:58:02","slug":"back-to-basics-divergence-of-a-random-walk","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2016\/10\/08\/back-to-basics-divergence-of-a-random-walk\/","title":{"rendered":"Back to basics \u2013 Divergence of a random walk"},"content":{"rendered":"
\"George<\/a>
George P\u00f3lya (1887 - 1985) one of the first to study rigorously random walks.<\/figcaption><\/figure>\n

Recently a colleague of mine came with a simple question related to his second year probability classes: how to prove that an asymmetric random walk diverges to infinity almost surely, without using the Borel-Cantelli lemma, the law of large numbers, or Markov chains tools such as stopping times and recurrence\/transience?<\/p>\n

A natural answer to is prove all what is needed from scratch, which turns out to be pretty short and intuitive for the random walk. More precisely, let \\( {{(S_n)}_{n\\geq0}} \\) be an asymmetric random walk on \\( {\\mathbb{Z}} \\) started from the origin, namely \\( {S_0=0} \\) and for any \\( {n\\geq1} \\)<\/p>\n

\\[ S_{n}=S_{n-1}+X_{n}=X_1+\\cdots+X_n, \\]<\/p>\n

where \\( {{(X_n)}_{n\\geq1}} \\) is a sequence of independent and identically distributed random variables following an asymmetric Rademacher distribution:<\/p>\n

\\[ p:=\\mathbb{P}(X_n=+1)=1-\\mathbb{P}(X_n=-1)\\neq\\frac{1}{2}. \\]<\/p>\n

Our objective is to prove that<\/p>\n

\\[ \\mathbb{P}(\\lim_{n\\rightarrow\\infty}S_n=-\\infty)=1 \\quad\\text{if}\\quad p<\\frac{1}{2} \\]<\/p>\n

and<\/p>\n

\\[ \\mathbb{P}(\\lim_{n\\rightarrow\\infty}S_n=+\\infty)=1 \\quad\\text{if}\\quad p>\\frac{1}{2}. \\]<\/p>\n

The idea is to show that \\( {{(S_n)}_{n\\geq1}} \\) is captured after a random time by a cone centered around \\( {\\mathbb{E}(S_n)=nm} \\) where \\( {m:=\\mathbb{E}(X_i)=2p-1\\neq0} \\), of width \\( {\\delta_n\\ll n} \\). To see it, for any \\( {\\delta_n>0} \\) to be chosen later, we introduce the event<\/p>\n

\\[ A_n:=\\{|S_n-nm|\\geq\\delta_n\\}. \\]<\/p>\n

The Markov inequality gives (trying with \\( {2} \\) instead of \\( {4} \\) shows that \\( {2} \\) is not enough)<\/p>\n

\\[ \\mathbb{P}(A_n) =\\mathbb{P}((S_n-nm)^4\\geq\\delta_n^4) \\leq\\frac{\\mathbb{E}((S_n-nm)^4)}{\\delta_n^4}. \\]<\/p>\n

But, denoting \\( {X_i':=X_i-m} \\), we get \\( {\\mathbb{E}(X'_i)=0} \\) and \\( {S_n-nm=X_1'+\\cdots+X_n'} \\) and<\/p>\n

\\[ \\mathbb{E}((S_n-nm)^4) =\\mathbb{E}((X_1'+\\cdots+X_n')^4) =\\mathcal{O}(n^2)\\mathbb{E}(X_1'^2)+n\\mathbb{E}(X_1'^4) =\\mathcal{O}(n^2) \\]<\/p>\n

where we used the fact that the \\( {X'_i} \\)'s are centered, independent, and bounded in \\( {L^4} \\): \\( {\\sup_{n\\geq1}\\mathbb{E}(X_n'^4)<\\infty} \\). Therefore for any \\( {\\delta_n=n^\\alpha} \\) with \\( {\\alpha>0} \\) to be chosen later,<\/p>\n

\\[ \\mathbb{P}(A_n)=\\mathcal{O}\\left(\\frac{1}{n^{4\\alpha-2}}\\right) \\quad\\text{and thus}\\quad \\sum_{n=1}^\\infty\\mathbb{P}(A_n)<\\infty \\]<\/p>\n

as soon as \\( {\\alpha>3\/4} \\). Let us introduce now the random variable<\/p>\n

\\[ Y:=\\sum_{n=1}^\\infty\\mathbf{1}_{A_n}. \\]<\/p>\n

The Fubini-Tonelli theorem or the monotone convergence theorem gives<\/p>\n

\\[ \\mathbb{E}(Y) =\\mathbb{E}\\left(\\sum_{n=1}^\\infty\\mathbf{1}_{A_n}\\right) =\\sum_{n=1}^\\infty\\mathbb{E}(\\mathbf{1}_{A_n}) =\\sum_{n=1}^\\infty\\mathbb{P}(A_n) <\\infty. \\]<\/p>\n

Since \\( {Y} \\) takes its values in \\( {[0,\\infty]} \\), it follows that \\( {\\mathbb{P}(Y<\\infty)=1} \\), in other words, almost surely, the series \\( {\\sum_{n=1}^\\infty\\mathbf{1}_{A_n}} \\) converges, in other words, almost surely, for \\( {n} \\) large enough (above a random threshold), we have<\/p>\n

\\[ |S_n-nm|<\\delta_n=n^{\\alpha}, \\]<\/p>\n

and by taking \\( {3\/4<\\alpha<1} \\), it follows that \\( {{(S_n)}_{n\\geq1}} \\) diverges to \\( {+\\infty} \\) if \\( {p>1\/2} \\) since \\( {m>0} \\) and to \\( {-\\infty} \\) if \\( {p<1\/2} \\) since \\( {m<0} \\) (drawing a picture with a cone may help!).<\/p>\n

Note.<\/b> This proof works beyond the case of \\( {\\pm1} \\) increments and requires only independence and boundedness in \\( {L^4} \\). Actually the same argument gives a quick proof of the strong law of large numbers for independent random variables bounded in \\( {L^4} \\) with same mean \\( {m\\in\\mathbb{R}} \\):<\/p>\n

\\[ \\mathbb{P}\\left(\\lim_{n\\rightarrow\\infty}\\frac{S_n}{n}=m\\right)=1. \\]<\/p>\n

Namely since \\( {\\mathbb{E}((\\frac{S_n}{n}-m)^4)=\\mathcal{O}(\\frac{1}{n^2})} \\), we get \\( {\\mathbb{E}(\\sum_{n=1}^\\infty(\\frac{S_n}{n}-m)^4)<\\infty} \\), and therefore \\( {\\mathbb{P}(\\lim_{n\\rightarrow\\infty}(\\frac{S_n}{n}-m)^4=0)=1} \\), which means that \\( {\\mathbb{P}(\\lim_{n\\rightarrow\\infty}\\frac{S_n}{n}=m)=1} \\). This strong law of large numbers provides in turn the almost sure divergence of the asymmetric random walk.<\/p>\n

The argument provides also a quick proof of the first Borel-Cantelli lemma by using the Fubini-Tonelli theorem or the monotone convergence theorem. Namely, if \\( {{(A_n)}_{n\\geq1}} \\) is a sequence of events such that \\( {\\sum_{n=1}^\\infty\\mathbb{P}(A_n)<\\infty} \\), then \\( {\\mathbb{E}(\\sum_{n=1}^\\infty\\mathbf{1}_{A_n})<\\infty} \\) and thus \\( {\\mathbb{P}(\\sum_{n=1}^\\infty\\mathbf{1}_{A_n}<\\infty)=1} \\) which means that \\( {\\mathbb{P}(\\limsup_{n\\geq1}A_n)=0} \\).<\/p>\n

Note.<\/b> The classical Markov chain way to prove the result consists in using the fact that \\( {{(S_n)}_{n\\geq0}} \\) is a Markov chain with state space \\( {\\mathbb{Z}} \\) and transition matrix \\( {\\mathbf{P}_{x,y}=p\\mathbf{1}_{y=x+1}+(1-p)\\mathbf{1}_{y=x-1}} \\). This matrix is irreducible, and therefore it suffices to show that the state \\( {0} \\) is transient. The chain has period \\( {2} \\) and therefore \\( {\\mathbf{P}^{2n+1}(0,0)=0} \\) for any \\( {n\\geq0} \\). For \\( {\\mathbf{P}^{2n}_{0,0}} \\), the coin tossing game due to the \\( {\\pm1} \\) increments gives \\( {(S_n-S_0+n)\/2\\sim\\mathrm{Binom}(n,p)} \\), which yields<\/p>\n

\\[ \\mathbf{P}_{0,0}^{2n} =\\mathbb{P}(S_{2n}=0\\mid S_0=0) =\\binom{2n}{n}p^n(1-p)^n \\sim_{n\\rightarrow\\infty} \\frac{\\rho^n}{\\sqrt{\\pi n}} \\]<\/p>\n

where \\( {\\rho:=4p(1-p)} \\). Now \\( {p\\neq1\/2} \\) gives \\( {\\rho<1} \\), and thus<\/p>\n

\\[ \\mathbb{E}\\left(\\sum_{n=1}^\\infty\\mathbf{1}_{S_n=0}\\mid S_0=x\\right) =\\sum_{n=1}^\\infty\\mathbf{P}^{n}_{0,0} =\\sum_{n=1}^\\infty\\mathbf{P}^{2n}_{0,0}<\\infty, \\]<\/p>\n

which shows that the chain is transient.<\/p>\n","protected":false},"excerpt":{"rendered":"

Recently a colleague of mine came with a simple question related to his second year probability classes: how to prove that an asymmetric random walk…<\/p>\n

Continue readingBack to basics \u2013 Divergence of a random walk<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"iawp_total_views":848},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/9025"}],"collection":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/comments?post=9025"}],"version-history":[{"count":17,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/9025\/revisions"}],"predecessor-version":[{"id":21248,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/9025\/revisions\/21248"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=9025"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=9025"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=9025"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}