# Tag Info

## Hot answers tagged markov-chains

8

Let $k_{ij} = \mathbb E[T\mid X_0 = i, Y_0=j]$. So we want $k_{00}$. Noting the clear symmetry in both axes, we have the equations \begin{align*} k_{00}&=1+k_{10} \\ k_{10}&=1+\frac{1}{4}k_{00}+\frac{1}{4}k_{20}+\frac{1}{2}k_{11} \\ k_{20}&=1+\frac12k_{12}+\frac14k_{10} \\ k_{11}&=1+\frac12(k_{12}+k_{10}) \\ k_{12}&=1+\frac14(k_{11}+k_{...

6

Let us encode the hexagonal grid using the hexagonal lattice $$\mathsf{G} = \{ a + b \omega : a, b \in \mathbb{Z} \}, \qquad \omega = e^{i\pi/3},$$ where each $z \in \mathsf{G}$ represents the center of a hexagonal cell. Then two cells $z_1$ and $z_2$ are adjacent precisely when $\left| z_1 - z_2 \right| = 1$. We also write $\mathsf{C}_n$ for the set of ...

5

Here's a nice method that doesn't require setting up $100$ equations. Let $\mu_i$ be the mean number of steps to reach state $i+1$ after reaching state $i$ for the first time, so we want $\sum_{i=0}^{99}\mu_i$. By the Markov property, $$\mu_i=1+\frac{1}{2}(\mu_{i-1}+\mu_i)\implies\mu_i=2+\mu_{i-1}.$$ Now $\mu_0=1$, so $\mu_i=2i+1$, hence the expected time to ...

4

The difference is that a $50$% loss and a $50$% gain (in either sequence) result in a net loss (AM-GM inequality), whereas halving and doubling (in either sequence) do not result in a net loss. Joshi is presenting (and solving) a different problem, one in which half the time the trader's expected return is $100$%. So there's no a priori reason to expect ...

4

They’re computing two entirely different things. Wilmott is computing the minimum number of days out of $260$ on which you must make a profit in order to come out ahead; Joshi is computing the expected value of your portfolio. Applying Joshi’s calculation to Wilmott’s setting, we get an expected value after $260$ days of (0.6\cdot1.5+0.4\cdot0.5)^{260}=1.1^... 4 As you have already shown, the eigenvalues of P are \lambda_1 = -1/\sqrt{2}, \lambda_2 = 0, \lambda_3 = 1/\sqrt{2} and \lambda_4 =1. Therefore, we can write P as P = SDS^T where D = \text{diag}(\lambda_1, \lambda_2, \lambda_3, \lambda_4). We also know that P^r = SD^r S^T. Therefore, we have, \begin{align*} \lim_{n \to \infty} M^{(n)} & =... 4 Let c_i be the expected hitting time when starting in state i. We have \begin{align} c_{100} &= 0 \\ c_i &= \frac{1}{2} (c_{i-1} + c_{i+1}) + 1 & 0 < i < 100 \\ c_0 &= c_1 + 1. \end{align} I think you can show that c_i = c_{i+1} + 2i + 1 (for 0 \le i \le 99) by induction, which will then lead you to the answer. 4 Let (X_n) be Markov(\lambda, P), where P is irreducible. Then (X_n) is reversible if, for all N\geq1, the sequence (X_{N-n})_{0\leq n\leq N} is also Markov(\lambda,P). Implicitly this requires that our initial distribution \lambda is invariant for P. The main result is the following: Theorem: Let P be irreducible, and \pi an invariant ... 4 You are correct that \lim_{n\to\infty}\mathbb P_1(X_n=3) is given by the equilibrium probability 1/5. Now observe that for n\geq1, we have that\mathbb P_5(X_n=3)=\frac{\mathbb P_1(X_{n-1}=3)+\mathbb P_4(X_{n-1}=3)+\mathbb P_5(X_{n-1}=3)}{3}$$So$$\lim_{n\to\infty}\mathbb P_5(X_n=3)=\lim_{n\to\infty}\frac{\mathbb P_1(X_n=3)+\mathbb P_4(X_n=3)}{2}=\...

4

If $X_n$ is the event of extinction in exactly generation $n$ then the probability of extinction in generation $3$ is $\mathbb P(X_3)$ but the probability of extinction in generation $3$ given not extinct by generation $2$ (i.e. no extinction in generation $1$ or in generation $2$) is $$\mathbb P(X_3 \mid X_1^c, X_2^c) = \dfrac{\mathbb P(X_3 ,X_1^c, X_2^c)}{\... 4 The period \ d(i)\  of a state \ i\  is not the shortest length of tine it takes to return to the state, but the gcd of all the times it can take to return to the state. In your example, if you start from state 2 you can reach it again after \ 4,6,8,\dots\  steps. That is \ P^n(2,2)>0\  for any \ n\  of the form \ 4+2r\  where \ r\  is ... 4 Maybe a good starting point would be to look at a simple example. The eigenvalues of the transition matrix \begin{bmatrix} \frac{1}{2} & 1 \\ \frac{1}{2} & 0\end{bmatrix} are: 1, with eigenvector \begin{pmatrix} \frac{2}{3} \\ \frac{1}{3} \end{pmatrix} (the principal eigenvalue giving the stationary Markov distribution) -\frac{1}{2}, with ... 4 Hint: ET=\sum P(T>n)=\sum P(X_i \neq Y_i: 1\leq i \leq n). 3 The crucial thing is that Wilmott asks about the chance of making a profit, regardless of how large the profit or loss is. Joshi is asking about expected value of the portfolio. Those are very different questions. If I pay 1 to bet on something and win 10 with probability \frac 15 but can only play once, Wilmott says I should not. I lose 80\% of ... 3 For infinite-state Markov chains, all 12 combinations of (irreducible or not), (aperiodic or not), and (positive recurrent or null recurrent or transient) are possible. There's also the further detail that if you're not irreducible, then different states of the Markov chain can vary in the other properties. Irreducible, but periodic, and transient Consider ... 3 The exact probability that the game has not ended after the \ n^\text{th}\  toss is$$ \frac{\pmatrix{n\\\left\lfloor\frac{n}{2}\right\rfloor}}{2^n}\sim\sqrt{\frac{2}{\pi n}}\ . $$The proof of the first expression turns out to be more straightforward than I had initially expected. The asymptotic approximation follows from the well known asymptotic ... 3 Let me start by clarifying some of your notation. When you say that the transition matrix for N is given by$$ P(N_{t-s} = y - x) = \frac{e^{-\lambda(t-s)} [\lambda (t-s)]^{y-x}}{(y-x)!}, $$this seems to refer to the matrix of transition probabilities p(x,y) = P(N_t = y \, | \, N_s = x) of going to state y at time t, given that we start from state ... 3 There is a uniform distribution on the space of stochastic matrices, because it is a bounded polytope. Sampling from this distribution is also easy. The first observation is that we can sample each row independently (because there are no constraints among elements from different rows). Each row is a probability distribution, therefore it suffices to sample ... 3 The moral of the story seems to be that your process does not converge. Explanation follows. We consider the process as you wrote, with r = 2/3. Let P_i be a random variable that is 2/3 with probability 1/2, and 3/2 with probability 1/2. We are interested in the random variable Z_n = \prod_{i = 1}^n P_i, and we want to figure out how we can get ... 3 Write m for the expected number of games; it is easy to see m is finite. The expected number of games until the first win is 3. From this point, one of three things can happen. You can win the next two games (probability 1/9), finishing in 5 games (in expectation); you can win the next one game (probability 2/9); or you can fail to win the next ... 3 Hint: consider what happens to the z-coordinate during the random walk. It either: increases by 1 (probability 1/6) stays the same (probability 2/3) decreases by 1 (probability 1/6) Showing that the simple symmetric random walk on \Bbb{Z}^3 crosses the xy-plane infinitely often, then, is equivalent to showing that the random walk on \Bbb{... 3 Observe that X_0,X_1,..,X_{n-1} depend only on \xi_1,\xi_2,...,\xi_{n-1}. Hence, P(X_n\leq x|X_0,X_1,..,X_{n-1})=P(\xi_n\leq x-\alpha X_{n-1}|X_{n-1}). By independence of \xi_n and X_{n-1} you can compute this as \Phi (x-\alpha X_{n-1}). 3 Recall from real analysis that$$\sum_{k=1}^{\infty} (1-a)^k = \frac{1-a}{a}\quad \text{for}\quad 0<a\le1.$$Consider the random variable n^{-1} T. We can split its expectation up as follows:$$E[n^{-1}T] = E[n^{-1} T\cdot \mathbf{1}_{\{T\ge n\}}] + E[n^{-1} T\cdot \mathbf{1}_{\{0\le T<n\}}].$$Observe that$$E[n^{-1} T\cdot \mathbf{1}_{\{0\le T< ...

3

Writing it down as a Markov process with all its states and calculating from the leaves of the tree should give you the answer. I have done it for the centrepiece for some intuition. Notice that many states are essentially the same due to symmetry of rotation. Hope it helps.

3

The answer above is entirely correct. Am just here with some simple code to give you confidence that $\mathbb{E}[T] = \frac{135}{13}$

3

Let $k_i=\mathbb E[T\mid X_0=i]$. Then for $n>2$, we have \begin{align} k_n &= 1+\frac{1}{n-1}(k_2+\dots+k_{n-1}) \\ k_{n-1} &= 1+\frac{1}{n-2}(k_2+\dots+k_{n-2}). \end{align} So from the second equation, $k_2+\dots+k_{n-2}=(n-2)(k_{n-1}-1)$. Sticking this into the first, $$k_n=1+\frac{1}{n-1}[(n-1)k_{n-1}-(n-2)]=k_{n-1}+\frac{1}{n-1}.$$ Now with $... 3 Let$\mathbb{E}[T_{100}(n)]$be the expected time to hit$100$starting from$n$Then you have $$\mathbb{E}[T_{100}(100)]=0$$ $$\mathbb{E}[T_{100}(0)]=1+\mathbb{E}[T_{100}(1)]$$ $$\mathbb{E}[T_{100}(n)]=1+\tfrac12 \mathbb{E}[T_{100}(n-1)] + \tfrac12 \mathbb{E}[T_{100}(n+1)]$$ for$0 < n<100$, giving you$101$equations in$101$unknowns. So solve it. ... 3 Foreword. Probably this answer is not what you expect. It aims actually at a more complicated task of computing the probability that the game ends at the$(n+1)$-th batch of trials. Knowing the probability one can of course compute the expected value of any quantity which depends only on the number of played batches. Yet the computation of an expected value ... 3 The notation is a bit confusing (although, it is typical to these settings). Here is the same proof presented differently. First, for$g\in \text{b}\mathcal{E}$, a transition semigroup$(P_t)_{t\ge 0}$, and$s<t$, the Markov property is $$\mathsf{E}_x[g(X_{t})\mid \mathcal{F}_{s}]=\mathsf{E}_{X_s}[g(X_{t-s})]=P_{t-s}g(X_s) \quad(\mathsf{P}_x\text{-a.s.}),... 3 The statement is true, but I think the way it is presented is a mistake by the authors. What is obvious is that$$\pi(z) = \frac{1}{\mathbb{E}_z (\tau_z^+)}.$$Indeed, starting from$z$, the Markov chain visits$z$exactly once (at time$t=0$) before returning to$z$, so$\tilde{\pi} (z) = 1\$. However, the stationary measure we got depends a priori on the ...

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