6
$\begingroup$

Consider a $k$-dimensional grid with integer points and let's begin our random walk at the origin $(0,0,\dots,0)$. Every step you have to move on each cartesian axis in the following way:

$x_1$ axis: one step forward with probability $\frac{1}{3}$ , one step backward with probability $\frac{1}{3}$ , remain where you were with probability $\frac{1}{3}$.

$ \vdots $

$x_k$ axis : one step forward with probability $\frac{1}{3}$ , one step backward with probability $\frac{1}{3}$ , remain where you were with probability $\frac{1}{3}$.

So we can define the random discrete vector $U_i=(X_{i1},\dots,X_{ik})$ that register the random actions taken on each axis at the $i$-th step of our random walk. The marginal density function of the random variable $X_{ij}$ is:

$$ f_{X_{ij}}(t) = \begin{cases} \frac{1}{3} \mbox{ if $t\in\{-1,0,1\}$} \\ 0 \mbox{ otherwise}\end{cases} $$

We would like to compute the following probability: $$ P\Biggl(\bigcup_{j=1}^{k}\Bigl\{\Bigl|\sum_{i=1}^{N}X_{ij}\Bigr|>\sqrt{N}\Bigr\}\Biggr) $$ as the number of steps $N$ approaches infinity. So we would like to know the probability after $N$ steps (where $N$ is a sufficiently large number) to be outside the $k$-dimensional cube with size $2\sqrt{N}$.

$k=1$ case We begin with the 1-dimensional case (a line). We want to compute: $$ P\Bigl(\Bigl|\sum_{i=1}^{N}X_i\Bigr|>\sqrt{N}\Bigr) = P\Bigl(\sum_{i=1}^{N}X_i>\sqrt{N}\Bigr) + P\Bigl(\sum_{i=1}^{N}X_i<-\sqrt{N}\Bigr) = 2\cdot P\Bigl(\sum_{i=1}^{N}X_i>\sqrt{N}\Bigr) $$ Since the random variables $\{X_i\}_{i=1}^{N}$ are indipendents and equally distributed, and $\mathbb{E}(X_i) = 0$,$Var(X_i) = \frac{2}{3}$, then we can apply the central limit theorem, so that: $$ P\Bigl(\sum_{i=1}^{N}X_i>\sqrt{N}\Bigr) = P\Bigl(\frac{\sum_{i=1}^{N}X_i}{\sqrt{N}\sqrt{\frac{2}{3}}}>\frac{\sqrt{N}}{\sqrt{N}\sqrt{\frac{2}{3}}}\Bigr) = 1- P\Bigl(\frac{\sum_{i=1}^{N}X_i}{\sqrt{N}\sqrt{\frac{2}{3}}}\leq\sqrt{\frac{3}{2}}\Bigr) \longrightarrow 1-\phi\Bigl(\sqrt{\frac{3}{2}}\Bigr) \approx 0.1112 $$ where $\phi(t) = \frac{1}{\sqrt{2\pi}}\int_{\infty}^{t}e^{-\frac{s^2}{2}}ds$ is the cumulative distribution function of a standard normal variable ($Z\sim\mathcal{N}(0,1)$).

So the probability requested is $2\cdot 0.1112 = 0.2224$.

$k$-dimensional case

Call $P\Bigl(\Bigl|\sum_{i=1}^{N}X_{ij}\Bigr|>\sqrt{N}\Bigr) = p = 0.2224$ which is the same for all axes ($p$ is indipendent from the index $j$).

$$ P\Biggl(\bigcup_{j=1}^{k}\Bigl\{\Bigl|\sum_{i=1}^{N}X_{ij}\Bigr|>\sqrt{N}\Bigr\}\Biggr) = \sum_{j=1}^{k}p - \sum_{j<m}^{k}p^2 + \dots + (-1)^{k+1}p^k = \sum_{h=1}^{k}(-1)^{h+1}\binom{k}{h}p^h = 1-(1-p)^{k} $$

Where we have applied the fact that the random variables $\Bigl|\sum_{i=1}^{N}X_{i1}\Bigr|,\dots,\Bigl|\sum_{i=1}^{N}X_{ik}\Bigr|$ are indipendent, so for example in the second term:

$$ P\Bigl(\Bigl\{\Bigl|\sum_{i=1}^{N}X_{ij}\Bigr|>\sqrt{N}\Bigr\}\cap\Bigl\{\Bigl|\sum_{i=1}^{N}X_{im}\Bigr|>\sqrt{N}\Bigr\}\Bigr) = P\Bigl(\Bigl\{\Bigl|\sum_{i=1}^{N}X_{ij}\Bigr|>\sqrt{N}\Bigr\}\Bigr)P\Bigl(\Bigl\{\Bigl|\sum_{i=1}^{N}X_{im}\Bigr|>\sqrt{N}\Bigr\}\Bigr) = p^{2}. $$ Limit case: $k\to\infty$ We can now easily compute the following probability: $$ P\Biggl(\bigcup_{j=1}^{\infty}\Bigl\{\Bigl|\sum_{i=1}^{N}X_{ij}\Bigr|>\sqrt{N}\Bigr\}\Biggr) = \lim_{k\to\infty} 1-(1-p)^{k} = 1 $$ since $p=0.2224\in(0,1) \implies (1-p)\in(0,1)$.

So the probability of escaping from a $k$-dimensional grid of size $2\sqrt{N}$ as $N\to\infty$ and $k\to\infty$ approaches the value 1!

My question: Do you think that this process is correct? I first applied the CLT and then used the indipendence of these random variables (since each step our "point" has to make a move across all the axes, and the movement made on the axis $x_i$ does not influence the movement made on the axis $x_j$).

Table of values:

$k=1 \implies P = 0.2224$;

$k=2 \implies P = 0.3978$;

$k=3 \implies P = 0.5327$;

$\vdots$

$\endgroup$

1 Answer 1

4
$\begingroup$

Your solution and the result are correct.

You can prove with a shorter solution.

$$\begin{align} P\Biggl(\bigcup_{j=1}^{k}\Bigl\{\Bigl|\sum_{i=1}^{N}X_{ij}\Bigr|>\sqrt{N}\Bigr\}\Biggr)& = 1-P\Biggl(\bigcap_{j=1}^{k}\overline{\Bigl\{\Bigl|\sum_{i=1}^{N}X_{ij}\Bigr|>\sqrt{N}\Bigr\}}\Biggr)\\ & = 1-P\Biggl(\bigcap_{j=1}^{k}\Bigl\{\Bigl|\sum_{i=1}^{N}X_{ij}\Bigr|\color{red}{\le}\sqrt{N}\Bigr\}\Biggr)\\ & = 1-\prod_{j}^k \left(P\Biggl(\Bigl|\sum_{i=1}^{N}X_{ij}\Bigr|\le\sqrt{N}\Bigr\}\right) \\ & = 1-(1-p)^n \end{align}$$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .