# Tag Info

0

The condition that $E(S_{i+1}\mid S_i=n)\lt0$ for every $n\ne0$ is not sufficient to guarantee positive recurrence. Counterexamples are discrete Bessel processes of suitable indexes.

5

For example, consider $$\left[ \begin {array}{ccc} 0&{\frac {49}{72}}&{\frac {23}{72}} \\ 1/2&1/6&1/3\\ 1&0&0\end {array} \right]$$ which is not diagonalizable (the eigenvalue $-5/12$ has algebraic multiplicity $2$ but geometric multiplicity $1$).

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 ...

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 ... 0 Well one interpretation of a stochastic matrix is as a state transition matrix. So consider the state after the n^\text{th} transition, S=M^n, and notice that$$\det(S) = \det(M^n) = \det(M)^n$$Except in marginal cases when \det(M) = 1 or when the transitions don't converge, we expect that \det(M^\infty) = \det(M)^\infty = 0. So the closer the ... 0 How are the Green's functions of a Markov chain related to the notion from PDE theory? These are the same: the Green function of a Markov chain is the Green function "from PDE theory" associated to its generator. Is there a reasonable notion of the (G)reen's "function" when you have a Feller process instead of a Markov chain? Indeed there is, with ... 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. ... 0 Can you just show that since:$$P(Y_{n+1}|Y_n) \neq P(Y_{n+1}|Y_n,Y_{n-1}) $$Then Y_n cannot be a markov chain as it violates the markov property 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 ... 0 Let X_n =(S_0+\ldots + S_n). Then, \{X_n\}_{n\geq 0} is not a Markov chain because the distribution of X_{n+1} given X_n is not known. However, X_{n+1}|X_n, X_{n-1} \overset{D}{=} X_{n} + X_{n} - X_{n-1} + Y_{n+1}. Thus, the chain \{Z_n\}_{n\geq 1}, where Z_n = (X_n, X_{n-1}), is a Markov chain. 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 ... 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. 0 You can make it into a Markov process if you include time information in the "state". 0 Here is an example (not very nice though): P=\begin{pmatrix}1/6&1/2&1/3\\1/2&0&1/2\\0&1/3&2/3\end{pmatrix} Eigenvector for eigenvalue 1: p=(1, 5/3, 7/2) Normalization: p_\text{normalized}=(36/577, 60/577, 126/577) So the entropy (after simplifying a little bit by putting together terms) is: ... 0 Let T_1 = \max\{i, X_i = 1\}$$P(T_1 = k) = p_{11}^{k}(1-p_{11})E(T_1) = \sum_{k=1}^{+\infty}kP(T_1 = k)$$You've forgotten the term 1-p_{11}. Of course the result can be simplified if you want 0 I am not sure if this answer is useful in your case. Theorem: Exists a basis formed by generalized eigenvectors of T:V\rightarrow V, even if V is an infinite dimensional vector space over a field F, if we assume the existence of a polynomial p(x)\in F[x] with all roots in F such that p(T)=0. Of course, we need to prove first for nilpotent ... 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 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 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 ...

0

This is based on the following equivalence: Consider three random variables or families of random variables $U$, $V$, and $W$, then $P(U\mid V,W)=P(U\mid V)$ if and only if $(U,W)$ is independent conditionally on $V$. To see why in the discrete case (the general case being similar), note that the first condition reads $$P(U=u\mid V=v,W=w)=P(U=u\mid ... 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$$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 Two classes of models: Markov chains of higher order, and Varying Length Markov Chains (VLMCs, also known as Variable-Order Markov Models). 0 Let n_0, n_1, n_2\in\mathbb N and i_0, i_1, i_2 \in S be given. We'll expand the expression in the following way.$$P(X_{n_{2}}=i_{2}\,|\, X_{n_1}=i_1, X_{n_0}=i_0)=  \frac{P(X_{n_{2}}=i_{2}, X_{n_1}=i_1, X_{n_0}=i_0)}{P(X_{n_1} = i_1, X_{x_0} = i_0)} =  \frac{\sum_{(k_q)}\sum_{(j_q)} P(X_{n_{2}}=i_{2}, ...

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 ... 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 ...

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 ...

Top 50 recent answers are included