Skip to main content
added 2 characters in body; edited tags
Source Link
Did
  • 5.7k
  • 1
  • 30
  • 36

Consider the simple symmetric random walk on the integers starting from the origin of length $n$. More precisely, I will denote an $n$ step random walk $w$ as $$ w:= \omega_0 \omega_1 \ldots \omega_n, $$
where $\omega_0 =0$ and $\omega_i := \omega_{i-1}+1$ or $\omega_{i-1}-1$. Let me denote the set of all such $w$ as $\Omega_n$ and endow it with the uniform probability measure. Note that the cardinality of the set $\Omega_n$ is $2^n$. Define the following random variable $$ Rt_n: \Omega_n \longrightarrow \mathbb{Z} $$
as follows: $Rt_n(w)$ is the number of times the walk $w$ returns to the origin.

$\textbf{Question 1:}$ Does there exist some real number $p>0$ and $C \neq 0$ such that the random variable $$w \longrightarrow \frac{Rt_n(w)}{n^p} $$ converges in probability to the constant $C$? More precisely, for every $\epsilon >0$ $$ \lim_{n \longrightarrow \infty} Prob\Big( |\frac{Rt_n(w)}{n^p}-C| > \epsilon \Big) = 0.$$$$ \lim_{n \longrightarrow \infty} Prob\Big( \left|n^{-p}Rt_n-C\right| > \epsilon \Big) = 0.$$ If yes, what is this $p$? I think $p = \frac{1}{2}$, but I do not know if this is true (or for that matter if $p$ exists).

$\textbf{Question 2}:$ This is weaker than Question $1$; let $\sigma_n(k)$ be the number of $n$ step random walks starting from the origin, that return to the origin exactly $k$ times. If $n$ is fixed (but large), for what value of $k$ does $\sigma_n(k)$ attain its maximum? Is it approximately of the order of $C n^p$, where $p= \frac{1}{2}$ and $C$ is some non zero constant?

$\textbf{Question 3:}$ If the answer to the Question $1$ is yes, does the random variable $\frac{Rt_n}{n^p}$ converge almost surely to $C$? In this case, I am going to think of $Rt_n$ as a map from the space of walks of infinite length; to compute the value of $Rt_n$ we truncate the walk after $n$-steps. This way the random variables are defined on a common sample space and almost sure convergence makes sense.

Consider the simple symmetric random walk on the integers starting from the origin of length $n$. More precisely, I will denote an $n$ step random walk $w$ as $$ w:= \omega_0 \omega_1 \ldots \omega_n, $$
where $\omega_0 =0$ and $\omega_i := \omega_{i-1}+1$ or $\omega_{i-1}-1$. Let me denote the set of all such $w$ as $\Omega_n$ and endow it with the uniform probability measure. Note that the cardinality of the set $\Omega_n$ is $2^n$. Define the following random variable $$ Rt_n: \Omega_n \longrightarrow \mathbb{Z} $$
as follows: $Rt_n(w)$ is the number of times the walk $w$ returns to the origin.

$\textbf{Question 1:}$ Does there exist some real number $p>0$ and $C \neq 0$ such that the random variable $$w \longrightarrow \frac{Rt_n(w)}{n^p} $$ converges in probability to the constant $C$? More precisely, for every $\epsilon >0$ $$ \lim_{n \longrightarrow \infty} Prob\Big( |\frac{Rt_n(w)}{n^p}-C| > \epsilon \Big) = 0.$$ If yes, what is this $p$? I think $p = \frac{1}{2}$, but I do not know if this is true (or for that matter if $p$ exists).

$\textbf{Question 2}:$ This is weaker than Question $1$; let $\sigma_n(k)$ be the number of $n$ step random walks starting from the origin, that return to the origin exactly $k$ times. If $n$ is fixed (but large), for what value of $k$ does $\sigma_n(k)$ attain its maximum? Is it approximately of the order of $C n^p$, where $p= \frac{1}{2}$ and $C$ is some non zero constant?

$\textbf{Question 3:}$ If the answer to the Question $1$ is yes, does the random variable $\frac{Rt_n}{n^p}$ converge almost surely to $C$? In this case, I am going to think of $Rt_n$ as a map from the space of walks of infinite length; to compute the value of $Rt_n$ we truncate the walk after $n$-steps. This way the random variables are defined on a common sample space and almost sure convergence makes sense.

Consider the simple symmetric random walk on the integers starting from the origin of length $n$. More precisely, I will denote an $n$ step random walk $w$ as $$ w:= \omega_0 \omega_1 \ldots \omega_n, $$
where $\omega_0 =0$ and $\omega_i := \omega_{i-1}+1$ or $\omega_{i-1}-1$. Let me denote the set of all such $w$ as $\Omega_n$ and endow it with the uniform probability measure. Note that the cardinality of the set $\Omega_n$ is $2^n$. Define the following random variable $$ Rt_n: \Omega_n \longrightarrow \mathbb{Z} $$
as follows: $Rt_n(w)$ is the number of times the walk $w$ returns to the origin.

$\textbf{Question 1:}$ Does there exist some real number $p>0$ and $C \neq 0$ such that the random variable $$w \longrightarrow \frac{Rt_n(w)}{n^p} $$ converges in probability to the constant $C$? More precisely, for every $\epsilon >0$ $$ \lim_{n \longrightarrow \infty} Prob\Big( \left|n^{-p}Rt_n-C\right| > \epsilon \Big) = 0.$$ If yes, what is this $p$? I think $p = \frac{1}{2}$, but I do not know if this is true (or for that matter if $p$ exists).

$\textbf{Question 2}:$ This is weaker than Question $1$; let $\sigma_n(k)$ be the number of $n$ step random walks starting from the origin, that return to the origin exactly $k$ times. If $n$ is fixed (but large), for what value of $k$ does $\sigma_n(k)$ attain its maximum? Is it approximately of the order of $C n^p$, where $p= \frac{1}{2}$ and $C$ is some non zero constant?

$\textbf{Question 3:}$ If the answer to the Question $1$ is yes, does the random variable $\frac{Rt_n}{n^p}$ converge almost surely to $C$? In this case, I am going to think of $Rt_n$ as a map from the space of walks of infinite length; to compute the value of $Rt_n$ we truncate the walk after $n$-steps. This way the random variables are defined on a common sample space and almost sure convergence makes sense.

Source Link
Ritwik
  • 3.2k
  • 20
  • 27

How many times does a simple symmetric random walk of length n return to the origin?

Consider the simple symmetric random walk on the integers starting from the origin of length $n$. More precisely, I will denote an $n$ step random walk $w$ as $$ w:= \omega_0 \omega_1 \ldots \omega_n, $$
where $\omega_0 =0$ and $\omega_i := \omega_{i-1}+1$ or $\omega_{i-1}-1$. Let me denote the set of all such $w$ as $\Omega_n$ and endow it with the uniform probability measure. Note that the cardinality of the set $\Omega_n$ is $2^n$. Define the following random variable $$ Rt_n: \Omega_n \longrightarrow \mathbb{Z} $$
as follows: $Rt_n(w)$ is the number of times the walk $w$ returns to the origin.

$\textbf{Question 1:}$ Does there exist some real number $p>0$ and $C \neq 0$ such that the random variable $$w \longrightarrow \frac{Rt_n(w)}{n^p} $$ converges in probability to the constant $C$? More precisely, for every $\epsilon >0$ $$ \lim_{n \longrightarrow \infty} Prob\Big( |\frac{Rt_n(w)}{n^p}-C| > \epsilon \Big) = 0.$$ If yes, what is this $p$? I think $p = \frac{1}{2}$, but I do not know if this is true (or for that matter if $p$ exists).

$\textbf{Question 2}:$ This is weaker than Question $1$; let $\sigma_n(k)$ be the number of $n$ step random walks starting from the origin, that return to the origin exactly $k$ times. If $n$ is fixed (but large), for what value of $k$ does $\sigma_n(k)$ attain its maximum? Is it approximately of the order of $C n^p$, where $p= \frac{1}{2}$ and $C$ is some non zero constant?

$\textbf{Question 3:}$ If the answer to the Question $1$ is yes, does the random variable $\frac{Rt_n}{n^p}$ converge almost surely to $C$? In this case, I am going to think of $Rt_n$ as a map from the space of walks of infinite length; to compute the value of $Rt_n$ we truncate the walk after $n$-steps. This way the random variables are defined on a common sample space and almost sure convergence makes sense.