Tag Info

Hot answers tagged

4

By the definition of the conditional expectation, $$\mathbb{P}(X_{n+m} = i \mid X_n = j, X_0 = j_n) = \frac{\mathbb{P}(X_{n+m}=i, X_n = j, X_0 = j_n)}{\mathbb{P}(X_n = j, X_0 = j_n)}. \tag{1} $$ Now, by the Markov property (MP) $$\begin{align*}& \mathbb{P}(X_{n+m}=i, X_n = j, X_0 = j_n) \\ &= \sum \mathbb{P}(X_{n+m} = i, X_{n+m-1} = ...


3

In general, the sum of two independent Markov chains is not a Markov chain. Let $X$ be a random variable such that $\mathbb{P}(X=0) = \mathbb{P}(X=1) = \frac{1}{2}$ and set $X_n := X$ for all $n \in \mathbb{N}$. Then, obviously $(X_n)_{n \in \mathbb{N}}$ is a Markov chain. Moreover, let $(Y_n)_{n \in \mathbb{N}_0}$, $Y_0 := 0$, be a Markov chain independent ...


3

The algebra is straightforward. We know $\pi P=\pi$ must be satisfied. The first equation gives us $\pi_1q=\pi_0p$. Take the equation: $\pi_2 q+\pi_0p=\pi_1$. A simplification gives us $\pi_2=(p/q)^2\pi_0$. Continuing this way, in general, you get: $\pi_k=(p/q)^k \pi_0$. Summing up the $\pi$s to 1, you will find $\pi_0=1-p/q$. The other probabilities can be ...


3

Proof: We first must note that $\pi_j$ is the unique solution to $\pi_j=\sum \limits_{i=0} \pi_i P_{ij}$ and $\sum \limits_{i=0}\pi_i=1$. Let's use $\pi_i=1$. From the double stochastic nature of the matrix, we have $$\pi_j=\sum_{i=0}^M \pi_iP_{ij}=\sum_{i=0}^M P_{ij}=1$$ Hence, $\pi_i=1$ is a valid solution to the first set of equations, and to make it a ...


2

It can be shown that for $\theta>0$, $P\{S_n\ge\theta n \text{ for some } n>0\}<1$... Let $Z_n=S_n/n$ where $S_n$ is a simple symmetric random walk. $Z_n$ is an $(\mathcal{F}_n^X)$ backward martin-gale ($\mathbb{E}[X_1|\mathcal{F}_n^X]=Z_n$). Fix $\hat Z_n=Z_{N-n}$ and $\hat {\mathcal{F}}_n=\mathcal{F}_{N-n}^X$ ($0\le n<N$) so that $\hat Z_n$ is ...


2

I think the answer will depend on the matrix $\mathcal{P}$. If all the transition probabilities $p_{ij}$ for the gates are $1/2$, then all the $G_{mk}$ are independent, hence all the $V_k$ are independent, hence $Q_k$ is a random walk and hence Markov. So let's consider an explicit example. Say $\mathcal{P} = \begin{pmatrix} 3/4 & 1/4 \\ 1/4 & 3/4 ...


2

A non-autonomous process is not Markov, basically because the distribution of $X_{n+1}$ cannot be specified solely by specifying the distribution of $X_n$. Try to prove this. On the other hand, a process which is "only not Markov because it is not autonomous" (i.e. where the distribution of $X_{n+1}$ can be specified from $n$ and $X_n$ but not from $X_n$ ...


2

The OFRBG comment is the thing (we know the long term average departure rate must be less than or equal to the long term average arrival rate). But here is some more intuition: Consider an $M/M/1$ queue with $0 < \lambda < \mu$. Define $\rho = \lambda /\mu$. The steady state distribution is $p_k = (1-\rho)\rho^k$ for $k \in \{0, 1, 2, \ldots\}$, ...


2

The departure rate must equal the arrival rate at equilibrium. Although, the service rate is larger than the arrival rate, the server is not busy all of the time and cannot serve customers who aren't there. (Do you know how to find the proportion of time the server is idle in terms of $\lambda$ and $\mu$?) Notice that Burke's theorem makes a statement about ...


2

Yes, it is just the chain rule for entropy. The chain rule for entropy is Theorem 2.2.1 in Cover and Thomas. $$H(X,Y) = H(X) + H(Y|X)$$ You can use the chain rule when you condition on another random variable $Z$. In this case, you get $$H(X,Y|Z) = H(X|Z) + H(Y|X,Z)$$ The proof is word for word the same as the proof of the original chain rule. In this case, ...


2

Another simple example: Consider a random walk on the real line with $p=1$ of a jump to the right. Then we have an infinite number of open classes, no closed classes, and all states are transient. Naturally, then, we stay within the set of transient states.


2

$$\mathbb{E}_x N_x=\mathbb{E}_x\sum_{n \geq 1} 1\{X_n=x\}=\sum_{n \geq 1} \mathbb{E}_x[1\{X_n=x\}]=\sum_{n \geq 1} P_x\{X_n=x\}=\sum_{n \geq 1} p^{(n)}(x,x)$$


2

The result is false in this generality. Fix some $z\in S$ and define $O\mu=\mu_c+\mu_d(S)\delta_z$, where $\mu_d$ and $\mu_c=\mu-\mu_d$ are the discrete and continuous parts of $\mu$, respectively. Then $O$ satisfies your conditions, but cannot possibly be given by a kernel, if there is a non-discrete probability measure $\nu$ on $S$. Why not? If ...


2

Since $P$ is symmetric, we know from the spectral theorem that $P$ has real eigenvalues and is diagonalizable. Since $P$ is a doubly stochastic matrix, the stationary distribution is uniform, i.e. $$\pi=\left(\frac16,\frac16,\frac16,\frac16,\frac16,\frac16\right).$$ Since $P$ has a stationary distribution, we know that $1$ is an eigenvalue. In particular, ...


2

If you have a state space $\mathcal{X}$ of cardinality $N$, then a first-order Markov chain requires $N$ probability mass functions with with $N$ mass points each. Equivalently, this first-order Markov chain can be described by a $N\times N$ transition probability matrix. Hence, there are $N(N-1)$ parameters (the probability mass function sums to one). If ...


1

First of all $Y-Z-W-Y$ would imply that $Y$ is independent of itself given $Z$ or $W$, i.e., both $Z$ and $W$ are sufficient statistics for $Y$: $I(Y;Y|Z)=H(Y|Z)=0$. But I do not think that this claim holds: The statements $X-Y-Z$ and $Y-W-Z$ neither imply $Y-Z-W$ (leading to your claim) nor $X-Y-W$ (leading to $X-Y-W-Z$).


1

Some related summary comments on ergodic Markov chains. (There are several fleas hopping around triangles elsewhere on this site, each according to the same transition matrix, but with varying questions about the associated process; search 'Markov flea vertex'.) With help from @Did, essentially by manipulating difference equations, I believe you have ...


1

The closed communicating class might be the whole set. For the second part, you will need an infinite state-space.


1

I think it helps to think about it in terms of both sides together. If you have a row-stochastic matrix $P$ corresponding to the Markov process $X_n$, a probability distribution $q$ written as a row vector, and a real-valued function $f$ on the state space written as a column vector, then $$q P^k f = E[f(X_k)]$$ where $X_0$ is distributed according to $q$. ...


1

That is mistaken. Let's look at the probability distribution of $X_2$ given $X_0=6$. \begin{align} & \Pr(X_2 = 6\mid X_0=6) \\[10pt] = {} & \Pr\Big( \underbrace{(X_1 = 1\ \&\ X_2 = 6)\text{ or }(X_1=2\ \&\ X_2=6)\text{ or }\cdots}_{\text{five disjuncts}}\mid X_0=6\Big) \\[10pt] = {} & \underbrace{\Pr\Big(X_1 = 1\ \&\ X_2 = 6 \mid ...


1

Consider a state space $\mathcal S=\{0\}\cup \{\delta\}\cup A\cup B$, where $A=\{a_1,a_2,\ldots\}$ and $B=\{b_1,b_2,\ldots\}$, and transition probabilities $$ P_{ij} = \begin{cases} \frac13,& i=0, j\in\{\delta, a_1,b_1\}\\ 1,& i = j = \delta\\ \frac13,& i=j=a_1\\ \frac23,& i=a_n, j=a_{n+1}\\ \frac13,& i=a_{n+1}, j=a_n\\ \frac23,& ...


1

Having broken things down according to the value of $H_x$, you can use the simple Markov property on each term in the sum on the far right — the event $\{H_x=m\}$ is $\mathcal{F}_m$-measurable because $H_x$ is a stopping time . Alternatively, you could write $f(X_n)$ as $g(X_n)\circ\theta_{H_x}$ on $\{H_x<\infty\}$ and use the strong Markov property at ...


1

The method is correct. The eigenvector corresponding to $\lambda_1=1$ should be $$v_1 = \begin{pmatrix} 1/2 \\ 1 \end{pmatrix}$$ The signs were wrong in the matrix $\lambda_1I_2-A$. The signs were also wrong for the other eigenvector. You must have made the same mistake.


1

For "short" sequences, in general you need the initial distribution to say anything. For "long" sequences, the "generic" situation is that there is a unique invariant distribution, to which the long-term distribution of the process converges. (When I say "generic" I mean that I am omitting some assumptions which hold for "most" transition matrices.) This ...


1

The probability of state i after n jumps can only be defined depending on what your initial probability vector is. Suppose you let u be your initial vector. It is simply a probability distribution of time 0, where you choose randomly. If you need to find the probablity distribution after n steps, you simply multiply u by your transition matrix raised to ...


1

A slightly differently worded proof. Consider any path of states $i_{0} = i, i_{1}, i_{2}, ... ,i_{n} = j$ such that $P_{i_{k}i_{k+1}} > 0$. If all the states in the path are distinct, then the path cannot have more than $M$ elements. On the other hand, if not all the states $i_{0}, ..., i_{n}$ are distinct then there exists a subpath consisting of ...


1

Here is an informal proof; it isn't that hard to see how to formalize it, but the notation for doing so is a bit tedious. Suppose you have a possible path $(i_0,i_1,\dots,i_n)$, where $i_0=i,i_n=j$, and $i_{k_1}=i_{k_2}=r$. Then it's possible to go directly from $r$ to $i_{k_2+1}$, and it's possible to get from $i_{k_2+1}$ to $j$. That means that ...


1

I don't see why not. Consider a simple random walk on $E=\mathbb{Z}^3$. Then all states are transient, i.e. $T=E$, and naturally the random walk never leaves $T$. Now, there is a theorem that says that in the above settings, and for any two states $x,y$, we have $$ \mathbb{P}_x[X_n=y] \leq \mathbb{P}_x[X_n=x]. $$ And since $x$ is a transient state, we ...


1

You want to compute the determinant $$ \begin{vmatrix} -x & 1 & & \\ & -x & \ddots & \\ & & \ddots & 1 \\ 1 & & & -x \end{vmatrix} $$ I suggest you expand along the first column (I gave it some thought ; no induction needed here). Feel free to ask for details if you need more. Hope that ...


1

From definition of Markovity in $p(x,y,z) = p(x)p(y|x)p(z|y)$, one can prove that $p(x,z|y) = p(x|y)p(z|y)$. This will give the following as another definition of Markovity: Past and future are conditionally independent given the present. With this, we can see that, if $X \rightarrow Y \rightarrow Z$, then $I(X; Z | Y)=0$. Therefore we have: $$I(X ; ...



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