# Tag Info

2

The book suggests to look at what goes through an edge. Indeed, at equilibrium, since the only way to go from $\{j\mid j\leqslant i\}$ to $\{j\mid j\geqslant i+1\}$ or from $\{j\mid j\geqslant i+1\}$ to $\{j\mid j\leqslant i\}$ is to use the edge $\{i,i+1\}$, the fluxes through this edge in the direction $i\to i+1$ and in the direction $i+1\to i$ must ...

0

If we make the boundaries at $0$ and $N$ reflecting, rather than absorbing, then your random walk is the Ehrenfest urn model. It is well-known that this Markov chain has invariant distribution $\pi_i={N\choose i}/2^N$ for $0\leq i\leq N$. In particular, the expected time to return to the origin, starting there, is $\mathbb{E}_0(T_0)=1/\pi_0=2^N$. This ...

0

If $i \in [0.1N,0.99N]$ then the expected time is exponential, since in order to reach the boundary when you are outside the interval $[N/4,3N/4]$, you move towards the boundary with probability at most than $1/4$. If the probability was $1/4$, then the expected time until reaching the boundary would be exponential in $N$, and hence $E(T_i)$ is exponential ...

1

Conway's algorithm would compare identical terms on the left and right of 131131: length $1$: yes 1 both sides length $2$: no 13 on left, 31 on right length $3$: yes 131 both sides length $4$: no 1311 on left, 1131 on right length $5$: no 13113 on left, 31131 on right length $6$: yes 131131 both sides So you have yes for $1$, $3$ and $6$, and $6$ faces ...

0

I can do your warm up, but the more general problem will be harder because you can't use the same state space reduction idea. Write for our state space the number of dimensions spanned so far, $\{0,1,2,3,\ldots,n\}$. One we have $k$ dimensions spanned, $2^k$ of the $2^n$ possible vectors will not give us any new dimensions, while $2^n-2^k$ of them will ...

2

There are at least three ways to answer this problem. If you just want a numerical answer, the easiest is probably is just to keep squaring the matrix to approximate $P^{\infty}$. Because a transition matrix can be written as $$V \begin{bmatrix} 1 & 0 & 0 \\ 0 & a & 0 \\ 0 & 0 & b \end{bmatrix} V^{-1}$$ with $a < 1$ and $b ... 2 The stationary distribution is a row vector$\pi$which satisfies $$\pi P = \pi$$ so the system of equations you need to solve isn't$P x = 0$, but rather$ \pi P = \pi$with the additional constraint that the elements of$\pi$must sum to 1. If we write$\pi = \begin{pmatrix} x & y & z \end{pmatrix}$so$x$,$y$and$z$are the elements of the ... 1 HINTS: Start by showing (using the definition of a Markov process) that$1$is an eigenvalue of$A$. Then show that if all the entries of$A$are positive, the vector$(1,1,\dots,1)$is the only eigenvector (up to scalar multiples) with eigenvalue of the matrix$A^\top$. (In general, you'll need to apply this to some power of$A$. Check the definition of ... 2 Unfortunately your proof contains an error,$\pi P = \pi Q$does not imply$P=Q$. Consider for example $$P = \begin{pmatrix} 0.5 & 0.5 & 0 \\ 0.5 & 0 & 0.5 \\ 0 & 0.5 & 0.5 \end{pmatrix}$$ and $$Q = \begin{pmatrix} 0.33 & 0.33 & 0.33 \\ 0.33 & 0.33 & 0.33 \\ 0.33 & 0.33 & 0.33 \end{pmatrix}.$$ These both ... 1 Well, I don't even think the first approach is correct. Notice that in the original MC, the expected number of jumps between to two visits in 1 is 1/$\pi_1=6$, and so is it for state 5. If the first approach is correct, then on average, there are 4 visits to state 1 between two successive visits to 5, which is not intuitively correct. In fact, the desired ... 1 Please refer to this or to this. The relevant key-word is lumpability. 0 I see no question in your post, except this consideration: The question adds at the end "for |s|<1" now isn't this a bit pointless, generating functions considered for their parameter being 1 is when they are actually useful! ...which happens to be squarely wrong. No, the generating function$g:s\mapsto E[s^X]$is not used only at$1$. Two basic ... 0 From the looong string of comments above, it seems a problem of understanding might be related to the words distribution of a stopping time. Let us explain these. To this end, one should consider a probability space$(\Omega,\mathcal F,P)$, a filtration$(\mathcal F_n)_{n\in\mathbb N}$on$(\Omega,\mathcal F)$, and a random variable$S:(\Omega,\mathcal F)\to ...

1

The number of states is more than simply the end-of-day inventory count {0,1,2,3,4,5} because we must include the machine's On/Off state as well. We will adopt the notations On(k) and Off(k) for the corresponding machine state + inventory count. There is no disaster if we include states that cannot be attained (by valid transitions). In some cases we may ...

0

To be in state 5 after eight steps starting from state 0, you must go from state 0 to state 7, from state 7 to state 4, from state 4 to state 6, from state 6 to state 5, and spend another four steps going from states to the same states. You need to sum the probabilities of the different patterns of steps which will make you be in state 5 after eight steps ...

0

Assume that the nonzero transitions on the state space $\{a,b,c\}$ are $a\to b$, $b\to a$, $b\to c$, and $c\to c$. Then $\{a,b\}$ and $\{c\}$ are communicating classes, $\{a,b\}$ is not a closed communicating class, $\{c\}$ is a closed communicating class.

0

If I understand you correctly, the question is "What is the most likely path (sequence of states) of a continuous-time Markov chain (CTMC), given some evolution time $t$ and possibly intitial and/or final state?" This problem has been solved here through a "Viterbi-like" dynamic programming algorithm. Matlab and R implementations are available for download ...

1

Thanks to the symmetrical structure of $P$, one can compute every power $P^n$ rather easily. To see how, let us introduce $I$ the $4\times4$ identity matrix and $J$ the $4\times4$ matrix whose every entry is $\frac14$. Then, $$P=(1-4a)I+4aJ.$$ The computations involving matrices that are polynomial in $J$ are simple, thanks to the identities $I^2=I$ and ...

0

You solve both of them with: $$P(t)=\exp(tG)$$

3

Here is a martingale (not a markov chain) solution that comes from noticing that he's playing a fair game, i.e., if $X_n$ is his money at time $n$ then $E(X_{n+1}|X_n)=X_n$. By the optional stopping theorem, the expected value when the game is finished is equal to the expected value when the game starts. He ends with either $\$0$or$\$10$ (sorry, but I ...

1

This looks to me as an absorbing Markov process. He starts at 2 GBP (forgive me for the denomination), if he wins he goes to 4, then to 8 and possibly to 10. But from 8 he can go back to 6 and from 6 back to 2 or wins to 10. From 2 he can also lose to 0. So we have the following "states": 0, 2, 4, 6, 8, and 10 where 0 and 10 are the absorbing states. From ...

0

Your formula is correct, assuming $q=1-p$; here's argument in biological terms. This Markov chain is a birth-death process and the concept you are looking for is the fixation probability (called the absorption probability in general). Formula (1) on this page gives the probability of absorbing at $N$ starting at state $i$, where $\gamma_k = \frac{1-p}{p}$ ...

1

A random walk, in the context of Markov chains, is often defined as $S_n = \sum_{k=1}^n X_k$ where $X_i$'s are usually independent identically distributed random variables. My understanding of your given statement is the probability of the summation $S_n$ reaching value $i$ given all its previous history.

3

Given: $$\frac{d}{dt} \left[ \begin{array}{c} A(t)\\ N(t)\\\end{array} \right] = \left[ \begin{array}{c c} -(a+b) & 0\\ a & -g\\ \end{array} \right] \left[ \begin{array}{c} A(t)\\ N(t)\\\end{array} \right]$$ For this problem, we find the eigenvalues by using $|A - \lambda I| = 0$, and then solve $[A-\lambda_i I]v_i = 0$ to get the eigenvectors. ...

2

This is a good question, and a nice point to bring up. The truth is that when dealing with a time-homogenous Markov chain, the transition matrix $P$ is supposed to be intrinsic to the Markov chain without reference to a particular initial distribution. That is, you can set up the transition matrix without reference to some initial distribution given in a ...

3

Linear birth-death processes are additive, this means that the sum of some independent processes with initial populations $i$ and $j$ has the distribution of a single process with initial population $i+j$. In particular, the probability that the latter dies before time $t$ is the probability that the former both die before time $t$. Thus, ...

0

Hint: For large values of $Y(>30)$ you can approximate binomial distribution by the Gaussian distribution. See this. Consider each outcome of the dice roll be from Bernoulli distribution such that $P_{Win}=p(w)$ and $P_{NotWin}=p(d)+p(l)=1-p(w)$.

2

This is a strange question, because usually in a CTMC the value at $t=0$ is specified. The transition rates don't determine the probabilities by themselves, you have to say how the process starts out. You could get the result in terms of the probabilities $P(X(0)=n)$: I get  P(X(0)=2 | X(1)=3, X(2)=4, X(3) = 5) = \dfrac{P(X(0)=2) P_{23}(1)}{P(X(0)=0) ...

Top 50 recent answers are included