Tag Info

New answers tagged

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