# Tag Info

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