Hot answers tagged

3

There are four equally probable possibilities for the first two steps of this random walk: positive, positive: $D=+2$ positive, negative: $D=0$ negative, positive: $D=0$ negative, negative: $D=-2$ so the square root of the mean of the squares of these is $\sqrt{\dfrac{4+0+0+4}{4}}=\sqrt{2}$ as expected. But this is before you know what actually happens. ...


2

I think the problem is that the number of attempts that can be used in a numerical simulation $n$ is finite. Notice this: if $Y_n=\frac{S_n}{\sqrt{2n\log\log n}}$, by properties of random walk we know $\mathbb{E}[Y_n]=\frac{\mathbb{E}[S_n]}{\sqrt{2n\log\log n}}=0$ and $$ Var[Y_n]=\frac{Var[S_n]}{2n\log\log n}=\frac{n}{2n\log\log n}=\frac{1}{2\log\log n}\to ...


2

Let $W_n=n^{-1/2}Y_n$. Then $$n^{-1/2}E[Y_n\mid Y_n>0]=E[W_n\mid W_n>0]\le \frac{\sqrt{E|W_n|^2}}{P\{W_n>0\}}=\frac{\sigma}{P\{W_n>0\}},$$ and $P\{W_n>0\}\to 1/2$ (by the CLT), i.e. for any $\epsilon>0$, $P\{W_n>0\}\ge \frac{1}{2}-\epsilon$ for $n$ large enough.


2

Since $X_t$ takes only the values $1$ and $-1$, we have $$|S_t| \leq 1$$ for all $t$. In particular, we find $$\{S_t \geq 1\} = \{S_t = 1\} = \bigcap_{j=1}^t \{X_j = 1\}$$ for all $t \in \mathbb{N}$, i.e. $S_t \geq 1$ can only happen if all $X_j$ equal $1$ for $j=1,\ldots,t$. This implies $$\mathbb{P}(\tau<\infty) \leq \mathbb{P}(X_1 = 1).$$ On the ...


2

The conjecture is true if no non-empty proper subset of $\{a_1,\ldots,a_n\}$ sums to $0$. Hereafter I will make that assumption. Let $\langle b_0,\ldots,b_{n-1}\rangle$ be any permutation of the numbers $a_1,\ldots,a_n$. Extend it to an infinite periodic sequence $\langle b_k:k\in\Bbb N\rangle$ with period $n$ by setting $b_{\ell n+k}=b_k$ for ...


1

It is not quite true that any random walk on $\mathbb{Z}_n$ is irreducible. This will depend on the increment distribution $\mu$ as well. For example, on $\mathbb{Z}_4$ if you take $\mu(g)=\delta_{g+2}$ then there are two communicating classes $\{0,2\}$ and $\{1,3\}.$ There are lots of different stationary distributions for this random walk.


1

Your equations are not correct. They should be as follows: $$ \begin{align} p(x,y)&\triangleq \mathbb{P}(X_1=y|X_0=x)\\ &= \mathbb{P}(X_0+\Xi_1=y|X_0=x)\\ &=\mathbb{P}(\Xi_1=y-x|X_0=x)\\ &\overset{(a)}{=}\mathbb{P}(\Xi_1=y-x)\\ &=f_\Xi(y-x), \end{align} $$ where $(a)$ follows since $\Xi_1$ is independent of $X_0$.


1

I'll recast the problem in terms of the random walk $W_n=W_0+\sum_{i=1}^n (X_i-M).$ For $j\geq 0$, define the (identically distributed) stopping times $$\tau_j=\inf\left(n> j: \sum_{i=j+1}^n (X_i-M)>0\right)=\inf(n> j: W_n>W_{j}). $$ If $\mathbb{P}(\tau_0<\infty)=1,$ then $\mathbb{P}(\tau_j<\infty)=1$ for all $j\geq 0$, and hence ...


1

Formally : $$(\frac{\partial}{\partial z}R)(z,s)=\sum_{n=0}^{\infty}\sum_{i=-\infty}^{\infty}r(i,n)iz^{i-1}s^n $$ $$(\frac{\partial^k}{\partial s^k}(\frac{\partial}{\partial z}R))(z,s)=\sum_{n=k}^{\infty}\sum_{i=-\infty}^{\infty}r(i,n)iz^{i-1}\frac{n!}{(n-k)!}s^{n-k} $$ So that : $$(\frac{\partial^k}{\partial s^k}(\frac{\partial}{\partial ...


1

Abusing technology (Mathematica) I got $$P=\left (\begin{array}{cccc} a&b&c&d\\ a&b&-c&-d\\ a&-b&c&-d\\ a&-b&-c&d \end{array} \right )$$ Such that $P^{-1}\cdot M\cdot P$ was diagonal. Not sure how much fun that would be to try by hand.


1

Given the present symmetries I'd call this a random walk on a tetrahedron. Your matrix has the eigenvalues $$1, \quad 2p-1, \quad 2q-1, \quad 2r-1\tag{1}$$ with corresponding eigenvectors $$(1,1,1,1),\quad(1,1,-1,-1),\quad(1,-1,-1,1),\quad(1,-1,1,-1)\ .\tag{2}$$ Don't ask me how I found this out. It seems that @IanMiller in his answer hints at $(2)$, and ...


1

If you can directly apply the result of Binomial distribution, you may try the following: Let $M_n = \sum_{i=1}^n X_n$ where $X_i$ represent each individual step with support $\Pr\{X_i = 1\} = p, \Pr\{X_i = -1\} = 1 - p$. Note $$ X_i \stackrel {d} {=} 2B_i - 1, i = 1, 2, \ldots, n$$ where $B_i \sim \text{Bernoulli}(p)$. Therefore summing them up $$ M_n ...


1

It is implied (and it should have been said) that all other probabilities are zero, i.e., the probability is supported by the origin, the basis vectors and their opposites; $p(y)=0$ unless $y$ is one of the $x_k$ or its opposite or the origin. The interpretation is that a random walk has probability zero of taking two jumps (including diagonal jumps) at a ...


1

As far as I can see, $p$ is just a distribution of a i.i.d random variable $X_i$ taking values on $\mathbb{Z}^d$. With respect to chosen generating set, any member of $\mathbb{Z}^d$ is represented as a coordinate vector $(k_1,\cdots,k_l)$ (using notation used in the original article. Now $p$ is saying that $P(X_i=(0,0,\cdots,0,\pm 1,0,\cdots,0)) = ...


1

Let $r=\frac{p_1}{p_{-1}}$, $M_n=\max_{k\le n} S_k$, $m_n=\min_{k\le n}S_k$. Then by reflection principle $$P(M_n\ge t)=P(S_n\ge t)+r^{t}P(S_n\le -(t+1))$$ $$P(-m_n\ge t)=P(S_n\le -t)+r^{-t}P(S_n\ge t+1)$$ and hence you get compute $E(M_n)$ and $E(-m_n)$. Case $r=1$ is especially easy $(E(M_n-m_n)=\Theta(\sqrt n))$. Similarly, for Brownian motion with drift ...



Only top voted, non community-wiki answers of a minimum length are eligible