Tag Info

Hot answers tagged

3

First part: For every $n$, the simple Markov property at time $nK$ yields $$P_j(T_i\gt(n+1)K\mid T_i\gt nK,X_{nK}=k)=u(k),\qquad u(k)=P_k(T_i\gt K),$$ and $u(\ )\leqslant1-\varepsilon$ uniformly by hypothesis hence $$P_j(T_i\gt(n+1)K,X_{nK}=k)\leqslant(1-\varepsilon)P_j(T_i\gt nK,X_{nK}=k).$$ Summing these over $k$ yields ...


3

Since the Markov chain is irreducible, it is possible to get from state $i$ to state $j$, so $p_{ij}^{(k)} > 0$ for some $k$. Then $p_{ij}^{(n+k)} \ge p_{ii}^{(n)} p_{ij}^{(k)}$, so $$\sum_{n\ge 0} p_{ij}^{(n)} \ge \sum_{n\ge k} p_{ij}^{(n)} = \sum_{n\ge 0} p_{ij}^{(n+k)}\ge p_{ij}^{(k)} \sum_{n \ge 0} p_{ii}^{(n)} = \infty$$


3

There can be no oscillations, because then there would be a state that you visit infinitely many times. Each time you visit that state, there is a positive probability for the process to go extinct. For example, just the probability of having no children in the next generation. Denote this probability $p > 0$. Since you visit this state infinitely many ...


2

This sounds like a job for the Goulden-Jackson cluster method. Doron Zeilberger and John Noonan have a gem of a paper (and Maple programs) about it. In short, this method takes a collection of "bad" words over a finite alphabet and efficiently produces a two-variable generating function for words of various lengths containing specified numbers of bad words. ...


2

Why is this equal to $\Pr(X_2=j\mid X_0=i)$? Because $$\Pr(X_1=j\mid X_0=k)=\Pr(X_2=j\mid X_1=k)=\Pr(X_2=j\mid X_1=k,X_0=i),$$ first by stationarity, then by the Markov property at time $1$, hence $$\Pr(X_1=j\mid X_0=k)\Pr(X_1=k\mid X_0=i)=\Pr(X_2=j,X_1=k\mid X_0=i),$$ in particular, $$\sum_k\Pr(X_1=j\mid X_0=k)\Pr(X_1=k\mid X_0=i)=\Pr(X_2=j\mid ...


2

At time $0$, $\xi^{Z_0}=\xi$. When $n\to\infty$, $Z_n\to+\infty$ on non-extinction hence $\xi^{Z_n}\to0$ on non-extinction and $Z_n\to0$ on extinction hence $\xi^{Z_n}\to1$ on extinction. Finally $|\xi^{Z_n}|\leqslant1$ uniformly, thus everything is in place for an application of martingale dominated convergence theorem.


2

More generally. Let $(X_n)_{n\geqslant0}$ be defined by $X_{n+1}=G(X_n,Z_{n+1})$ for every $n\geqslant0$, where $(Z_n)_{n\geqslant1}$ is i.i.d. and independent of $X_0$. Then $(X_n)_{n\geqslant0}$ is a Markov chain. If need be, one can write down the transition probability of $(X_n)_{n\geqslant0}$ as $$P(X_{n+1}\in A\mid (X_k)_{0\leqslant k\leqslant ...


1

Let $P$ denote the transition matrix of some discrete Markov chain $(X_n)$ indexed by the nonnegative integers. Assume that $P=\mathrm e^Q$ where $Q$ is the generator of a Markov process $(\xi_t)$ indexed by the nonnegative real numbers, then it is natural to realize $(X_n)$ using $(\xi_t)$, by the identity $$X_n=\xi_n,$$ valid for every integer $n$. In ...


1

I don't know how much you know about Markov Chains but you can simplify your problem by using the concept of irreductibility. We can notice that $$\forall (i,j) \in \mathbb{N}^2, \exists n\geq 0, \quad P(X_n=j|X_0=i)>0 $$ (i.e. we can go from any $i$ to any $j$). The chain is therefore irreductible. A property of irreductible chains (or subchains) is ...


1

Maybe she is estimating as: $$ || \sum_i a_i \phi_i T^{\frac{1}{2}} || \leq || T^{\frac{1}{2}} || \cdot || \sum_{i \neq 0} a_i \phi_i || \\ \leq || T^{\frac{1}{2}} || \cdot || \sum_{i} a_i \phi_i || \leq || T^{\frac{1}{2}} || \cdot || f T^{-\frac{1}{2}} || \\ \leq || T^{\frac{1}{2}} || \cdot || T^{-\frac{1}{2} } || \cdot || f|| \leq \frac{\max_x ...


1

A direct proof is to note that, if $(X_k)$ denotes the Markov process on $\{0,1,\ldots,N\}$, then the random process $(Y_k)$ defined by $$Y_k=u(X_k),\qquad u(x)=\max\{x,N-x\},$$ is a Markov chain on $\{N/2,N/2+1,\ldots,N\}$ with transition rates $2g_{N/2}=2r_{N/2}$ for $N/2\to N/2+1$, $g_n=r_{N-n}$ for $n\to n+1$ and $r_n=g_{N-n}$ for $n\to n-1$ for every ...


1

Here's a rough estimate which may give an idea of how to get a proper answer. Let $X_i(t)$ be the number of colors such that there are $i$ balls of that color. Let the level at time $t$, denoted by $L(t)$, be the largest $i$ such that $X_i(t)>0$. Suppose $L(t)=i$. We want the probability that $L(t+1)=i+1$. At time $t$, there are $i X_i(t)$ balls of ...


1

For the counterexample, consider $$P(X_5 = 4 | X_4 = 3, X_3 = 2, X_2 = 1, X_1 = 0, X_0 = 0)$$ and $$P(X_5 = 4 | X_4 = 3, X_3 = 1, X_2 = 0, X_1 = 0, X_0 = 0).$$ How do these two probabilities differ based on different $X_3, X_2, X_1$? (Unravel the definitions and figure out what each $Y_i$ has to be.) Hopefully by doing this, you'll have some more intuition ...


1

Two classes of models: Markov chains of higher order, and Varying Length Markov Chains (VLMCs, also known as Variable-Order Markov Models).


1

Direct computations show that, for every $n\geqslant1$, $E(N_{t+1}-N_t\mid N_t=n)=\sum\limits_{k=0}^\infty ka_k-R\sum\limits_{k=0}^\infty a_k$ (assuming the series $\sum\limits_kka_k$ converges absolutely, say). This drift does not depend on $n\geqslant1$. The formula for $E(N_{t+1}-N_t\mid N_t=0)$ is different since the transitions from state $0$ are ...


1

This is not an easy thing to prove and in general the spectral gap of a matrix does not exceed the convex combination of its component gaps. It's a hard problem and an active area of research. However, if one of your Markov chains happens to be rank 1, you can apply Corollary 1 of http://arxiv.org/pdf/math/0307056v1.pdf. The earlier results in this paper can ...


1

As explained in the comments, differentiating exponentials of matrices such as $\bar P(s,t)$ is slightly more complicated than in the scalar case since, quite generally, $$\left.\frac{\mathrm d}{\mathrm dt}\mathrm e^{A+tB}\right|_{t=0}=\sum_{i\geqslant0}\sum_{k\geqslant0}\frac{A^iBA^k}{(i+k+1)!},$$ which is neither $B\mathrm e^A$ not $\mathrm e^AB$ in ...



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