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
15 views

recurrence time for transient state

I have the following transition matrix for a MC with state space $S = \{ 1,2,3,4,5,6,7,8 \}$ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.4 ...
0
votes
0answers
24 views

Markov Chain (DTMC)

What is the expected number of times we need to roll a die until we get three consecutive 6's? I am trying to construct the transition matrix; however, I am not sure how also how to go from here.
3
votes
1answer
33 views

Uniqueness of the solution to a discrete boundary value problem

Given a Markov chain with state space $\Omega$ and transition matrix $P$, and $A\subset \Omega$, define function$f(x)=\Bbb E _x(\tau_A)$, where $\tau_A$ is the "stopping time into set $A$", meaning ...
0
votes
0answers
22 views

A question about the “stopping time with respect to a set” of a Markov chain

Given a Markov chain with state space $\Omega$ and transition matrix $P$, and $A\subset \Omega$, define function$f(x)=\Bbb E _x(\tau_A)$, where $\tau_A$ is the "stopping time with respect to a set", ...
0
votes
0answers
7 views

Deriving upper bound on number of recolorings of 3-colorable graph that 2-coloring won't give any monochromatic triangle

I clearly don't uderstand something in this exercise (because my answers seems to trivial to me). Let G be a 3-colorable graph. Consider the following algorithm for finding such a 2-coloring. ...
1
vote
2answers
28 views

The relation between the discrete Harmonic function and the Harmonic function in PDE

Given a Markov chain with state space $\Omega$ and its transition matrix $P$, a function $h(x):\Omega\to\Bbb R$ is called a harmonic at state $x$ if $h(x)=\sum_{y\in\Omega}P(x,y)h(y)$, and is called ...
2
votes
0answers
47 views

Convergence of empirical average of Markov chain from transient class

I am trying to get an intuition of how to understand the limit of the empirical average $$\frac1n\sum_{i=1}^nX_i\tag{$\ast$}$$ of some Markov chain $(X_n)_n$ with transition matrix $P$ (let's assume ...
0
votes
0answers
10 views

Efficient exploration of the “least important” nodes in a large graph

We call Markov Chain Crawler (MCC) a graph learner that is given query access to a Markov Chain Teacher (MCT) which itself is given a specific Markov Chain. At the beginning, the MCC is given some ...
1
vote
1answer
23 views

How to discretely stochastically simulate a continuous-time Markov chain?

A continuous-time markov chain describes a continuously varying process, such that future state only depends on the current state. A sampling of a continuous markov chain can be described in terms of ...
0
votes
0answers
11 views

Number of transitions in a 2-state markov chain in time t

Suppose I have a 2-state discrete-time Markov chain. Start in some initial state, and take t time steps forward. I want to know, what is the expected number of state switches (e.g. 1 -> 2 or 2 -> 1) ...
0
votes
0answers
26 views

Density function of absorption time in this Markov Chain

Let $X_t$ be a continuous time Markov Chain with state space $\{1,2,3\}$ with the following transition matrix: $$\left( \begin{matrix} -(\lambda+\delta) & \lambda & \delta \\ \mu & ...
0
votes
1answer
20 views

Strange eigenvector of a transition probability matrix

My question is related to the derivation of eigenvectors of a transition probability matrix in Hamilton's ''Time Series Analysis''. I have troubles deriving the same eigenvectors as what the author ...
1
vote
1answer
33 views

Help explain an inequality in a proof about Markov chain first hitting time.

The following is part of my textbook about proving the expectation of Markov chain first hitting time is finite. I understand everything except for the circled inequality $\sum\limits_{t \ge 0} {P\{ ...
0
votes
0answers
32 views

Markov Chains - Random Walk

Let $X_n$ be the distance from his desired path of our drunken man. At each step he is moving right or left with probabilities $p$ and $1− p$. Given that $p\neq 1-p \neq 0.5$ 1)Calculate the ...
2
votes
1answer
55 views

Markov Chain: flip coin 8 times and get 3 consecutive heads

I have confusion while reading the following example in the course material. Q: In a sequence of independent flips of a fair coin, let N denote the number of flips until there is a run of three ...
0
votes
1answer
21 views

Property conditional expectations - System of linear equations

A player throws a coin until he gets three consecutive faces. We are interested in the expected number of pitches thrown by assuming that the piece is balanced and that the throws are independent. To ...
0
votes
1answer
30 views

Find the transition function of the Markov chain (Xm)

I haven't taken a probability/statistics course in years and I'm trying to make my way through an Introduction to Stochastic Processes book. The question reads as follows: Suppose we have two urns ...
0
votes
1answer
53 views

For which values of $p$ is the Markov chain recurrent? ( sort of a RW with two steps forward and one back)

I have a process with indices in $\mathbb{Z}$ with the following transition probabilities: $P(i,i+2)=p$ and $P(i,i-1)=1-p$, with $p\in(0,1)$, i.e. with probability $p$ I take two steps forward and ...
1
vote
1answer
21 views

Markov Chains in a Casino

Consider an agent that enters a casino with an integer amount of money $y$ such that $0 < y \leq 5.$ The agent will stop gambling if the agent has either 0 dollars (in which case, the agent cannot ...
0
votes
2answers
68 views

Markov Chain: flip 8 coins and get 3 consecutive heads

I was reading the material and I am confused at the following example. Q: In a sequence of independent flips of a fair coin, let N denote the number of flips until there is a run of three ...
0
votes
1answer
39 views

Markov Chain: memoryless property?

I have a question about the Markov Chain. We were doing derivation of the Chapman-Kolmogorov Equations, the $n+m$ step state transition probability (please see below): where $P_{i,j}$ is the ...
0
votes
0answers
21 views

What is the transition matrix for the number of machines operating state at the beginning of a day?

A production unit comprises two machines which operate independently of each other. Each machine has a reliability of over $0.9$ a day, which means that the probability to fail during this period is ...
1
vote
0answers
44 views

Eigenvectors of Approximations to Infinite Stochastic Matrices

Given a function $[0,1]\to[0,1]\times[0,1]$ on the reals, such that the function is "stochastic" (probably an abuse of vocabulary: defined such that integrating along any vertical line gives $1$), ...
1
vote
1answer
32 views

A question about markov chain's transition matrix

Suppose $P$ is the transition matrix of some homogeneous finite Markov chain with state space $Ω=\{1,2,…,n\}$, then $P(x,y)$ is the probability that the next state is $y$ if the current state is $x$. ...
0
votes
1answer
21 views

Is a Markovian chain irreducible when one state does not have a recursive path?

Let be the following homogeneous Markovian chain with three state: \begin{pmatrix} 1/2 & 1/4 & 1/4 \\ 2/3 & 0 & 1/3\\ 3/5 & 1/5 & 1/5 \end{pmatrix} Is this ...
0
votes
1answer
36 views

Calculate probability of two different outcomes where history is governed by markov chain

Let the state space, $s_t$, be $\{0,1\}$ and be governed by a Markov chain with probability $\pi(s_0=1) =1$ for the initial state and time-varying transition probabilities $\pi_1(s_1=1|s_0=1)=1$, ...
1
vote
1answer
33 views

Recurrence of a Markov chain (lemma of Pakes)

For my course on Markov chains, we have to think about the following problem: Consider the irreducible Markov chain with $P$ on the state space $S={0,1,2,...}$, with $p_{0,1}=1$, ...
0
votes
0answers
19 views

Reference request for name of matrix similar to transition matrix of Markov chain

If $P$ is the transition matrix of a Markov chain, and $\pi$ is its stationary distribution, define matrices $Q,$ $R$ by the formulae: $$Q_{ij} = \pi_i P_{ij}~.$$ $$R_{ij} = ...
1
vote
1answer
37 views

Modelling probability problems by Markov chains

For one of my courses, we have to think about how we could model certain problems with the help of Markov chains. Most are straight-forward, but I find it difficult to choose the right states and ...
2
votes
1answer
29 views

How to find Kolmogorov Forward Equations, given generator matrix Q?

I am having difficulty in forming Kolmogorov Forward Equations. I understand how the KFE is derived and that $$\frac {d}{ds} p_{ij} (s) = \sum_{k \neq j} p_{ik} (s) \lambda_{k} r_{kj} - p_{ij} ...
3
votes
1answer
59 views

Computational methods for the limiting distribution of a finite ergodic Markov chain

We wish to show what can be discovered about the limit of a finite, homogeneous, ergodic Markov Chain $X_1, X_2, \dots,$ using simple methods of computation and simulation. Specifically, consider the ...
0
votes
0answers
29 views

Markov chain: Find expected value to get back to starting state

I wonder why they complicate this solution? Call the mean time to get from i to j $M_{i,j}$ and set up three simple equations starting with $$M_{0,0} = 1 + (1/3)M_{1,0} + (1/3)M_{2,0}$$ and you ...
1
vote
0answers
54 views

Does a Markov process have memory zero?

I have the following question: The Markov process with two states and a transition matrix $$P =\begin{pmatrix} 0.3 & 0.7 \\ 0.3 & 0.7 \end{pmatrix}$$ has memory zero. Is it true? My ...
1
vote
0answers
26 views

Simple random walk on the $N$-cycle

I am considering the following example: In my lecture notes we noted that "the functions $(\phi_j)_j$ form a basis". I think they refer to the space $\mathbb{C}^G$ where $G$ is the above ...
2
votes
0answers
49 views

distribution of times that a traveller passes by vertex

a traveller is travelling on a map. arriving every vertex of the map, the traveller could choose to go to next vertex according to a constant probability. The probabilities are represented in a matrix ...
24
votes
5answers
2k views

When the product of dice rolls yields a square

Succinct Question: Suppose you roll a fair six-sided die $n$ times. What is the probability that the product of the rolls is a square? Context: I used this as one question in a course for ...
1
vote
0answers
24 views

Quasistationary distribution for the Moran model.

The Moran model is a model for genetic drift. Basically, it is a finite Markov chain (more precise: a birth-death chain) with state space $S:=\{0,...,N\}$ and the following transition probabilites: ...
1
vote
0answers
40 views

Birth and death process. Total time spent in state i.

Question: Let $X(t)$ be a birth-death process with $\lambda_n = \lambda > 0$ and $\mu_n = \mu > 0,$ where $\lambda > \mu$ and $X(0) = 0$. Show that the total time $T_i$ spent in state $i$ is ...
1
vote
0answers
66 views

Show crazy identity with too many sums in it (for numbers $\tau_1,…, \tau_{N-1}$). [closed]

Let $N \geq 2$ be a natural number and $ i \in \{1,\ldots,N-1 \}$. Then we define the number $\tau_i$ via $$ \tau_1 := \frac{1}{N} \sum_{k=1}^{N-1} \sum_{l=1}^k \frac{N^2}{l(N-l)}, $$ $$ \tau_i := ...
2
votes
2answers
38 views

Asymptotic behaviour of mean absorption time at the Moran model

In the Moran model, a model from population genetics, the mean time until absorption is given by $$ \tau _i =N \left( \sum_{j=1}^i \frac{N-i}{N-j} + \sum_{j=i+1}^{N-i} \frac{i}{j} \right),$$ where ...
3
votes
1answer
33 views

Markov Chain with two components

I am trying to understand a question with the following Markov Chain: As can be seen, the chain consists of two components. If I start at state 1, I understand that the steady-state probability of ...
15
votes
2answers
464 views

Knight returning to corner on chessboard — average number of steps

Context: My friend gave me a problem at breakfast some time ago. It is supposed to have an easy, trick-involving solution. I can't figure it out. Problem: Let there be a knight (horse) at a ...
0
votes
0answers
11 views

Log moment generating function from two state transition matrix of markov process

How to find the log moment generating function of two state Markov process where the distribution is gamma distribution. The transition matrix is $$ P=\begin{pmatrix}1-\sigma & \sigma\\ \tau ...
1
vote
0answers
39 views

Gambler's ruin problem - expected time

I have troubles seeing the following. Consider the classical gambler's ruin problem, betting 1 at each time $t\in \mathbb{N}$, and losing or winning -1 respectively +1 at each time till the fortune of ...
0
votes
0answers
21 views

Problem in an example of Introduction to stochastic processes by Lawler page 25

Example. page 25: Consider the two-state Markov chain with $S=\{0,1\}$ and P= $\begin{pmatrix} 1-p & p \\ q & 1-q \\ \end{pmatrix}$ where $0< p,q< 1 $ Asuume the chain starts in ...
1
vote
1answer
17 views

Finite, irreducible Markov chains - Is the mean arrival time at $j$ always finite?

We consider an irreducible Markov chain $(X_0,X_1,...)$ with finite state space $S$ and transition probabilities $p_{ij}$. Then, for $j \in S$, we can define the random variable $$ T_j :=\min{\{ n \in ...
0
votes
0answers
23 views

Confusion in the defition of 'first passage time' (Markov Chains)

Consider a state $i$ from some state space $A$. First passage time to state $i$ is the random variable $T_i$ defined by $T_i(\omega) = inf$ { $n \geq 1: X_n(\omega) = i$ }. Does this means that ...
2
votes
0answers
37 views

Markov chain limit problem

Let $X_n$ be a Markov chain on a countable state space, $\mathbb{S}$. Let $N_n(x) = \sum_{k=1}^n\mathbb{1}_{\{X_k=x\}}$ denote the number of times the chain visits state $x\in \mathbb{S}$. Let ...
0
votes
0answers
9 views

Example of the strong Markov property

Can someone give me an example of strong Markov property? I have been looking Markov chains by J.R. Norris for this and the example given in that book is confusing. If anyone has read that example ...
0
votes
0answers
27 views

Convergence to equilibrium

Hi I have a question about the following proof. By definition then $\mathbb{P}$ should refer to the distribution of $X_n$, so something like $P_\lambda=\mathbb{P}$. What it confuse me a bit is the ...