Hot answers tagged

4

Let $p$ be the probability you want. Look at the possible sequences of three tosses (including the initial $H$). We have $\{HH*,HTT,HTH\}$ Conditional on the first being $H$, the probability of $HH*$ is $\frac 12$, and the probability of the other two are each $\frac 14$. The first is a win for $H$, the second is a win for $T$, and the third restarts the ...


3

If the chain has an absorbing state, then the answer is no, because then $P(X_0=x_0,...X_n=x_n)>0$ but $P(X_n=x_n,...,X_0=x_0)=0$, where $x_n$ is the absorbing state. On the other hand, suppose your markov chain can be broken down into two disjoint communicating classes, i.e. two disconnected Markov chains. Then if the individual markov chains are ...


2

$$X_{n+1}-X_n = ((X_n+Z_{n+1})\vee 0)-X_n=Z_{n+1}\vee (-X_n) \Rightarrow$$ $$\mathbb{E}[X_{n+1}-X_n\mid X_n=i]=\mathbb{E}[Z_{n+1}\vee (-i)]=\mathbb{E}[Z_1\vee (-i)]\to \mathbb{E}Z_1<0$$ as $i\to \infty$ (assuming that $Z_1\in L^1$).


2

Suppose you have a uniform grid of points in the domain $\Omega$. Each of these points has a certain number $N(x)$ of neighbors (most of them have $2n$ of them). If you introduce a Markov chain with $P(x,y)=1/N(x)$ if $x$ and $y$ are neighbors and $0$ otherwise, then a harmonic function $h$ in the sense of your probability definition is a finite difference ...


2

The solution in image. I will find some time to type in latex later. The solution uses the result of a previous problem.


2

Here, state 4 is needed to sort out the difference between "the third heads just happened" and "the third head happened before now". The probability that it takes 8 flips to get 3 heads in a row is the probability the process is in state 3 just after the 8th flip (that is, the third heads happened on the 8th flip). Notice, if the state is 4 just after the ...


2

$\Bbb P[X_0=x_0,X_1=x_1]=\pi(x_0)P(x_0,x_1)$ and $\Bbb P[X_0=x_1,X_1=x_0]=\pi(x_1)P(x_1,x_0)$, so the $n=1$ case of reversibility already implies detailed balance.


2

You are right to be skeptical as there are some conditions missing. For example, $\mathbb{P}(T_{s_1}<T_{s_2}\mid X_1=s_1)=1$, but there is no guarantee that $b_{s_1}=1$. The equation $b_i=\sum_{j\in S}b_j\, p_{ij}$ will be true if the initial state $i$ is so "far away" from $s_1$ that $X_1=s_1$ is impossible.


2

For $kr\le t\le (k+1)r$, $P(\tau > t)\le P(\tau>kr)$, so$\sum_{t\ge0}P(\tau>t)=\sum_{k\ge0}\sum_{i=0}^{r-1}P(\tau>kr+i)\le\sum_{k\ge0}rP(\tau>kr).$


1

Say your generator matrix is: $$ G = \begin{bmatrix} -\lambda_0 & \lambda_{01} & \lambda_{02} & \cdots \\ \lambda_{10} & -\lambda_{1} & \lambda_{12} & \cdots \\ \lambda_{20} & \lambda_{21} & -\lambda_{2} & \cdots \\ \cdots \\ \end{bmatrix} $$ where, as usual, for each ...


1

It is not quite true that any random walk on $\mathbb{Z}_n$ is irreducible. This will depend on the increment distribution $\mu$ as well. For example, on $\mathbb{Z}_4$ if you take $\mu(g)=\delta_{g+2}$ then there are two communicating classes $\{0,2\}$ and $\{1,3\}.$ There are lots of different stationary distributions for this random walk.


1

Once you have got 3 consecutive heads, your goal is attained, and the task is over. 1.The probabilities in question obtained after N trials are the cumulative probabilities. 2. No, you can't say that. $P(N \le 8)$ is the probability that at most $8$ flips are needed. you can understand from the probability values for trials 3 through 8 $3\quad 0.125 000 ...


1

The sum of each column in transition matrix has to equal 1 (consider a perfectly located state in the beginning - after the matrix multiplication the probability vector will represent the corresponding matrix column). In your case it would be equal to zero. You can also think of it this way - you would converge to a state where the imaginary particle is ...


1

This is the very first application of the first step analysis, which introduce the usage of law of total expectation and the Markov property. Let $X_{t}$ and $X_{t+1}$ be the current state and next state respectively, $N_{t}$ be the number of throws to reach the absorption state $3$ at time $t$. Then for $i \neq 3$, $$ \begin{align*} \phi_i & = ...


1

In order to find the steady-state vector $s = \begin{pmatrix} s_1 \\ s_2 \end{pmatrix}$ you need to solve a simple matrix equation \begin{equation} (T - I)s = 0. \end{equation} But \begin{equation} T - I = \begin{pmatrix} -\frac{1}{2} & 1 \\ \frac{1}{2} & -1 \end{pmatrix} \end{equation} and, thus, you have a linear system \begin{equation} ...


1

First of all, notice that $Z_{n+1} = 2 \Leftrightarrow X_{n+1} = 2$ and $Z_n = 0 \Leftrightarrow X_n \in \{0,1\}$. So $$P(Z_{n+1} = 2 \mid Z_n = 0, Z_{n-1} = 2) = P(X_{n+1} = 2 \mid X_n \in \{0,1\}, X_{n-1} = 2).$$ Write this quantity as $$P(X_{n+1} = 2 \mid \{X_n = 0\} \cup \{X_n = 1\}, X_{n-1} = 2).$$ The strong Markov property says that you can drop the ...


1

maybe this helps. page 153 ff. https://www.math.ucdavis.edu/~gravner/MAT135B/materials/ch13.pdf You will also find the definitions for the transition rates there by summing over probabilities P[X_n=j|X_0=i] and the expected mean time of recurrence. So if some probabilities P[X_n=j|x0=i] of returning back to i in n steps are <1, by definition you ...


1

I'd consider $8$ states, namely for $1\leq k\leq 6$ the states $s_k:\ $"last roll was $k\>$, but game is not yet over", and the two end states $e_5$ and $e_7$. Denote by $x(n)$ the $(1\times8)$ row vector giving the probabilities that after $n$ rolls we are in the state $s_1$, $s_2$, $\ldots\ $, $s_6$, $e_5$, $e_7$ respectively. It follows that ...


1

For brevity, I'm going to say "we win" if the game stops with a sum of $5$, and "we lose" if the game stops with a sum of $7$. Let $p_k$ be the probability that we win, given that the first roll is $k$. Suppose we roll a $1$ and then a $2$. After the $2$, the probability that we will win is $p_2$; that is, all that matters after that roll is that we last ...


1

The generator matrix is: $$ G= \begin{bmatrix} -2 & 2 & 0 & 0 \\ 3 & -5 & 2 & 0 \\ 0 & 3 & -5 & 2 \\ 0 & 0 & 3 & -3 \\ \end{bmatrix} $$ The balance equations in vector form are: $\mathbf{\pi G = 0}$, so, working down each of the four columns in turn: \begin{align} ...


1

It is implied (and it should have been said) that all other probabilities are zero, i.e., the probability is supported by the origin, the basis vectors and their opposites; $p(y)=0$ unless $y$ is one of the $x_k$ or its opposite or the origin. The interpretation is that a random walk has probability zero of taking two jumps (including diagonal jumps) at a ...


1

As far as I can see, $p$ is just a distribution of a i.i.d random variable $X_i$ taking values on $\mathbb{Z}^d$. With respect to chosen generating set, any member of $\mathbb{Z}^d$ is represented as a coordinate vector $(k_1,\cdots,k_l)$ (using notation used in the original article. Now $p$ is saying that $P(X_i=(0,0,\cdots,0,\pm 1,0,\cdots,0)) = ...


1

Consider the two Markov kernels on the finite state space $\{1,2,3,4,5\}$, expressed as stochastic matrices: $$ K_\epsilon=\left[\matrix{ 0&1-\epsilon&\epsilon&0&0\cr 1-\epsilon&\epsilon&0&0&0\cr \epsilon&0&1-2\epsilon&\epsilon&0\cr 0&0&\epsilon&0&1-\epsilon\cr ...


1

Conditioned on any state, the progression of a Markov chain is independent of any earlier state, so yes, $$ P(X_{n+m} = j \mid X_n = k, X_0 = i) = P(X_{n+m} = j \mid X_n = k) $$ and that means also that you are right, that $$ P(X_{n+m} = j \mid X_{n+1} = b, X_n = k, X_0 = i) = P(X_{n+m} = j \mid X_{n+1} = b) $$


1

I think you need the condition that the Markov Chain is reversible. Def: Let $X$ be an irreducible Markov chain such that $X_n$ has the stationary distribution $\mathbb{\pi}$ for all $n$. The chain is called reversible if the transition matrices of $X$ and its time-reversal $Y$ are the same, which is to say that $$\pi_iPij = \pi_jPji \:\:\:\: \forall ...


1

The other answer is incorrect in saying that you need detailed balance. Intuitively, the equation in the OP says that the probability going into state $i$ is equal to the probability going out of state $i$, when the distribution is the stationary distribution. But the difference between these two quantities is $(\pi P - \pi)_i$, which is zero by the ...


1

To see a counterexample to your argument, let for example the transition probabilities: $6 \to 5= 0.01$ and $6 \to \{3,4\}=0.99$, $5 \to 6= 0.01$ and $5 \to \{1,2\}=0.99$. Now, a simple calculation shows that $$P_6[T_{1,2}<+\infty]\le 0.01 < 0.99 \le P_5(T_{1,2}<+\infty)$$ For them to be equal, you need certain symmetry conditions on the ...



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