# Tag Info

8

First let's consider a closely related enumeration problem. Define the range of a cycle $\{x_0, x_1, x_2, \ldots, x_{k-1}, x_k=x_0\}$ to be $\max_i \left|x_{i+1}-x_i\right|$. How many cycles on $\mathbb{Z}$ are there with $k$ edges and range $\le r$? (Two cycles are equivalent if they differ by a translation or a rotation.) If $N_k^{(r)}$ is the ...

5

Note: OPs approach is correct from my point of view. This is an alternate approach based upon the generating function of the transitition matrix of OPs automaton. Let's assume the situation with nodes $\{0,\ldots,n\}$, $n\geq 1$ and walks according to OPs rules from $0$ to $n$. We consider the $(n+1)\times(n+1)$ transition matrix $M(n+1)$ describing the ...

5

Yes your recurrence is right, i.e., $$N_i = 1 + (1-p)N_{i-1} + pN_{i+1}$$ with $N_0 = 1+N_1$ and $N_n = 0$. This can be rearranged to give $$p(N_{i+1}-N_i) - (1-p)(N_i-N_{i-1}) = -1$$ with $N_1 - N_0 = -1$ and $N_n = 0$. Setting $v_i = N_{i+1} - N_{i}$, we obtain the equations to be $$pv_i - (1-p)v_{i-1} = -1$$ with $v_0 = -1$ and $N_n=0$. Setting $v_i = u_i ... 4 Let$\mathbb{P}(X_{n+1}=X_{n}+1)=p$and$\mathbb{P}(X_{n+1}=X_{n}-1)=1-p=q$. Since$X_{2n}=0$, we must have taken$n$upward and$n$downward steps, as$\#\{$steps up$\}+\#\{$steps down$\}=2n$and$\#\{$steps up$\}-\#\{$steps down$\}=0$. So the probability is$C_{n}p^nq^n$where$C_n$is the number of ways it can be done. We will prove that$\displaystyle ...

3

Suppose $X_1, X_2, \dots X_n$ is a sequence of independent and identically distributed random variables with mean $0$ and standard deviation $\sigma$. Then the sum $S_n = X_1 + \dots + X_n$ has mean $0$ and standard deviation $\sqrt{n} \sigma$. There are a large class of results in probability, the simplest being Chebyshev's inequality and the most famous ...

3

Here is another approach, which involves a lot of elementary computations. The key is similarity. In the case of steps up to size two, this works in the following way: Let $P(i_1,i_2,\dots,i_k)$ denote the probability to stop at zero after you went through $i_1,i_2,\dots,i_k$. Then the probability you search is $$P=\frac 14(P(-2)+P(-1)+P(1)+P(2)).$$ By ...

2

Let's look at $\mathbb{E}[X_{n+1}^2-(n+1)|F_n]$ (take $s=n$). We need show it equals to $X_n^2-n$. Since $X_{n+1}=X_n+ Y_{n+1}$ It should be $$\mathbb{E}[X_{n}^2|F_n]+2\mathbb{E}[X_{n}Y_{n+1}|F_n]+\mathbb{E}[Y_{n+1}^2|F_n]-\mathbb{E}[n+1|F_n]$$, Since $X_{n}$ is measurable w.r.t. $F_n$, and $Y_{n+1}$ is independent of $F_n$ (for which we can "take out ...

2

For $s\le n$, $$\mathbb{E}(M_{n+1}\mid \mathcal{F}_s)=\mathbb{E}((X_n+Y_{n+1})^2-(n+1)\mid \mathcal{F}_s)\\=X_n^2+2X_n\mathbb{E}(Y_{n+1})+\mathbb{E}(Y_{n+1}^2)-(n+1)\\=X_n^2-n=M_n$$ the steps have used the fact that $Y_n$ is an i.i.d. $\mathcal{N}(0,1)$ sequence. The possible mistake that you are making in your approach is the one rightly pointed out by @saz ...

2

First, the graph must be undirected (if it's directed and there exists an edge from $a$ to $b$ but not from $b$ to $a$, then if $X_1 = a$ and $X_2 = b$, it is impossible to have $X_{n-1} = b$ and $X_n = a$. Let $d(x)$ be the out degree of node $x$: $$P(X_i = x_1, \ldots, X_n = x_n | X_0 = x_0) = \prod_{i \in [0, n)} d(x_i)^{-1}$$ $$P(X_i = x_{n-1}, ... 2 I'm not sure how that remark about an O(N^{1/2}) sequence being random came about, because you can easily come up with a deterministic (non-random) sequence such that the sum of the first N terms is exactly N^{1/2}. However square root does have some notable importance in randomness. If you have a random sample of n i.i.d. samples from a ... 2 if you the average of N independent random variables you get something that has standard deviation of size roughly N^{-1/2}. This is the central limit theorem. So the sum has error O(N^{1/2}). The law of iterated logarithms might also be relevant in terms of the rate of convergence of a sequence to the average. 2 This is a non-rigorous answer. If t \mapsto R_t is a differentiable function from \mathbb R to SO(n), then its derivative satisfies$$ \frac{dR_t}{dt} = R_t A_t ,$$where A_t is an anti-symmetric matrix. I could rewrite this non-rigorously as$$ dR_t = R_t A_t \, dt = R_t (\exp(A_t \, dt) - I) ,$$where \exp(A) denotes the matrix exponential of a ... 2 You already have the solution to the problem in the difference equation$$N_i=1+(1-p)\cdot N_{i-1}+p\cdot N_{i+1}$$with boundary conditions$$N_n=0 \text{ and } N_0=1+N_1,$$and all that remains is the technical issue of finding the solutions. You may want to look up solutions to difference equations to learn more about it, but here's a quick go at this ... 1 This random walk, like many others, can be modeled by using a Markov chain. See Chapter 11 of the on-line probability book by Grinstead and Snell (it can be freely downloaded). You need to know a bit of linear algebra to understand Markov chain theory. 1 Denote a_n:=\mathbb E[M_n] and b_n:=\mathbb E[S_n^+ ]/n. The LHS is$$\sum_{n=0}^\infty r^na_n-\sum_{n=1}^\infty r^na_{n-1}=a_0+\sum_{n=1}^\infty r^n(a_n-a_{n-1}).$$By identification of the coefficients of power series, we derive that for each n\geqslant 1,$$a_n-a_{n-1}=b_n,\quad a_0=0, $$from which the wanted formula follows. 1 Obviously, it only works for large n. Heuristically, the explanation is that although X_n and Y_n are not actually independent, after a large number of steps n, the information about the individual horizontal components of X_n is essentially lost, so that little can be deduced about the distribution of Y_n, except that n and X_n together ... 1 Regular Markov chain means that all the entries of the transition matrix P are positive. Let Markov chain have n states. If \pi _i is the equilibrium probability for state i, you can say:$$ \pi _i = \sum _{j=1}^n\pi _j P_{ji}  Assume by contradition that $\pi _i=0$. Since all the entries of $P$ are positive, from equation above you can conclude ...

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