Questions tagged [markov-chains]

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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
17 views

Markov umbrellas

"I have $4$ umbrellas randomly distributed between my house and my office. Each day I go from my house to the office and back. If it's raining, i will take an umbrella in my way to the other ...
user avatar
  • 135
0 votes
0 answers
10 views

Cover time of lollipop graphs

A lollipop graph is a graph with a complete graph $K_{n/2}$ connected to a path on $\frac{n}{2}$ vertices, like a shape of a lollipop. Let $u$ be the point where the complete graph and the path meets, ...
user avatar
0 votes
0 answers
16 views

Proof of Chapman-Kolmogorov equations for the general case

I've started studying Markov Chains, but I'm fairly new to the topic and I don't follow some of the reasonings done in the books I'm reading, especially those related with integral manipulation, For ...
user avatar
  • 2,395
1 vote
0 answers
18 views

Finding stationary distribution of random process

Suppose we are given $x_t, \bar{x_t}, t\in \mathbb{Z_+}$ independent 2-states $\{0, 1\}$ Markov chains with positive transition probabilities. Initial states are $x_0 = 0; \bar{x}_0 = 1$. For which ...
user avatar
0 votes
0 answers
14 views

Properties of Continuous Time Markov Chains

In school, I only learned about about "Discrete Time Markov Chains" - in Discrete Time Markov Chains, transitions can only happen at fixed time points. For example, suppose there are three ...
user avatar
0 votes
0 answers
14 views

Deriving Transition Probabilities of a Markov Process

I was reading this article about Markov Processes (https://www.jstatsoft.org/article/view/v066i06) and saw the following equation (4): I am trying to understand why equation (4) is true. I can ...
user avatar
1 vote
0 answers
18 views

Trouble understanding identity $\mathcal{L}(X_n) = \lambda P^n$ in Nummelin's Markov Chains

I've recently started studying Markov chains and I've started reading Nummelin's General Irreducible Markov Chains and non-negative operators. I don't follow the following reasoning made in page 5. ...
user avatar
  • 2,395
1 vote
0 answers
6 views

Can we construct an equivalent markov process with newer states, some of which are combination of previous states?

Let there be a continuous time Markov chain with three possible states $C_1, C_2, C_3$, and the rate of going from configuration $C_i$ to $C_j$ be $r_{ij}$. A very simple markov chain could be such ...
user avatar
1 vote
0 answers
24 views

Best way to estimate probability of heads of a biased coin

What is the best way of estimating the probability p of getting heads in a biased coin? An intuitive idea is to flip it over an over again, and look at the empirical frequency etc, MLE type ...
user avatar
0 votes
1 answer
21 views

Perron-Frobenius theorem for reducible non-negative matrices

Let $M$ be a non-negative matrix ($M_{ij}\geq 0$ for all $i,j$). If $M$ is irreducible, then we know that there exists an eigenvalue $\lambda$ of $M$ that equals the spectral radius $\rho(M)$ and has ...
user avatar
  • 1,041
0 votes
1 answer
25 views

The expectation of event occurrence (two-state model in CTMC)

Below problem is excerpted from Stochastic Processes (2e, Ross). The solution for 5.12(b) can be found here. 5.12 Suppose that the “state” of the system can be modeled as a two-state continuous-time ...
user avatar
  • 41
0 votes
0 answers
21 views

IID hitting times of a subset in simple random walks

Let $X_n$ be a simple random walk on $\mathbb{Z}^d$. Due to the strong Markov property (it is even true for Markov chains) we have that the hitting times $\tau_0 = 0$, $$\tau = \tau_1 = \{ t > 0: ...
user avatar
0 votes
0 answers
10 views

Why does converting the Chordal Markov network to Bayesian network need the concept of clique tree?

In the book Probabilistic Graphical Models Principles and Techniques, Page141 mentioned Theorem 4.13 as: Theorem 4.13: H is a chordal Markov network, then there is a Bayesian network G such that I(G)=...
user avatar
0 votes
0 answers
15 views

Two independent spatial Poisson processes are almost surely disjoint

I want to show that if A, B are independent spatial Poisson processes on R^d with mean measures that have finite densities with respect to Lebesgue measure, then their intersection is almost surely ...
user avatar
2 votes
1 answer
46 views

A statement about finite Markov chains

The following quantity $\tilde\pi$ is defined in the textbook Markov chains and mixing times by David A. Levin. Here $\tau_z^+ = \min \left\{t\geq 1| X_t = z\right\}$. Let $z \in \mathcal{X}$ be an ...
user avatar
1 vote
0 answers
19 views

Computing transition probabilities in continuous time Markov chain

How do we compute the transition probabilities in a continuous time Markov chain? Supposing $h$ is sufficiently small then how would I compute $p_{i,j}(h)$, I am aware of the relation to the generator ...
user avatar
2 votes
1 answer
54 views

Markov Chains—Transition Matrix with λ proof

I was reading "Linear Algebra: A Modern Introduction: Poole, David". This is theorem 4.31 on page 325. Theorem 4.31 Let $P$ be an $n\times n$ transition matrix with eigenvalue $\lambda$. (a) ...
user avatar
0 votes
2 answers
72 views

Proof that markov chain equilibrium using Farkas' lemma

Given a transition matrix for markov chain $ P \in \mathbb R^{dxd} $ such that $$ P_{i,j} \geq 0,\quad 1 \leq (i,j) \leq d, \quad \sum_{j=1 \in d }P_{i,j} $$ and $i=1,....,d$. Let $ x_{0}$ be ...
user avatar
0 votes
0 answers
53 views

Changing Ehrenfest model stationary distribution

The stationary distribution of the Ehrenfest model is bin$(N, 1/2)$. Given a number $0<p<1$, $p\neq 1/2$, modify the Ehrenfest model suitably so that the new Markov chain has a stationary ...
user avatar
  • 319
1 vote
0 answers
32 views

Computing $E(X_n | X_n \geq 0)$, where $X_n$ is an asymmetric lazy random walk on $\mathbb{Z}$

Suppose $X_n$ is a ''lazy'' asymmetric random walk such that, at each step, $X_{n+1} = X_n + 1$ with probability $\alpha$, $X_{n+1} = X_n - 1$ with probability $\beta$, and $X_{n+1} = X_n$ with ...
user avatar
  • 1,492
1 vote
0 answers
25 views

Doubt in Example 4.3.4 of Brémaud's Markov Chains book

I'm reading Brémaud's Markov Chains, Gibbs Fields, Monte Carlo Simulation and Queues 2nd edition and I'm not following example 4.3.4 in page 159. Here's what's in it: Let $A$ be a square matrix of ...
user avatar
  • 2,395
1 vote
2 answers
50 views

Write probability of first return time in terms of first hitting time

For a time homogeneous Markov chain $(X_n)_{n\ge 0}$ with state space $I$ with no self loop . Given $X_0 = i \in I$ , define the first return time $T_i = \inf\{n\ge 1 : X_n = i\} $ and first hitting ...
user avatar
  • 335
0 votes
0 answers
8 views

Are branching processes infinite state space markov processes?

Is it correct to view a branching process as an infinite state space markov process, with the states being the total population which can be 0,1,2,...?
user avatar
0 votes
0 answers
28 views

In a simple Birth and Death Process, how to calculate probability of being at state $i$ at time $n+1?$ [closed]

In a simple Birth and Death Process, the Birth and Death rates satisfy $b_i = ib$ for $i = 1,...,N-1$, where $b_i$ is Birth Probability of being in state $i$, and $d_i = id$ for $i = 1,...,N$ and $0$ ...
user avatar
  • 1
0 votes
2 answers
88 views

The win rate of three player rotation battle

Three players $A,B,C$ are playing a game. Players play against each other in round, the order of battle is $$AB \to BC \to CA \to AB \to \cdots$$ Players need to win two consecutive rounds to win the ...
user avatar
  • 863
0 votes
0 answers
49 views

Ehrenfest urn model - expected hitting time

Consider the Ehrenfest urn model with $N$ identical balls divided in two urns $A$ and $B$. At each step, pick a ball at random and switch its urn. I need to compute $E_{N-1}(\tau_N) $ which is the ...
user avatar
  • 319
1 vote
1 answer
28 views

$M/M/2/3$ Queuing Theory Word-Problem

A service center consists of two servers, each working at an exponential rate of two services per hour. If customers arrive at a Poisson rate of three per hour, then, assuming a system capacity of at ...
user avatar
  • 11
0 votes
1 answer
46 views

Probability of a two-state continuous Markov chain

Consider a continuous-time Markov process ($\epsilon_t$) which takes two values ($\epsilon_t=0$ or $\epsilon_t=1$). Let $p_0$ denote the probability of switching from state 1 to 0 and let $p_1$ denote ...
user avatar
  • 627
0 votes
0 answers
45 views

Probability and expected time a symmetric random walk hits the graph of $f(x) = x$

Suppose we have a simple symmetric random walk $X_n$ where $X_0 = i > 0$. Say we define the time $T=$ $\{n\geq0 |X_n=n\}$, i.e $T$ is the first time that the time index of $X_n$ equals $X_n$. I ...
user avatar
1 vote
1 answer
23 views

How can I find the average output of my Markov Chain based random number generator?

I have a Markov Chain based random number generator which I've modeled here. It works by going along 5 points starting at the 1st point, each has a 25% chance to forward, a 25% chance to go backward, ...
user avatar
  • 11
0 votes
0 answers
21 views

Is this a time-homogeneous Markov Chain?

Let $Z_0,Z_1,Z_2,...$ be i.i.d. random variables,taking values $+1$ and $-1$ each with probability $1/2$. Let $S_n=\sum_{i=0}^n Z_i$(where we take $S_0=0$).Let $X_n=\sum_{j=0}^n S_j$. say whether or ...
user avatar
  • 1
-1 votes
1 answer
31 views

Multivariate Probability? Or markov chain? [closed]

[the equation][1] My friend recently gave me this image, i thought it was a simple multivariate equations, until i realize that it was not. I tried to look it up online, then stumble upon markov ...
user avatar
1 vote
1 answer
93 views

Conditional probability for path calculation in a markov chain model

This question extends a previous question I asked with respect to the markov chain model. I post another question here since I'm trying to follow the Stack Exchange's guidelines. So, based on the ...
user avatar
0 votes
1 answer
36 views

Transitional probabilities in a markov chain model

Just for the sake of providing some context, I'm dealing with the following: Alice's smartphone plan includes a voicemail service with a maximum storage capacity of two voice messages. On a daily ...
user avatar
0 votes
0 answers
16 views

Markov Chain Expected value of first Hitting Time

i am struggling with this task: Let X be a Markov chain on {0,1,..,N} with $\mathbb{P}$($X_k$ = n |$X_{k-1}$ = m) = $\frac{1}{N-m}$, if n > m (0 else). I have to compute $E_0(T_N)$ (the mean of the ...
user avatar
  • 1
0 votes
0 answers
32 views

Is it a Markov Chain? If yes, find its transition matrix

I'm doing some exercises on Markov Chains. Let $S_n$ be the simple walk of $\mathbb{Z}$, then are the following processes Markov chains? and if yes find its transition Matrix: $(S_n + n)_{n \geq 1}$ ...
user avatar
  • 337
0 votes
2 answers
20 views

Generalising $P^n$ for nth time-step of markov chain

We have the following state-space $S = \{0,1,2,3\} $ with transition matrix:$$ P = \begin{pmatrix}\frac{1}{2} & \frac{1}{2} & 0 & 0 \\ \frac{1}{2}&\frac{1}{2}&0&0 \\ 0 &...
user avatar
1 vote
0 answers
38 views

Expected time in markov mouse problem

Here is the problem A mouse trap is placed in room 1 of the house with the pictured floor plan. Each time the mouse comes into room 1, he is trapped with probability p = 0.1. If he is not trapped, he ...
user avatar
1 vote
1 answer
20 views

How to reorder matrix to its canonical form (Markov chain)?

Is it possible to rearrange this matrix in its canonical form (link below)? I have searched numerous websites and videos and have only found answers for small matrices where you automatically get the ...
user avatar
4 votes
2 answers
108 views

Best strategy to reach $500 for a gambling situation in a casino

Suppose a gambler has \$100 to start with. Each time he/she has 0.4 chances of winning and 0.6 chances of losing a bet. If he/she wins he gets twice the money he put in and loses what he bet if he ...
user avatar
  • 477
1 vote
1 answer
32 views

Durrett's Probability: Example 5.5.14 (M/G/1 queue)

I am reading over the stationary distribution section Durrett's textbook Probability: Theory and Example, and I got stuck by a statement in an example he gave about the M/G/1 queue. Here's the problem:...
user avatar
  • 511
0 votes
0 answers
13 views

Markov chain converges to the same steady state for different initial probability vectors.

I was asked to write a code to simulate the following Markov chain, and find the PMF of the random variable $X$: The code I've written for simulating the given Markov chain: ...
user avatar
0 votes
1 answer
11 views

Is Little's Law applicable to all Continous Time Markov Chain Models?

I was reading about Little's Law which is in general(infinite capacity system) form L = R*W ( R: throughput rate ,W : expected waiting time of a customer). I know it is applicable on M/M/S type ...
user avatar
0 votes
1 answer
39 views

Monte Carlo computation of probability of a subset of samples

I would like to compute the probability for some subset $\omega \subset \Omega$ of events to occur, i.e. $P(\omega) = \sum_{x \in \omega} P(x)$ where I know $P(x)$ for all $x \in \Omega$, which are ...
user avatar
  • 175
0 votes
0 answers
23 views

Infinite-countable state space Markov Chain

I tried to review a few posts related to the infinite-countable state space Markov chain and its stationary distribution. However, I could not solve the problem myself. It relates to my previous post ...
user avatar
1 vote
0 answers
23 views

Another condition for determining recurrent & transient states of Markov chain (Norris exercise 1.5.3)

Overview : Below problem reinforces Norris theorem 1.5.3 for time homogeneous discrete time markov chain $(X_n)_{n\ge 0}$ with state space $I$ The following dichotomy holds: (i) if $P(T_i= \inf\{n\...
user avatar
  • 335
0 votes
0 answers
38 views

Exponential convergence of a Markov chain

We are learning about the exponential convergence of a Markov chain. We learned that if a Markov chain(represented by the transition matrix $P$) is a-periodic, irreducible and reversible then it ...
user avatar
  • 319
0 votes
0 answers
26 views

In a Markov chain is an absorbing state considered an irreducible set of one element?

A closed set $C$ is irreducible if $x$ leads to $y$ for all states $x$ and $y$ in $C$. Would you consider a set of a singular absorbing state irreducible. Note that this is mostly a question of ...
user avatar
0 votes
1 answer
99 views

Continuous-time Markov chains: system with components in parallel and enough repairmen. How to calculate availability?

I am trying to solve a continuous-time Markov chain exercise. But I have been stuck for a few days and I don't know how to continue or even If what I have done is correct. Consider a system having ...
user avatar
1 vote
0 answers
34 views

Finding recurrent and transient states with first hitting probabilities (Norris exercise 1.5.1)

I want to see why the following attempt won't work . Problem : In a discrete time markov chain (DTMC) $(X_n)_{n\ge 0}$ with transition matrix P and state space I , which states are recurrent and ...
user avatar
  • 335

1
2 3 4 5
106