Tag Info

New answers tagged

1

Then after the mosquito goes to $0$, the mosquito must immediately go back to $1$ next move, i.e. the whole situation restarts. Consider the case that when the mosquito goes from $1$ to $4$ without passing $0$ as a success, and the case when the mosquito goes from $1$ to $0$ without passing $4$ as a failure. You already calculated the two probabilities as ...


0

Let's model your Markov chain as follows. Let $(U_n)_{n\geq 0}$ be i.i.d. random variables uniformly distributed on the unit disk in $\mathbb{R}^2$. Set $Z_0$ take values in $\bar D$, and for $n\geq 0$ let $$Z_{n+1}=Z_n+{1\over 2} \varphi(Z_n)\, U_n,$$ where $\varphi(z)=\inf\{\|x-z\|: x\in D^c\}$. Since \begin{eqnarray*}\mathbb{E}(Z_{n+1}\mid {\cal F}_n) ...


1

Denote by $$\tau_j := \inf\{n \geq 1; X_n = j\}$$ the hitting time and define, iteratively, $$\tau_j^k := \inf\{n > \tau_j^{k-1}; X_n = j\}$$ for $k \geq 2$. Hints: It suffices to show that $P_i(X_n = j$ i.o.$)=0$ for all $j \geq 1$. Show that $$P_j(\tau_0<\infty) \leq P_j\left( \left\{ X_n = j \, \, \text{i.o.} \right\}^c \right).$$ Conclude ...


1

Solution 1: Denote by $P$ the transition matrix and by $P^n = (P^n(i,j))_{i,j=1,2,3}$ the $n$-th power of $P$. Let $(X_n)_{n \in \mathbb{N}}$ be a Markov chain with transition matrix $P$. It is known that $$P^n(i,j) = \mathbb{P}^i (X_n=j), \tag{1}$$ i.e. $P^n(i,j)$ is the probability that the Markov chain starts at $x=i$ and moves to $x=j$ in $n$ steps. ...


1

Your Markov chain is reducible, since there is no way to enter or leave state 2: State 2 does not communicate with either states 1 or 3. In general, you might find a solution using the Perron-Frobenius theorem relating the eigenvalues of a matrix to its reducibility. For example, the matrix you gave us has the eigenvalue 1 with multiplicity 2. For a matrix ...


0

Your expression is correct. The $i$-th entry of $\vec t_{\text{exp}}$ is the sum over all states $j$ of the expected number of times state $j$ is visited, starting in state $i$ and ending with absorption, multiplied by the time one Markov chain step takes in state $j$.


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


0

Calculating the powers of $M$ (see here: How to compute the powers of $2\times2$ Markov matrices) shows that the matrix whose $(i,j)^{\rm th}$ entry is $\pi(i)(M^k(i,j)-\pi(j))$ can be written $$A:=\underbrace{\pi(1)\pi(2)(1-M(1,2)-M(2,1))^k}_{\rm scalar}\pmatrix{1&-1\\-1&1}.$$ The expression you want is \begin{eqnarray*} \mu^T A \mu ...


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

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


1

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


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


0

I did some further research and found out the following: The statement $p(x_{t-1}|u_t) = p(x_{t-1})$ has nothing to do with the Markov assumption. It rather states that control is randomly chosen and not a function of the state. The assumption of random controls is essential for the Bayes filter: Without this assumption, the Bayes filter algorithm does ...


0

Transition probability matrix (P) in this case will be $$ P=\begin{bmatrix}0 & 0.5 & 0.5\\ 0.5 & 0 & 0.5\\ 0.5 & 0.5 & 0\end{bmatrix}. $$ Though $p_{ii}=0$ for $i=0,1,2$, it can be observed that $p_{ii}^n\ne0$ for $n\ge 2$ (also intuitive). Rest is a straight forward calculation depending on $n$.


0

I perused the book you mention and found no definition of what is the Markov assumption (the author does have a word on the markov assumption but its more a critique on the hypothesis then a definition I believe the definition is somewhere else in the lines of conditional independence). Usually markov assumption is translated as $P(x_{t+1} \mid x_0,\ldots, ...


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


0

Hi and thanks for your answers, I ended up solving it by taking steps when studying the behavior of the Markov chain with these 2 absorbing states. Toying a bit with a smaller problem (read not generic) I came up with a standard system of equations, then when writing the concrete results I noticed that the ratio between state $a_i$ to $a_{i+1}$ is always ...


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


0

In general, we have (given to unedited version of the question, i didn't fully understand): $$P_r(s_0)=(1-p)P(s_1)=a$$ $$P_r(s_1)=(1-p)P(s_2)$$ $$P_r(s_2)=pP(s_1)+P(s_3)(1-p)$$ $$P_r(s_3)=pP(s_2)$$ $$P_r(s_4)=pP(s_3)=b$$ $$\sum_{i=0}^{4} P(s_i) = 1\ \ \ \ (1)$$ For more tractability, I refine above $5$ equations as the below matrix representation : ...


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.


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


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.


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


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)$$


0

No, aperiodicity is not needed, only irreducibility (which is the statement that for all $x,y$ there exists an $n$ such that $P^n(x,y)>0$). In fact, even for a periodic or cyclic chain you get the result, that the Cesaro average of $P^n$ converges to a matrix in which every row equals $\pi$. Your result then follows from this. The proof is based on the ...


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


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

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

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


0

Let $\alpha(n)$ represent the probability of reaching 1 before 5 starting at state $n$. We are looking for $\alpha(3)$. From the transition probabilities, we have the following: \begin{align*} \alpha(1) &= 1, \\ \alpha(2) &= p\alpha(1) + q\alpha(3),\\ \alpha(3) &= p\alpha(2) + q \alpha(4),\\ \alpha(4) &= p\alpha(3) + q\alpha(5),\\ \alpha(5) ...


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


0

A Markov transition matrix contains the one-step transition probabilities from each state to every other state. With seven states your matrix is $7\times 7$, and if I have understood your process correctly, looks like: $$\matrix{ &\color{red} 1&\color{red}2&\color{red}3&\color{red}4&\color{red}5&\color{red}6&\color{red}{7+}\cr ...


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


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

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


0

This is a sub problem of an open problem called the Nonnegative Inverse Eigenvalue Problem, see Reference.


0

Suppose you have a particle which you know its position and velocity at $t=0$ and the force affecting it at $t > 0$. So you can evolve the position and velocity of the particle to any point in future (usually by a differential equation). This is the analogous to a Forward Equation, but on deterministic setting (Kolmogorov himself used this example in his ...


0

Nope, you cannot combine them like that, because there would actually be a loop in the dependency graph (the two Y's are the same node), and the resulting graph does not supply the necessary Markov relations X->Y->Z and Y->W->Z. The proper conclusion to draw from the two Markov relations can only be: X->Y->W->Z because p(x,y,z) = \sum_w p(x,y,w,z) = p(x) ...


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


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

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


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


0

In general, from $X\rightarrow Y \rightarrow Z$ and $Z\rightarrow W \rightarrow U$ we cannot conclude $X\rightarrow Y\rightarrow Z\rightarrow W\rightarrow U$. To have this last Markovity, we need to have $Y\rightarrow Z \rightarrow W$, too. That is, $p(w,y|z)=p(w|z)p(y|z)$ is also required too. Regarding $ Y \rightarrow Z \rightarrow W \rightarrow Y$, when ...


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


0

I tried to follow @Bernhard's recommendations, and this is the progress I made so far. Uniformization in itself didn't help me much. The CTMC converges, so clearly the corresponding uniformized (discrete) chain converges as well. Consider the uniformized (linearized) chain. Instead of making a single "small" change at each discrete step (direct consequence ...


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

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



Top 50 recent answers are included