Tag Info

New answers tagged

0

P=\begin{bmatrix} 0.5 & 0.4 & 0.1 \\ 0.4 & 0.5 & 0.1 \\ 0.2 & 0.2 & 0.6 \end{bmatrix} This transition matrix represents the current days conditions as the rows and tomorrows condition as the column. So to find the probability of a rainy tomorrow given today is sunny go to $P_{13}$. To find future days you must multiply the matrix ...


0

Define $\tau_{00} = \inf \{ n>0 : X_n = 0 | X_0=0 \}$ (with the usual convention $\inf \emptyset = +\infty$). Then either you stay at $0$ the first step, in which case $\tau_{00}=1$, or you leave $0$ in the first step, in which case $\tau_{00}=1+T$, where $T$ is geometric with parameter $q$. So $\mathbb{E}[\tau_{00}] \leq 1+\frac{1}{q}$. Now you use the ...


0

Let $Y_t = 1 \text{ if }X_t \neq 0; Y_t = 0 \text{ if }X_t = 0$. This is a 2 states Markov chain; 0 is recurrent for $X$ iff it is recurrent for $Y$. For this Markov chain, the distribution of the time of return to 0 is a geometric law; it is almost always finite. Hence the chain is recurrent.


0

It is not bounded sorry for the inconvenience. Here is the proof a friend gave me (thanks a lot to him): (It can also be found here) Let consider the set $W_1 = \{w = (s,w_1,\dots)| w_1 \leq n\}$. Then $\mathcal{E}^n_n$ is bigger than $\displaystyle\sum_{w\in W_1}O^n_n(w)*P(w)$. \begin{align} \sum_{w\in W_1}O^n_n(w)*P(w) &= \sum_{k=0}^n \sum_{i=0}^k ...


1

Note that unless you're distinguishing between the players in some way (e.g., modeling their different skill levels), then their identities don't matter, and you can work with a much smaller number of states. To see how this works, imagine that each live player is "stuck" to all the players that he has frozen. So if a live player has frozen $n$ other ...


1

The classical example of the first case is $ b = a + c$ where $a$ and $c$ are independent fair Bernoulli variables, $P(a=1)=P(a=0)=1/2$, and the sum is modulo 2 (XOR). Then $I(a;b)=0$ (knowing one of the inputs tells you nothing about the output) and $I(a;b|c)=1$ (given that one of the inputs is know, to know the other is to know the output). For the ...


0

I don't think the Ballot Theorem justifies it. It comes from evaluating the probabilities involved: \begin{eqnarray*} &&p\cdot P(S_{n-1} = b-1) - q\cdot P(S_{n-1}=b+1) - \dfrac{b}{n}P(S_n=b) \\ && \\ && \qquad\qquad = p\binom{n-1}{\frac{n+b-2}{2}} p^{\frac{n+b-2}{2}}q^{\frac{n-b}{2}} - q\binom{n-1}{\frac{n+b}{2}} ...


0

There are two parts to MCMC. The first part is Markov Chain and the second is Monte Carlo. Mostly, MCMC methods are used to do multi-dimensional integration when analytic methods are difficult or impossible. Difficulties may arise because regions are partly described in terms of functions that do not have integrals in closed form. Also, it is sometimes ...


0

Yes, it's just a slightly more general version of the Chapman Kolmogorov equations; Let $P_{m,n}$ denote the matrix of probabilities of transitioning from a given state at time $m$ to another at time $n$. That is $$[P_{m,n}]_{i,j}=P[X(n)=j|X(m)=i].$$ Using the law of alternatives $$[P_{m,n}]_{i,j}=P[X(n)=j|X(m)=i] = $$ $$\sum_{k} ...


1

Assume we have a state space $S = \{1,2, \ldots, k\}$. Then the sum of the elements lying on $m-$ row of the transition matrix is: $$\sum_{i=1}^k p_{mi}\begin{array}[t]{l}=p_{m1}+p_{m2}+\cdots+p_{mk} \\ =prob\{X_n=1\, \mid X_{n-1}=m\}+\cdots+prob\{X_n=k\, \mid X_{n-1}=m\} \\ =prob\left\{(X_n=1)\cup (X_n=2) \cup \cdots \cup (X_n=k)\, \mid ...


1

First of all, any right-stochastic matrix $A$ has an eigenvalue of $1$. This is easiest to see because $A^T$ has $\begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix}$ as an eigenvector. So $A$ also has an eigenvalue of $1$. Provided all entries of the corresponding eigenvector have the same sign, the eigenvector can be normalized to obtain a stationary ...


0

A (non-zero) steady state vector under a matrix transformation is an eigenvector of the matrix corresponding to an eigenvalue of 1. Any matrix without a unit eigenvalue will not posses a ( non-zero) steady state vector . an easy example is ... $ \begin{pmatrix} 2 & 0 \\ 0 & 3 \end{pmatrix} $ which has eigenvalues of 2 and 3.


1

For intuition, think about a recurrence relation, say $a_n = a_{n-1} + a_{n-2}$. You can turn this into a first order recurrence in two variables by writing $a_n = a_{n-1} + b_{n-1},b_n = a_{n-1}$. We do the same thing to turn higher order differential equations into first order differential equations. Do the same thing for your Markov chain: given the ...


2

Have you really looked at a hidden markov model in graphical form? I'm guessing a lot of things would become clearer if you did so. For (1) Yes, you need to have the Markov property to show that $p(\mathbf{O_t}|q_1, q_2,\ldots, q_T) = \prod_t p(o_t|q_t)$. Otherwise, you would have the more general expression. Let me just demonstrate with a simple example. ...


2

Here is an interpretation of the original question. Assume the states are $S_i$, each representing the event that there are exactly $i$ non-empty boxes. Clearly, we have $$p_{ij} = \begin{cases}i/k & \text{if }i = j \\ 1-i/k & \text{if } j = i + 1 \\ 0 & \text{otherwise}.\end{cases},$$ where $i,j\in\{0,1,\dots, k\}$. This gives us a Markov chain ...


0

After thinking some more about it, I came up with this, but I am not sure this is right: Every probabilty measure $\mu$ on $B(S)$ can be written as: $\mu = \int_S \delta_y \mu(dy)$, then we have for $O\mu$ $O\mu = O\int_S \delta_y \mu(dy)=\int_S O\delta_y \mu(dy)$ (last equality holds because of the linearity of O) This cannot be defined, if ...


0

In regards to question $(2)$: We have that $p_{i,j} > 0\ \forall i,j$, consider $$p_{i,j}^{(2)} = \sum_{k}p^{}_{i,k}p_{k,j} > 0,\text{ since }p > 0 \ \forall i,j$$ With an induction step, we can show that $p^{(n)}_{i,j} > 0 \ \forall i,j,n$. Let us assume that $p^{(n)}_{i,j} > 0\ \forall i,j$ for some $n$, we will show that $p^{(n+1)}_{i,j} ...


1

Starting with the definition, $\newcommand{\prob}{\mathbb{P}}$ $$ \prob(X_n = x_n | X_{n-1} = x_{n-1},…,X_0 = x_0 ) = \prob(X_n = x_n | X_{n-1} = x_{n-1}) $$ Then let $j_1...j_N$ be a labelling of $\{0,1,2,3,...,t_n\}\setminus \{t_1,t_2,...,t_n\}$. You just need to sum over the values you don't specify in the conditioning: \begin{align} &\prob(X_{t_n ...


0

Yes, the Markov chain you gave is aperiodic. To see this, you can try proving that whenever the underlying graph is strongly connected (or, in other words, the MC is irreducible) and contains at least one self-loop, then the Markov chain is aperiodic.


0

The generating function is $$ \phi(t)=\sum_{k\ge 0} {\mathbb{P}}(X=k) t^k=\frac{1}{2-t} $$ and it's easy to prove by induction that the $n$-fold composition of $\phi(t)$ with itself is $$ \phi^{(n)}(t)=\frac{n-(n-1)t}{(n+1)-nt} $$ so the probability that the process is extinct by the $n$th generation is $$ \phi^{(n)}(0)=\frac{n}{n+1}$$ and as you say the ...


0

The definition of aperiodic is that every state is aperiodic, meaning that $\gcd\{t: \ P(X_t=s | X_0=s)>0\}=1$ for all states $s$. You can easily verify this to be the case for your Markov chain with one state and a self-loop.


0

Define the state space as the number of broken machines $S=\{0,1,2\}$. Now try to draw the graph: three nodes corresponding to the three states and add the transition rates between all of them. You should get a simple birth and death process as you expected. From this graph you can derive the transition matrix of the Markov chain and the appropriate backward ...


1

The idea is this, you start with a vector $x$ and write it out in the eigenvalue basis of the PageRank matrix. Suppose that $1=\lambda_{1}> |\lambda_2|\geq ...\geq |\lambda_{n}|$. We write $$x=a_1 v_{1} + a_2 v_{2} +... + a_{n}v_{n}$$ Now multiplying by $A$ (both sides $k$ times) we have: \begin{align*} A^{k}x &= \lambda_{1}^{k} a_{1}v_{1} + ...


0

You seem to be thinking in nearly the right way, but you are putting your thinking together in a way that might make it difficult to work with it. First, when constructing the transition matrix, you do not need to consider the initial values. That makes it a bit easier to think about it. For each possible state $i$ (if the animal is at position 1, 2, 3, or ...


1

Double check the definition of the period. First off, a period always refers to a particular state $i$. Specifically it's the GCD of all times $k$ for which a return is possible. So figuring out the "shortest time of return" is not sufficient. Next, a state $i$ is aperiodic if its period is 1. A Markov Chain is aperiodic if all states have period 1. In ...


2

Assume that the random walk is defined as $$ X_n = \sum_{k = 1} ^ n \xi_k $$where $(\xi_a)_{a\ge 1}$ are iid and such as $P(\xi_1 = \pm 1) = 1/2$. $$1_{T_0 = m,X_0=0} = 1_{T_0 = m,X_0=0, X_1 = 1}+ 1_{T_0 = m,X_0=0, X_1 = -1} $$ Now using the Markov property, and as $T_0$ depends in a deterministic way on $(X_a)_{a\ge 1}$, you get $$ T_0 |(X_0=a, X_1 = ...


0

For any $n\times n$ stochastic matrix $P$, it is true that $$\left|\lambda_i\right| \le 1,\quad i = 1, \ldots, n.$$ Also, we can easily prove that $\lambda = 1$ is an eigenvalue of matrix $P$. Combining these facts, it holds that the spectral radius of $P$ is $\rho(P) = 1$. Due to irreducibility, we may apply Perron - Frobenius theorem to the stochastic ...


1

Assume discrete time $t \in \{0, 1, 2, \ldots\}$. Let $Z(t)$ be the value of your Markov chain, so $Z(t) \in \{s_1, s_2\}$. Let $R(t)$ be the observation on slot $t$ (assume $R(t) \in \{a,b\}$). Assume that $Pr[R(t)=a|Z(t)=s_1] = 0.25$, $Pr[R(t)=a|Z(t)=s_2]=0.5$. Let $H(t)$ be the history of observations up to time $t$: $$ H(t) = [R(0), R(1), \ldots, ...


0

There are different types of Markov chains, which you will be able to recognize by their transition matrix (and/or by their transition graph). These transition matrices have the property that their columns add up to one and all entries are between 0 and 1. I will discuss here two of the most common types. (Here I will use the convention that the ...


0

Look at the 'reverse' move, in which you pick a card from within the deck and move it to the top. These reverse moves can get you from starting state $(a_{\pi(1)},\ldots,a_{\pi(n)})$ to final state $(a_1,\ldots,a_n)$ by first locating card $a_n$ and moving it to the top, then locating card $a_{n-1}$ and moving it to the top, and so on, finally moving card ...


0

Events are occurring under the homogeneous process $N$ at rate $\lambda$. Each such event, occurring at time $t$ say, is then either counted in the $N_c$ process, with probability $p(t)$, or ignored with probability $1-p(t)$. So it's not correct to say that $p(t)$ is the probability that an event occurs at time $t$ in process $N_c$. Mathematically, we can ...


0

$\alpha \geq 1$ means the chance to hit $C$ at any time is greater than the chance to hit $B$, so the chance to hit it in finite time will be greater or equal and we are done. In the case $\alpha <1$ let's say the stopping time of the $k$th-entry to $B$ is $\tau_B (k)$. With the (strong) Markov property we get $\mathbb{P}_x \{\tau_B ...


1

To compute $P(j\cap i)$, the probability of reaching $i$ having reached $j$ as minimum, consider playing two games after each other: $G$ Is the game that is won by starting from zero, ending at $j$ without having reached $i$ $H$ is the game that is won by starting from $j$, ending at $i$ without having reached $j-1$ For the first one we have $$ ...


0

I hope I'm understanding you correctly. If $X(t)$ is the number of people who want to try at stage $t$, then $X(0) = n$ and the conditional distribution of $X(t+1)$ given $X(t)$ is binomial with parameters $X(t)-1$ and $q$. If $T$ is the first $t$ where $X(t) = 0$, then conditional on $T$ the number of successes $S$ is binomial with parameters $T$ and $p$. ...


0

For this to be a Markov chain, the probability specification must be so that $$ P_w(X_{n+1}=y| X_n=x)=\begin{cases} w_x& \text{if}\,\,y=x+1\\ 1-w_x& \text{if}\,\, y=x-1\\ 0 &\text{otherwise}\end{cases} $$ independent of all earlier steps. So we can write that $$ X_{n+1} = X_n + Z_n $$ where $Z_n$ is plus or minus 1 with probabilities given ...


1

Obviously, $$P(W_1 > w_1, W_2 > w_2 ) = \int_{0}^{1}\int_{0}^{1}f(x, y)\ \text dx\text dy$$ cannot be correct because the lhs is a function of $w_1$ and $w_2$ while the rhs, being a real number, isn't. Furthermore, recall that by the definition of probability density functions, if $f(w_1, w_2) = \lambda^2e^{-\lambda w_2}{\bf ...


0

I think Zoe's approach is the easiest but that she has the equations wrong. Let $$T_{11} = E(T_1\mid X_0=1) \\ T_{21} = E(T_1\mid X_0=2).$$ We want to find $T_{11}$. Considering the possible transitions between states $1$ and $2$ and their probabilities, we get equations: $$T_{11} = 1+\dfrac{1}{2}T_{21}\qquad\qquad\qquad (1) \\ T_{21} = ...



Top 50 recent answers are included