Tagged Questions

Stochastic processes (with either discrete or continuous time dependence) on a discrete (finite or countably infinite) state space in which the distribution of the next state depends only on the current state. For Markov processes on continuous state spaces please use (markov-process) instead.

learn more… | top users | synonyms

0
votes
0answers
16 views

Finding the number of non empty urns after 9 steps

I'm trying to understand this example given in the book and am having trouble. The example states. Suppose that balls are successively distributed among 8 urns, with each ball being equally likely to ...
2
votes
0answers
24 views

Verifying the Markov property

We throw a dice infinitely often. Define $U_n$ to be the maximal number shown up to time $n$. How can I verify that $$ ...
0
votes
1answer
13 views

Determining the Likelihoods of Different Game States

Suppose a game is played in which Player 1 must gain two points to win and Player 2 must gain five points to win. Both players start with zero points. In any round, Player 1 has a $1/3$ chance of ...
0
votes
0answers
9 views

Eigen Value -1 of a stochastic matrix

I have to prove that if there is an eigen value of -1, of a stochastic irreducible transition matrix $P$, then the corresponding markov chain has a period which is a multiple of 2. I am approaching ...
3
votes
1answer
32 views

Is it true that $\|\text{diag($\pi$)} P\|_2 \leq 1$ for $P$ stochastic and $\pi P = \pi$.

$\| \cdot \|_2 $ is the matrix norm induced by $L_2$. $P$ is any given real square $n \times n$ non-negative matrix with rows summing to one, i.e. $P1 = 1$, where $1$ is the vector of ones. There is ...
1
vote
2answers
37 views

Characterize stochastic matrices such that max singular value is less or equal one.

By a stochastic matrix, I mean any non-negative square real matrix with rows summing to one. It is well-known that singular values of stochastic matrices can be more than one. Is there a ...
9
votes
2answers
728 views

Expected number of turns for a rook to move to top right-most corner?

Suppose a rook starts on the lower left-most square of a standard $8 \times 8$ chess board. The board contains no other pieces. The rook randomly makes a legal chess move with every turn (directly ...
0
votes
1answer
31 views

A Markov Chain problem concerning a flea moving around a triangle

A Flea moves around the vertices of a triangle in the following manner: Whenever it is at vertex i it moves to its clockwise neighbor vertex with probability $p_i$ and to the counterclockwise neighbor ...
2
votes
0answers
26 views

Layman perspective of mean time spent in transient state of a Markov chain.

Let $X=\{X_n\}$ be a finite state Markov Chain with the state space $\{0,1,2,\ldots,N\}$ such that $0$ is the single absorbing state and all the rest states are transient. The following is the ...
0
votes
0answers
18 views

Markov chain, cut point, hitting times

This question refers to this one: Hitting time $h_i(k)\geqslant h_i(j)\cdot h_j(k)$. The preliminaries are again these: Let $(X_n)_{n\in\mathbb{N}_0}$ be a Markov chain with state space $E$. ...
1
vote
4answers
64 views

Find the expected number of steps needed until every point has been visited at least once.

The complete graph on {1,...,N} is the simple graph with these vertices such that any pair of distinct points is adjacent. Let $X_{n}$ denote the simple random walk on this graph and let T be the ...
0
votes
2answers
55 views

Hitting time $h_i(k)\geqslant h_i(j)\cdot h_j(k)$

Let $(X_n)_{n\in\mathbb{N}_0}$ be a Markov chain with state space $E$. The hitting time of a set $A\subseteq E$ is a RV $$ ...
1
vote
1answer
41 views

Back to square 1…

A friend of mine was telling me about one of the problems, which he described thus: As you can see, the answer to the toy problem presented here is reportedly 13. However, I don't understand how ...
0
votes
0answers
7 views

Show that the closed classes are the maximal elements of the partial order

In the lecture we defined a partial order $\leq$ on the communicating classes associated to a Markov chain. Now it is to show that the maximal elements of the partial order $\leq$ are the ...
1
vote
0answers
10 views

Closed communicating class and stochastic matrix

Let $(X_n)_{n\in\mathbb{N}_0}$ be a Markov chain with state space $E$ and transition matrix $(p_{ij})_{i,j\in E}$. Let $C\subseteq E$ be a closed communicating class. Show that $$ ...
0
votes
1answer
12 views

Why does $(p_{04}^{(n)})_{n\in\mathbb{N}}$ not converge?

Consider a Markov chain with the states 0,1,2,3,4,5,6 and transition matrix $$ P=\begin{pmatrix}\frac{1}{5} & \frac{3}{5}& 0 & 0 & \frac{1}{5} & 0 & 0\\0 & 0 &1 & 0 ...
0
votes
0answers
17 views

Comparing frequencies in stationary distribution

Do there exist theorems for comparing frequencies in the stationary distribution of a (say) aperiodic, positive recurrent Markov chain? i.e. given the transition probability matrix $\mathbf{P}$ with ...
0
votes
1answer
17 views

Transition matrix to graph

Is there a program which can given a transition matrix $P$ draw a graph from a it? The transition matrix is also known as stochastic matrix and probability matrix see ...
1
vote
1answer
29 views

Show that $\mathbb{P}((X_{n+1},…,X_N)\in F|X_n\in A, (X_{n-1},…,X_0)\in G)=\mathbb{P}((X_{n+1,}…,X_N)\in F|X_n\in A)$

In our reading we had the following Theorem concerning Markov chains: Take $0<n<N$ and $(X_n)_{n\in\mathbb{N}}$ a Markov chain. Then for all $a_n\in E$ (where $E$ is the state space) ...
1
vote
1answer
55 views

Which of the following processes are Markov chains?

A dice is thrown an infinite number of times. Which of the following procsses are Markov chains or not? Justify your answer. For those processes that are Markov chains give the transition ...
1
vote
2answers
28 views

What is the expected number of flips that are needed?

Suppose we flip a fair coin repeatedly until we have flipped four consecutive heads. What is the expected number of flips that are needed? The hint is given is as follows: Consider a Markov chain ...
0
votes
0answers
16 views

Markov chains: identifying a nonregular transitional matrix

I am currently TA'ing for a course in which the students are soon to learn about Markov chains and stochastic matrices. During the sections, it refers to the possible existence of a stable state and ...
0
votes
1answer
10 views

How to properly determine observations related to a Hidden Markov Model alike problem?

I got a an exercise problem which should be seen as a HMM scenario and argument some statements. However I'm quite confused about how to properly solve and argument my solutions. Problem tells: ...
0
votes
0answers
30 views

statements of matrix analysis

Let $y$ be fixed value. Let $A=a(x,y)$ be a matrix and $f_{t}(x)=\frac{\sum_{n=0}^{\infty}{a^{(n)}(x,y)(\frac{1}{t})^n}}{\sum_{n=0}^{\infty}a^{(n)}(y,y)(\frac{1}{t})^n}$ Show that ...
0
votes
0answers
13 views

Calculating the hitting probability using the strong markov property

We have the following Markov chain. $X_n=(F_{n-1},F_n)$ where $F_0=0, F_1=1$ and with probability 1/2 $F_{n+1}$ is the difference of $F_{n-1}$ and $F_{n}$ and with probability 1/2 the sum. I have to ...
0
votes
0answers
32 views

general state space markov chain limit problem [on hold]

Suppose that the general state space $\chi$ is partitioned as $S$ and $S^c$ and $P(x, S^c)>0$ for any $x\in S$. How can one show that $P_x(\tau_{S^c}<\infty)=1$? I know how to show it when ...
0
votes
1answer
16 views

Irreducibility of markov chains

Let $A=(a(x,y))_{x,y\in X}$ be a finite irreduzibel nonnegative matrix. Let $b,c >0$, and $\alpha=a^{(b+c)}(x,x)>0$. So $a^{(n(b+c))}(x,x)\ge \alpha^n$. And therefore $\lim ...
1
vote
0answers
19 views

Is there a single matrix norm such that for all stochastic $P$, $\| P \| = 1$?

By a stochastic matrix I mean a square real non-negative matrix with rows summing to one. Denote the set of all such matrices $\mathcal{S}$. By matrix norm I mean a norm in the vector space of ...
0
votes
1answer
37 views

How do we establish the existence of fundamental matrix of a Markov chain?

Let $X=\{X_n\}$ be a finite state Markov Chain with the state space $S = \{0,1,2,...,N\}$ such that $0$ is the single absorbing state and all the rest states are transient. The following is the ...
0
votes
1answer
22 views

How do we compute the mean time spent in transient states of a Markov Chain?

Let $X=\{X_n\}$ be a finite state Markov Chain with the state space $S = \{0,1,2,...,N\}$ such that all the states are transient. The following is the transition matrix. $$ P = \left[\begin{matrix} ...
1
vote
2answers
22 views

Symmetric Random walk on $\mathbb {Z}^d$

Consider the symmetric random walk on $\mathbb{Z}^d $. Symmetric means that the probability of going into any of the $2^d$ directions is $1/2^d$. Starting in 0, what is the probability of ...
0
votes
1answer
20 views

Random walk on $\mathbb{Z}$ (probability to be again in the starting point after n steps)

Consider the random walk on $\mathbb{Z}$, where the probability of going one step to the right from any given state shall be $p\in (0,1)$. Starting in 0, what is the probability of returning ...
0
votes
0answers
9 views

Simulating a continous time, inhomogenous Markov chain

What algorithms are used to simulate a time-continous, inhomogenous Markov chain? For the homogenous case, I've found (among others) this reference, which contains a few exact and approximative ...
1
vote
0answers
18 views

Problem involving periodic Markov Chains — probability of being in a given state at time $n$

I'm working on the following problem: I believe that the simplest possible irreducible periodic Markov Chain would be one with two states and no self-loops? Does this seem correct? However, I'm ...
0
votes
0answers
28 views

Smallest irreducible periodic Markov chain

What would be the smallest periodic Markov chain?
-1
votes
0answers
24 views

Stationary distribution of a birth-death model where a parameter follows a uniform distribution.

I asked this question about some type a markov process I was interested in. @Did offers an answer but I fail to understand how to apply his answer to a concrete example. I am therefore seeking for an ...
0
votes
0answers
17 views

finite state space and geometric ergodicity proof

If the state space of is finite, then all irreducible and aperiodic Markov chains are geometrically ergodic. How can one show this fact?
1
vote
1answer
19 views

Discrete-time random process is Markov iif… (Proving a theorem)

First some background: We say that $(X_n)_{n\geq 0}$ is a Markov chain with initial distribution $\lambda$ and transition matrix $P$ if (i) $X_0$ has distribution $\lambda$; (ii) for $n\geq ...
0
votes
0answers
20 views

Markov chains (which book can be recommended?)

This semester I am learning about Markov chains, mainly including basic definitions & properties Recurrence & Transience Perron-Frobenius Theory equilibrium states convergence to ...
0
votes
1answer
25 views

Why is $1/4$ the probability of hitting 6, starting in 0?

We had the following Markov chain: I cannot see the following statement: Starting in 0, the probability of hitting 6 is $1/4$. I do not see because what does this mean "hitting 6"? In ...
0
votes
0answers
17 views

Why is this class recurrent?

In our reading we had the following example for a Markov chain. I cite from the reading: Here we have three communicating classes: $\left\{0\right\}, \left\{1,2,3\right\}$ and ...
1
vote
0answers
20 views

Random Walk and strong law

I want to prove that a Random Walk in 1 dimension is transient when $p\neq\frac{1}{2}$ but i want to prove it by the strong law of large numbers, so i have this: Define a random variable $$X_i = ...
1
vote
1answer
12 views

Construct the Transition matrix for the Markov chain that models this situation?

I'm given this figure and I need to find transition matrix for this. Thep problem says that the robots have been programmed to traverse the maze and at each junction randomly choose which way to go. ...
0
votes
2answers
35 views

About random walk 1D

I just don't understand why is betha expressed in this way. I don't understand the "conditioning on the initial transition" . Hope you help me thanks
1
vote
0answers
49 views

Can we find a correlation between states of a Markov chain?

I have a fair bit of knowledge on Markov chains but I recently wondered if there is a way to find out a correlation between the states of a finite Markov chain. I could not find any material on this. ...
0
votes
1answer
43 views

A way to check the accuracy of a Markov chain?

I am not sure whether I should post this question on MSE or SSE. I will post it here 1st to see if I can get some feedback. Say I have a finite discrete Markov chain constructed maybe using some data ...
1
vote
0answers
43 views

Linear Filtering Problem (Keynman Fac/Particle Model)

$lienar Filtering Problem $$X_n^1 = X_{n-1}^1 + \epsilon_n *W_n $$ $$X_n^2 = (1-\alpha* \delta) X_{n-1}^2 + \beta*\delta X_n^1 $$ $$X_n^3 = X_{n-1}^3 + \delta*X_n^2$$ above is $$\approx$$ $$dX_n^1 ...
0
votes
1answer
21 views

Ergodic behaviour for bounded random dynamical system

Considering an iterated system described by $$ X_n =\gamma_nX_{n-1} , $$ where $\gamma_i$ are non-negative i.i.d. variables. It is easy to show that the expectation will grow unbounded for $\mathbb ...
0
votes
1answer
40 views

Proofs in Stochastic Processes

Let $$X_{n}$$ be an irreducible Markov chain on the state space {1,...,N}. Show that there exists $$C < \infty$$ and $$\rho < 1$$ such that for any states i,j, $$\mathbb{P} [ X_{m}\neq j , m=0 ...
0
votes
0answers
18 views

Stationary VS. limiting probability

I'm just wondering what the difference between stationary probability and limiting probability is. And, if any of you know: What does it mean that some elements exist and some elements doesn't, when ...