Tag Info

Hot answers tagged

3

Are you sure you wrote this correctly? It didn't take me long to find a counterexample. Take $$ P = \pmatrix{0 & 1\cr 1/2 & 1/2\cr},\ \Xi = \pmatrix{1/2 & 0\cr 0 & 1\cr},\ \Xi^2 - P^T \Xi^2 P = \pmatrix{0 & -1/4\cr -1/4 & 1/2\cr}$$


3

Hint: Define the random variable with $Y_n \in \{0,1\}$ (indicator variable with $2$ states) as follows $$Y_n=\begin{cases}1,& X_n=6\\0,&X_n\neq6\end{cases}$$ with transition matrix $$\mathbf P_{(1)}=\begin{array}{r|cc|r}&0&1&\\\hline0&\frac{4}{5}&\frac{1}{5}\\1&1&0 \end{array}$$ Initially $Y_0=1$. You want to find the ...


3

What about using the $\infty$-norm? That is $$ \|A\|_\infty = \sup_{x: \|x\|_\infty=1} \|Ax\|_\infty. $$ Take a vector $x$. Then $$ \|Px\|_\infty \le \max_{i}\left|\sum_j p_{ij} x_j\right| \le \max_{i}\sum_j p_{ij} (\max_k |x_k|) \le\|x\|_\infty. $$ Denote $z:=Px$. Then $$ \|P^T\Xi^2 z\|_\infty = \max_i \left|\sum_j p_{ji}\xi_j^2 z_j\right| \le\max_i ...


3

These are not problems on a circle but on the linear interval of integers $$L=\{0,1,2,\ldots,12\},$$ where the hand $12$ is represented by both states $0$ and $12$, and every other hand by the state with its number. Starting from $k$ in $L$, the mean number of steps $t_k$ that the symmetric simple random walk needs to hit $0$ or $12$ is $$t_k=k(12-k),$$ ...


2

Sure. You just need to compute the eigenvalues that are not $1$. In this case your eigenvalues are the solutions to $\lambda^2-1.4\lambda+0.4=0$, which are $1$ and $0.4$. This means that $p A^n$ = $\pi + 0.4^n v_p$ for some distribution $v_p$ depending on $p$, and where $\pi$ is the equilibrium distribution. Specifically $v_p$ is the component of $p$ in the ...


2

It's true. See for example Theorem 5.3 of this reference. The idea is that you can indeed apply the strong law of large numbers by splitting $N_T(x)/T$ into excursion times: considering how long it takes to come back to state $x$ when one has just reached state $x$. These excursion times are all independent of each other and hence the strong law applies.


2

The Markov chain of the residues mod $13$ is irreducible and aperiodic on the finite state space $\mathbb Z/13\mathbb Z$ and its transitions are invariant by translation hence the unique stationary distribution is uniform. Thus, for every $i$, $P(X_n=i\pmod{13})\to\frac1{13}$ when $n\to\infty$. In particular, $P(13\ \text{divides}\ X_n)\to\frac1{13}$ when ...


2

Consider a "renewal time" as a time when the number of customers goes from $1$ to $0$. After a renewal time, we wait Exponential($\lambda$) time in each of the states $0, 1_u, \ldots, (n-1)_u$: a total expected time $n/ \lambda$ of which an expected time $1/\lambda$ is spent in state $0$. Then the server becomes active, and we are in a "normal" M/M/1 queue ...


2

A finite Markov chain always has at least one steady-state distribution. If the transition matrix is $A$, each column of $A-I$ sums to $0$, so $A-I$ doesn't have full rank, and there is at least one nontrivial solution to $Ax=x$. On the other hand a Markov chain with an infinite state space doesn't have to have a steady-state distribution. For example, ...


2

The question asks to compute $P^n$ for every $n$, where $$2P=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}=3J-I,\qquad 3J=\begin{pmatrix}1&1&1\\1&1&1\\1&1&1\end{pmatrix}.$$ This is pure algebra, only, playing with $3\times3$ matrices in the ring $\mathbb R[J]$. Note (and this will be the only matrix ...


1

Let $Y_k$ be a random variable which is 1 if $X_k = j$ and 0 otherwise. Observe that $V_n = \sum_{k=1}^n Y_k$. Then use linearity of expectation.


1

You should exploit the symmetry of the Markov chain and of the state space. Try to work out the case with 4 points on a circle, then 6 points and then you should have understood how to solve the case of $2n$ points on circle.


1

Denote with $1$ it's starting position. Let $h(i)$ be the expected number of steps to return to the position $1$ starting from position $i$ for $i=1,2,\ldots 12$. To avoid confusion it can be helpful to denote state $1$ (the initial state) as state $13$ when you visit it the second time. With this notation you have that ...


1

In my opinion, the tricky bit is to figure out a way of sampling the space of walks that you are interested in. Luckily, the problem is a classic one in polymer physics (e.g. modelling a 2d ideal polymer on a square lattice between fixed points), with an added constraint. Well, actually the constraints are two: the lengths of the segments in both ...


1

Let $X_t$ be the number of busy servers in a $M/M/\infty$ queuing system. You want to compute $E(X_t|X_0=n)$. This can be done by considering the sum $$X_t=Y_t+Z_t,$$ where $\{Y_t|X_0=n\}\sim Binomial(n,e^{-\mu t})$ is the number of servers that did not complete service in the interval $(0,t]$ (out of the $n$ that were busy), and $Z_t\sim ...


1

Are we allowed to note that this is the dynamics of a population such that every living individual gives birth to one new individual at rate $\lambda$ and dies at rate $\mu$, independently of the other living individuals? Because this is what rates proportional to the population are modelling, actually... Then one sees that a population of $i\geqslant1$ ...


1

I think you are struggling because you are misunderstanding what we are intending to describe with the term steady state. You are correct, a Markov Chain is completely determined once it is defined. That means, no matter what step (or time) you are interested in, I can find the distributions for that step. This property is known as uniqueness. Though, that ...


1

$0\to1\to0\to1\to0\to1\to0\to1\to0\to1\to0\to1\to0\to1\to0\to1\to\ldots$ -- Did From state $0$ you go to state $1$ with probability $1$ and from state $1$ you go to state $0$ with probability $1$. -- Ritz


1

An elementary argument we can make is as follows: Define by $d_n$ the expected number of deaths occurring before we reach state $n+1$ given that we start in state $n$. We clearly have $d_0=0$. Further we can write an expression for $d_n$ noting that, with, probability $\lambda_n$, we will have no deaths before reaching state $n+1$, and with probability ...


1

I was able to figure it out eventually... 1. \begin{align*} &\sum_{i \in J} \left|\frac{V_i(n)}{n}-\pi_i\right| + \sum_{i \notin J} \left(\frac{V_i(n)}{n}+\pi_i\right)\\ &= \sum_{i \in J} \left|\frac{V_i(n)}{n}-\pi_i\right| + \left(1-\sum_{i \in J} \frac{V_i(n)}{n}\right)+\sum_{i \notin J}\pi_i & \sum_{i \in I} V_i(n)=n\\ &= \sum_{i \in J} ...


1

By the Gershgorin's theorem , for every eigenvalue $\lambda$ of $\Xi(Id-P)$ exists $j$ such that $|\Xi_{jj}(1-P_{jj})-\lambda|\leq\Xi_{jj}(\sum_{i\neq j }|-P_{ji}|)$ Now, notice that for every $j$, $\Xi_{jj}(1-P_{jj})=\Xi_{jj}(\sum_{i\neq j }P_{ji})=\Xi_{jj}(\sum_{i\neq j }|-P_{ji}|)\geq 0$. Thus, $|\Xi_{jj}(\sum_{i\neq j ...


1

Your approach is certainly right: superharmonic functions form a convex cone, that is if $f$ and $g$ are superharmonic, then $\alpha f + \beta g$ is superharmonic for non-negative $\alpha$ and $\beta$. Moreover, if $f$ and $-f$ are superharmonic then $f$ is harmonic, so the whole question is to construct an example when there are superharmonic functions that ...


1

As often, it is difficult to answer this question because the OP says nothing about their background. Anyway, a standard approach to determine the recurrence/transience of a Markov chain (its type) is to compute $P_1(T_0\,\text{infinite})$ as the limit of $P_1(T_n\lt T_0)$ when $n\to\infty$, since each $P_1(T_n\lt T_0)$ involves only a finite Markov chain. ...


1

Consider some nonnegative integers $i$ and $j$. To reach $i+j$ starting from $0$, one must first reach $i$ starting from $0$ then reach $i+j$ starting from $i$. The probability of the first event is $d_i$. By the Markov property and the invariance of the dynamics by the translations of $\mathbb Z$, the property of the second event conditionally on the ...


1

The relatively high number of states is only there to force you to understand the structure of the paths the Markov chains can follow to reach state $20$ starting from state $11$. Thus, a mandatory prologue to the proof is to draw a picture of the states and the transitions of the Markov chain... Once this is done (and if you did not do it, the proof below ...


1

What you're confusing is the idea of the existance invariant measure and convergence to the invariant distribution. A lot of Markov chains have invariant measures (in fact, on a finite state space you always have at least one, and in general for irreducibility a null recurrent chain will have an invariant measure and positive recurrent will have invariant ...


1

Let $u=(1,\ldots,1)$. Notice that $P^t\Xi u=\Xi u$ and $Pu=u$. Therefore, $P^t\Xi Pu=P^t\Xi u=\Xi u $. So, $\Xi_{ii}=\sum_{j=1}^n\Xi_{ij}=\sum_{j=1}^n(P^t\Xi P)_{ij}$. Next, $\Xi_{ii}-(P^t\Xi P)_{ii}=\sum_{j\neq i}(P^t\Xi P)_{ij}=\sum_{j\neq i}|-(P^t\Xi P)_{ij}|\geq 0$. Therefore, $\Xi-P^t\Xi P$ is diagonally dominant symmetrix matrix with non ...


1

Let $Y=X_{T_S}$ and $$C=\left[\lim\limits_{\alpha\to\infty}X_\alpha=Y\right].$$ For every fixed $\alpha$, on the event $[T_S\leqslant\alpha]$, $X_\beta=Y$ for every $\beta\geqslant\alpha$ hence $X_\beta\to Y$ when $\beta\to\infty$. This proves that $[T_S\leqslant\alpha]\subseteq C$. This inclusion holds for every $\alpha$ and ...


1

In addition to your comment: Let $P$ be a stochastic, irreducible matrix. Since $P$ is irreducible it will be either aperiodic or periodic. $P$ aperiodic$\iff\displaystyle\lim_{k\to\infty}P^k$ exists. $P$ periodic matrix with period $d>1$ $\iff \displaystyle\lim_{k\to\infty}P^k$ does not exist. We can prove the latter using cyclic subclasses.


1

I think so... Here's my thought. Let $M$ be an irreducible, symmetric and positive-definite $n\times n$ stochastic matrix, with spectrum $\sigma(M)=\{\lambda_1, \lambda_2,\ldots, \lambda_n\}$. Since $M$ is stochastic, we have that $\lambda_1=1$. Since $M$ is symmetric we have that $M$ is diagonalizable. Since $M$ is positive definite, we have that all ...



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