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
2answers
189 views

Markov Chain Monte Carlo in plain English

I barely know what a markov chain is (I had a terrible teacher) and I probably have an idea of what a stationary distribution is... but I don't know how a Monte Carlo method works and I don't know how ...
2
votes
2answers
289 views

probability terminology for parameter in a Markov process

Suppose $$P(\text{feature present at time} \ t \ \text{and} \ t+\Delta t) = \beta^{2}+\beta(1-\beta) \exp(\Delta t/\tau)$$ where $\tau = 1/(\pi_{01}+\pi_{10})$. What is $\tau$?
0
votes
0answers
21 views

“Simple” proof about expected number of visits

Let $X_n$ be a markov chain with state space $\Omega$. Let $G(x,A)$ denote the expected number of visits to $x \in A$ before exiting a subset $A \subset \Omega$. Prove that for all $x,y$ and A, ...
3
votes
1answer
20 views

non-stationary Markov chain n-step

When I search for the long term behaviour of a stationary markov chain I just multiply the transition matrix with itself for the number of steps: P(n) = P(0)^n. But how do you go about doing it ...
0
votes
0answers
15 views

Book recommendation needed: asymptotic behavior of non-stationary Markov chain

Is there any stochastic process textbook which covers some standard results for non-stationary Markov chain? For my purpose, countable state space is enough. Thanks!
0
votes
1answer
30 views

How to prove that the column sum for a markov matrix is 1?

As is the topic, it is obvious and easy to explain in non-math language but how do I mathematically prove it?
0
votes
0answers
6 views

Efficient random sample from Markov chain with known states at two times

Assume a 2-state Markov chain with known transition matrix. Suppose I know, for example, that the chain is in state 1 at time 1, and is also in state 0 at time 10. I want to sample randomly from the ...
0
votes
2answers
102 views

Does there exist a steady state vector of this Markov Matrix?

Does there exist a steady state vector of Markov Matrix $$P=\begin{bmatrix} \frac{1}{2} & \frac{1}{3}\\ \frac{1}{2} & \frac{2}{3} \end{bmatrix}$$ Initially I was not sure whether to answer ...
1
vote
1answer
20 views

Converting second order Markov chain into a first order Markov chain

I'm having some trouble converting a second order Markov chain into a first order Markov chain, namely I want to define some new random variables $Y_i$, that have the property ...
0
votes
1answer
37 views

Beginner's questions to Hidden Markov Models

I have started reading about Hidden Markov Models, and have some (more or less) minor questions about things I am not sure I understood correctly. I hope asking here is fine: (1) Assumption about the ...
0
votes
0answers
11 views

Finding a One Step Transition Matrix for a Markov Process? (Gambling Application)

I need help finding what a one step transition matrix would look like for the following gambling scenario: Using the bold strategy, say you have a certain amount of money x at any time and you're ...
1
vote
0answers
58 views

How to calculate this integral?

I got confused with this Markov Chain problem: suppose the kernel $Q$ is $Q_x=N(cx,1)$, $c$ is a fixed constant with $|c|<1$ and the stationary distribution is $\pi=N(0,\frac{1}{1-c^2})$. I want ...
1
vote
0answers
40 views

Expected time of reaching 0 of a simple symmetric random walk

Consider the symmetric, simple random walk on $S = \{0, 1, \ldots , k\}$ for $k \in \mathbb N$. Let $$T = \min \{ n \in \mathbb N_0|X_n = 0\}$$ be the first time where the process reaches $0$ and ...
4
votes
1answer
94 views

$P^n$ transition matrix of a Markov chain

The setup: We have an unlimited supply of balls and $k$ boxes. In every step, we randomly (all of them have the same probability) choose a box and put a ball in it. Let $X_n$ be the number of ...
2
votes
1answer
60 views

Show that a Markov Chain is ergodic

Let $Y_n$ be iid random variables with values 1,2,3..n so that $P[Y_i=j]=p_j>0$, where $i\leq1$ and $1\leq j\leq n$. I think I managed to show that $Y_n$ is a Markov chain using the definition, ...
1
vote
1answer
37 views

Stronger version of Markov Chain

I have just started looking into the concept of Markov chains and I was wondering if anyone could help me with this problem. Let $X_1, X_2, ...$ be a Markov chain with the state space $S$. I need ...
0
votes
2answers
29 views

Aperiodicity of Markov chain

If a markov chain which has many states but only one state has a self-loop edge, then does it mean that the markov chain is aperiodic? Or every state in the markov chain has to have self-loop? For ...
0
votes
1answer
86 views

Probability of extinction in branching process

Consider a branching process where the offspring distribution is given by $$P(X = k) = \frac{1}{2^{k+1}}$$ what is the probability that the process becomes extinct at exactly at the nth generation? ...
0
votes
0answers
31 views

Two-state Markov Chains

If I have a two-state Markov chian $V(t)$ with transition probabilities: $P_{00}(t)=(1-\pi) + \pi e^{-\tau t}$ $P_{01}(t)= \pi - \pi e^{-\tau t}$ $P_{10}(t)=(1-\pi) - (1-\pi)e^{-\tau t}$ ...
1
vote
0answers
16 views

Random DFS properties

Have there been any work analyzing some properties of random DFS walks? By that I mean a DFS search, which chooses the next node to visit with uniform probability. i.e, it still refrains from visiting ...
2
votes
1answer
57 views

Random walks : Hitting and recurrence Times relation

I have trouble understanding that how $$E\left[T_0|X_{0} = 0\right] = 1 + E[H_0|X_0=1] $$ where $T_0 = \inf\{n \geq 1:X_n = 0 \}$ and $H_A =\inf\{ n\geq 0: X_n \in A \}$. In other words $T_0$ is the ...
0
votes
0answers
47 views

how to determine transient and recurrent state from transition matrix

I wonder how can I determine the transient and recurrent state from transition matrix ? I mean if I have 10 states It would be very hard to draw diagram for them so how to analyse the matrix? For ...
1
vote
0answers
40 views

Limiting probability of a successful bid

I'm having trouble completing the above question, as my working knowledge of "limiting probabilities" is not very good. For the 1-step transition matrix, I have $$P= \begin{pmatrix} 0.0 & 0.0 ...
0
votes
1answer
78 views

PageRank (power iteration method) convergence rate?

I could not get my head around the idea that the second eigenvalue is the convergence rate. Since the matrix in this application is a Markov matrix (rows/columns sum to one), the largest eigenvalue ...
0
votes
1answer
26 views

Trying to find the markov chain and adjacency matrix of this graph?

This is graph of the problem: Suppose animal x is at node 3 of the graph. It chooses small path labelled s with 2 times probability then long path l. If length is same then probability is same ...
1
vote
1answer
24 views

Period of a Markov Chain: Why is this one aperiodic?

Here is the problem from a stochastic processes book: Consider a Markov Chain on {0,1,2} having transition matrix 0 1 2 0| 0 0 1| 1| 1 0 0| 2|.5 .5 0| ...
1
vote
1answer
1k views

Example of a Markov chain transition matrix that is not diagonalizable?

It is well-known that every detailed-balance Markov chain has a diagonalizable transition matrix. I am looking for an example of a Markov chain whose transition matrix is not diagonalizable. That is: ...
0
votes
0answers
13 views

Computing smoothed state distribution in HMM

Suppose we have an HMM with two states: $s_1$ and $s_2$. The transitional model is as follows: $P(s_1|s_1) = 0.5$, and $P(s1|s2) = 0.25$. There are two observations: $P(a|s_1) = 0.25$ and $P(a|s_2) = ...
1
vote
0answers
26 views

Learning about Markov Chains

I am trying to learn about how to use markov chains for complicated probability problems. I have been looking for different materials to learn these but haven't had much luck. Does anyone have any ...
0
votes
1answer
45 views

Left eigenvector of stochastic matrices with eigenvalue 1

I am only talking about matrices for finite number of states. By the existence of unique equilibrium distribution, this surely means there can only be one of such eigenvector (i.e. the eigenvalue 1 ...
1
vote
1answer
47 views

Question about HMM

I have this HMM model that I need to solve. Unfortunately, my textbook isn't the best and only describes general cases which I have difficulty working with. Consider an HMM with two states: s1 and ...
1
vote
0answers
13 views

Mixing time analysis of time inhomogeneous markov chaons

There are common methods to characterize mixing times of time homogeneous Markov chains through coupling, conductance and strongly stationary times. However, suppose there is a time-inhomogeneous ...
0
votes
1answer
30 views

Markov Chain--starting states

How do we define the starting states in a Markov Chain. For example if we are asked to calculate the transition matrix for different starting states, what does that mean? I am ultimately asked to ...
1
vote
1answer
23 views

Proving irreducibility of Markov chain

I have a Markov chain: state: a permutation of n cards transition: taking the top-most card and randomly choose one of the n possible positions for the card I know it is obviously irreducible ...
2
votes
1answer
36 views

Time sampling an ordinary poisson process

My questions will be given at the end, let me just give some definitions first. The counting process $\{ N(t), t \geq 0 \} $ is said to be a non homogenous Poisson process with intensity function ...
0
votes
0answers
21 views

DTMC: repairing the machine

A machine works for $Y_0$ time then fails and takes $X_1$ time to repair. Then again works for $Y_1$ time and then fails and takes $X_2$ time to repair and so on. All the $X_n$'s and $Y_n$'s ...
0
votes
1answer
21 views

Markov-Chain with general state space - recurrent sets

I have an irreducible Markov Chain $(z_n )_{n\in \mathbb N } $ with state space $X$ and with transition-probability-kernel $K$, so $K(x,\cdot)$ is a probability measure (on the $\sigma$-Algebra ...
1
vote
0answers
27 views

Getting stuck in a loop or the probability of hitting all points in a random walk around a circle.

Suppose you are walking around a circular path made up of $n$ tiles. Each tile $i$ is assigned a distinct value $r_i$ by a random variable uniformly distributed on the set of integers $\{1,...,k\}$ ...
2
votes
1answer
57 views

Random walk : probability of reaching value $i$ without passing by negative value $j$

This is just some question that popped out of nowhere while starting studying random walks, and I don't really know how to approach this. Say I have a random walk that starts at zero, and goes up or ...
0
votes
1answer
32 views

Expected success of trial with conditions

Assume that $n$ people want to achieve a task T. One person can try, and is successful with probability $p$. But when a person try all the other have to do an other trial to have the right to ...
1
vote
0answers
15 views

Dwell times of an absorbing markov chain conditional on reaching specific absorbing state

The fundamental matrix of a discrete time markov chain with absorbing states dictates the expected amount of time spent in each state $j$, given that you started in state $i$. The equation is $$S = ...
1
vote
1answer
39 views

Independence of random variables derived from a Random walk

Let $w=(w_x)_{x \in \mathbb Z}$ be i.i.d random variables taking values in $(0,1)$. Let $(X_n)_{n \in \mathbb{N}_0} (\mathbb{N} \cup {0})$ be a Markov chain (more specifically a simple random walk ...
0
votes
0answers
37 views

Markov chains: Condtitional independence implies independence?

In one proof, I encountered the following reasoning: $$P(T_1=n,T_2=m\mid X_0=j)=P(T_1=n\mid X_0=j)P(T_2=m\mid X_0=j)$$ Where $T$s are waiting times between returns to a state, $X_0$ is the state at ...
0
votes
0answers
15 views

Plot probability density and calculat a probability from a markov transition matrix

Let's say we have a vector $v_0 = (-10, -1, 0.2, 0.3, 0.7, 1, 1.5, 2, 3)$ where the elements are possible values of a portfolio at time $0$ (denoed $C_0$), and let's say we have a transition matrix ...
0
votes
0answers
29 views

Canonical Construction of a Markov Chain: Intuition

Let $P=(p_{xy})_{x,y \in E}$ be a transition probability matrix over a discrete state space $E$ and $\mu_0$ any distribution over $E$. We proved in the lecture that there is a unique ...
3
votes
1answer
64 views

Joint density function Poisson Process

We did an example in class that I'm not sure how we came up with the answer. The problem is: If I let X(t) be a Poisson process of rate $\lambda$. I'm supposed to validate the identity ...
1
vote
2answers
58 views

Expected first return time of Markov Chain

Given the following Markov Chain: $$M = \left( \begin{array}{cccccc} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 \\ \frac{1}{4} & \frac{3}{4} & 0 & 0 & 0 & 0 ...
0
votes
0answers
26 views

Optimal stopping strategy

I try to solve the following problem : Given a series of random variables : X1,X2,... such that each one can get either -1 or 1 with probability 0.5, give a strategy to maximize the expected value of ...
0
votes
1answer
26 views

conditional probability density function

If the joint probability density function for the waiting times $W_1$ and $W_2$ is given by: $f(w_1,w_2)=\lambda^2$ $exp(-\lambda w_2)$ for $0<w_1<w_2$. How would I determine the conditional ...
3
votes
1answer
45 views

Question about random walk markov chain

For a random walk, let $a$ denote the probability that the markov chain will ever return to state $0$ given that it is currently in state $1$. Because the markov chain will always increase by $1$ with ...