Thursday, November 19, 2015

On a class of random walks

$\newcommand{\bZ}{\mathbb{Z}}$ $\newcommand{\bR}{\mathbb{R}}$  $\newcommand{\bE}{\mathbb{E}}$ $\newcommand{\eC}{\mathscr{C}}$ $\newcommand{\bP}{\mathbb{P}}$  $\newcommand{\eF}{\mathscr{F}}$ $\newcommand{\whS}{\widehat{S}}$ $\DeclareMathOperator{\var}{\boldsymbol{var}}$ $\newcommand{\bC}{\mathbb{C}}$

I heard   of these random walks from my number-theorist colleague Andrei Jorza who  gave me a probabilistic translation of some    observations in number theory. What follows is rather a variation  on  that theme.

There is a whole family of such walks, parametrized by a complex number  $\newcommand{\ii}{\boldsymbol{i}}$ $\rho=\cos \theta +\ii \sin\theta$, $\theta\in [0,\pi]$, $\ii=\sqrt{-1}$.

This is  discrete time walk  on  the configuration space  $\newcommand{\lan}{\langle}$ $\newcommand{\ran}{\rangle}$

$$  \eC_\rho:= L[\rho] \times  C(\rho,-\rho), $$

where $C(\rho,-\rho)$ is the subgroup of $S^1$ generated by $\pm\rho$, i.e.,

$$ C(\rho,-\rho)=\bigl\{\; \pm \rho^k;\;\;k\in\bZ \;\bigr\},$$

and $L[\rho]\subset  \bC$ is the additive subgroup of $\bC$ generated by the elements $\rho^n$, $n\in\bZ_{\geq 0}$.

The state of the walk at time $n$ is given  by a pair of random variables $(X_n,  V_n)$, where one should think of $X_n\in L[\rho]$  as describing the "position'' and $V_n\in G(\rho,-\rho)$ as describing the ``velocity''   at time $n$.

Here is how the random walk takes place.  Suppose that at time $n$ we are in the configuration $(X_n, V_n)$. To decide where to go next, toss a fair coin.   If a  the Head shows up  then

$$V_{n+1}=\rho V_n,\;\; X_{n+1}= X_n+V_{n+1}. $$


$$ V_{n+1}=-\rho V_n,\;\; X_{n+1}= X_n+V_{n+1}. $$

More abstractly, we are given a probability space $(\Omega,\eF,\bP)$ and a sequence of  independent, identically distributed variables

$$ S_n:\Omega\to\{-1,1\},\;\;\bP[S_n=\pm 1]=\frac{1}{2},\;\;n\in\bZ_{\geq 0}. $$

If we set
\whS_n:=\prod_{k=1}^nS_k, $$
then we have
V_n= \whS_n \rho^n,\;\;X_n=\sum_{k=1}^n V_n=\sum_{k=1}^n \whS_k\rho_k.
Observing that

$$\bE[\whS_k]=0,\;\;\var[\whS_k]=\prod_{j=1}^k\var[S_j]=1,  $$ we deduce

$$\bE[X_n]=0,\;\;\var[S_n]=\bE[X_n\bar{X}_n] $$

$$=\sum_{j,k=1}^n \bE[ \whS_j\whS_k]\rho^{k-j}=\sum_{j=1}^n \bE[ \whS_j^2]+2\sum_{1\leq j<k\leq}^n \bE[ \whS_j\whS_k]\rho^{k-j}=n. $$

Example 1.   Suppose that $\theta=\frac{\pi}{2}$ so that $\rho=\ii$. In this case $L[\rho]$ is the lattice $\bZ^2\subset \bC$ and $G(\ii,-\ii)$ is the group  of forth  order roots of $1$.  At time $n=0$,  the moving particle is at the origin facing  East,. turns right or left  (in this case North/South) with equal probability. Once   reaches a new intersection, it turns  right/left  with equal probability.  The following MAPLE generated animation  a loop describes a 90-step   portion of one such walk.

This is somewhat typical   of  what one observes in general.

Example 2.   Suppose that  $\theta  =\frac{\pi}{3}$. In this case $G(\rho,-\rho)$ is the group of    6th order roots of  $1$ and $L[\rho]$ is a lattice in $\bC$.   The following  MAPLE generated   animation depicts a  90 step portion of such a walk and the patterns you observe are typical.

Example 3.    Assume   that the angle $\theta$ is small and $\frac{\theta}{\pi}$ is not rational,  say $\cos \theta=0.95$. The animation below  depicts a 90-step stretch of such a walk.

Example 4.   For comparison, I have included an animation of a 90-step segment of the usual uniform random walk on $\bZ^2$.

Clearly, I am interested to  figure out what is happening and I have a hard time asking a good question. A first  question  that comes to my mind would be to find   statistical invariants  that would distinguish the  random walk in Example 1 from the random walk in Example  4.    I will refer to them as $RW_1$ and $RW_4$

 Clear each of these two  walks   surround  many unit squares with vertices in the lattice $\bZ^2$.  For $j=1,4$ will denote by $s_j(n)$ the expected number of unit squares      surrounded by a  walk of $RW_j$ of length $n$.. Which grows faster as $n\to\infty$, $s_1(n)$ or $s_4(n)$?

I will probably update this posting as I get more ideas, but maybe this shot in the dark will initiate a conversation and will suggest other, better questions.


Post a Comment