The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
0answers
32 views

Basic Definition and Notations in RWRE [on hold]

From the definition of Zeitouni's lecture notes on RWRE: $(V, E)$ is a special graph, and $N_v:= \{k \in V: (v,k) \in E\}$ is the neighborhood of $v \in V$. $\Omega = \prod_{v \in V} M_1(N_v)$ ...
0
votes
1answer
80 views

Exact formula for computing n-step transition probability of random walks with self-transitions

Consider a semi-infinite random walks $X_n$, $n=0,1,2,\ldots$, whose state space is a set of consecutive integers and whose one-step transition probabilities are $P_{ij}=\mathrm{Pr}\{X_{n+1}=j|X_n=i\}$...
-1
votes
0answers
13 views

Markov Chain: Number of communicating classes of a power of the irreducible transition matrix [closed]

Suppose $P$ is an irreducible transition matrix, with period $d$. Consider the transition matrix $P_k$. In terms of $d$ and $k$, how many communicating classes does $P_k$ have, and what is the period ...
0
votes
0answers
72 views

Looking for an exposition of a certain theorem of Talagrand

The following is a theorem by Talagrand (as stated here, http://arxiv.org/pdf/1511.08609v1.pdf), Let $(X, \mu)$ be a probability space. Let $F : X \rightarrow \{0,1\}$ be a family of functions ...
1
vote
1answer
58 views

Uniqueness of invariant measure for equivalent transition probabilities

Suppose $P(x,dy)$ and $Q(x,dy)$ are two Markov transition kernels on a topological space $E$ equipped with Borel $\sigma$-algebra $\mathcal B(E)$. Suppose for every $x \in E$, $P(x,\cdot)$ and $Q(x, \...
0
votes
0answers
23 views

Dependency of the error term on the states, in the definition of the transition rates of a continuous time Markov chain

I think this is certainly not a research or graduate level question. But I didn't get any answer from math.stackexchange.com. I'm studying G.F.Lawler's stochastic process book. There he defines the ...
1
vote
2answers
61 views

How can I efficiently approximate the stationary distribution of an infinite CTMC with a sparse rate matrix?

I am looking for methods to approximate the stationary distribution of an infinite CTMC with a sparse rate matrix. Each row and column of the rate matrix has a finite number of non-zero elements. ...
4
votes
3answers
365 views

Why does the overhand shuffle converge to the uniform distribution on $S_n$?

Pemantle 1989 proves, among other things, that the Markov chain on $S_n$ induced by repeatedly and independently performing an overhand shuffle on a deck of $n$ cards is ergodic and has limiting ...
2
votes
0answers
126 views

markov processes and ergodic theory

For an ergodic Markov Chain $$ \frac{1}{N}\sum_{i=1}^n f(X_i) \rightarrow E_\pi[f] $$ where $\pi$ is the invariant distribution. I am also dealing with a Markovian process (a state space model to ...
3
votes
2answers
163 views

The necessary sufficient condition for recurrence of a Markovian random walk

Suppose $\sigma_{1},\sigma_{2},...$are i.i.d random variables.$S_{0}=0$. Define $S_{n}=S_{0}+\sum_{i=1}^{n}\sigma_{i}$, then ${S_{n}}$ is a Markovian random walk. I want to figure out the necessary ...
-1
votes
1answer
39 views

Discrete time hidden markov process [closed]

I am dealing with a hidden Markov model for variable $X_{t+1}$ where $X_{t+1}$ = $\alpha_{t}$$X_{t}$ + $(1-\alpha_{t})$$Z_{t}$ $X_{t}$ is an indicator variable indicating wether an individual is ...
1
vote
1answer
125 views

Neat definition of Harris Ergodicity

I can't find any reference where the definition of Harris Ergodicity for Continuous time Markov processes is defined. a) What would be exactly the definition? b) What reference could be helpful? ...
6
votes
1answer
321 views

Does every (generalized?) Markov chain admit transition probabilities?

To pose the question let us start by recalling the following notions: Transition Probabilities. A transition probability matrix between two measurable spaces $(S,\mathcal{S})$ and $(V,\mathcal{V})$...
1
vote
1answer
60 views

Is there an easy way to convert a non-deterministic optimal policy to a deterministic optimal policy for a given MDP?

For a MDP (Markov Decision Process) is there an easy way to convert a non-deterministic optimal policy into a deterministic optimal policy? The trivial way will take $O(|\mathcal{A}|^{|\mathcal{S}|}$...
2
votes
0answers
152 views

Must rows of a transition matrix be distinct?

Is it true that for all continuous time Markov processes on a countable state space $S$, we have all rows of the transition matrix $\mathbf{P}_t$ are distinct for all time $t\in[0,\infty)$ ? This ...
4
votes
0answers
66 views

Most visited vertex in a random walk with place dependent drift

Consider the following Markov chain on $\mathbb{Z}$: $$ P(x,x+1)=1-P(x,x-1)=\frac{1}{2}+e^{-|x|}\cdot \mathbf{1}_{\{x\neq 0\}} $$ Do there exist constants $c,C>0$ such that $$ c\cdot P^t(z,z) \...
1
vote
1answer
60 views

Choose uniformly from fixed-length paths in $[0,n]\cap\mathbb{Z}$ with fixed start and end

Let $X_k$ be a symmetric (discrete time) random walk on $\mathbb{Z}$ and let $m,n\in\mathbb{N}$. I want to chose uniformly from the paths of $X_k$, which start at $0$ stay in $[0,n]\cap\mathbb{Z}$ ...
0
votes
0answers
30 views

Sufficient moment conditions to make $E[\sup_n |X_n|]< \infty$ for Markov process $X_n$

Is there any Markov process $X_n$ for which we can impose sufficient moment condition which will imply $E[\sup_n |X_n|]< \infty$
0
votes
0answers
34 views

Strong Markov vector-valued process from component strong Markov process and independence

I want to prove that if $X$ and $Y$ are (continuous time) independent strong markov $\mathbb{R}$-valued processes w.r.t. their natural filtrations $\mathcal{F}^X_t$ and $\mathcal{F}^Y_t$, that the ...
1
vote
0answers
46 views

Expected number of forward jumps to reach a given quantile of a rv [closed]

I'm a noob in randomized algorithm and ran into a problem(definitely not home work. I'm doing a self study out of my interest with help of my friends. I'm pursuing research career in a machine ...
0
votes
1answer
30 views

Does an infinite chain of a.s. eventual transitions between states necessarily implies a.s transitions along the whole chain?

Given a Markov process among a (possibly infinite) set of states $S$, with possibly infinite depth (that is, the transition probabilities from $s_i \to s_j$ at time $t$ are permitted to depend not ...
2
votes
1answer
101 views

Random Walk 2D with dependent weights [closed]

I have spent a lot of time trying to solve this problem but have had no luck so far! Any help would be highly appreciated! Suppose I have a 3x3 grid as shown below. (3,1) (3,2) (3,3) (2,1) (2,2) (...
0
votes
0answers
57 views

Maximal inequality for Markov process

For a Markov process $\{X_n\}$ is there any inequality available for $$ E[\sup_{0 \leq n \leq k} X_{n}]$$ in terms of moments of $E[X_n], 0 \leq n \leq k$
0
votes
0answers
19 views

Can MDPs over functions be solved?

I understand that dynamic programs are difficult to be solved in general. However I have an MDP, for which intuitively I have a solution, I am curious to know if there is a formal approach to get a ...
-2
votes
1answer
33 views

how to resolve the infinite nesting of interactive POMDP

I am reading papers about I-POMDP. I cant understand the finitely nested I-POMDPs given in these papers. The belief update of the algorithm has a problem that agents' belief updates mutually depend ...
1
vote
0answers
86 views

Markov Chains and Simple Machine Learning [closed]

Suppose I have a large training set consisting of many strings of symbols. $TS = \{Str_0, Str_1, ..., Str_n\}$ $Str_i = \{Sym_0 ... Sym_{len}\}$ These strings of symbols are each generated by the ...
1
vote
0answers
23 views

Properties of a map regarding the space of invariant probability measures for controlled Markov process

Let us consider a controlled Markov process with the transition kernel $p(dy|x,\theta)$ ($\theta$ being the control parameter. Now, consider the map $\theta \to I(\theta)$ where $I(\theta)$ is the ...
0
votes
0answers
30 views

Markov Modulated Markov Chain

Consider a discrete time Markov chain $X_t$ on some finite state space $\mathcal{S}$ with transition matrix $P$. Now consider a process $Y_t$ also on $\mathcal{S}$, which conditioned on $X_{t}=s$ ...
2
votes
1answer
79 views

Eigenvectors of a perturbed reducible stochastic matrix

Let $Q$ be a $n\times n$ reducible stochastic matrix. Let $J$ be such that $[J]_{ij}={1 \over n}$. Now for a small positive constant $\alpha\in [0,1]$, consider the matrix $$\tilde{Q}\,=\,(1-\alpha)Q+\...
0
votes
0answers
56 views

Circular process ergodic?

Let us define a continuous-time Markov process on a circle consisting of $m-$ equally spaced points, i.e. every point has two neighbours. Now, we define a space of functions $S:= \{-1,1\}^{\{1,...,m\}...
0
votes
1answer
163 views

Mixing time of lazy random walk on the directed cycle $C_n$

Briefly: A hint (if this is easy), reference or derivation would be of great help. The question Let $C_n$ be the directed cycle with loops in each of its $n$ vertices, and consider the random walk ...
1
vote
0answers
17 views

Bounding Hidden Markov model Bayesian filter error with inexact models

In context of a hidden Markov model, I am interested in bounding the error of a Bayesian filter when using inexact state transition and observation models. Consider a hidden Markov model (HMM) with ...
0
votes
0answers
48 views

Regularity of the entrance measure of SRW

Let $S(n)$ be the discrete sphere of radius $n$ (i.e., the internal boundary of the Euclidean discrete ball $B(n)$) centered in the origin, and consider a simple random walk starting at some $x\in\...
0
votes
0answers
66 views

Order statistic of Markov chain sample path and related probabilities

Consider a 1D sample path, denoted as $\{X(1), ..., X(t), ..., X(n)\}$, generated from a discrete time finite state (time homogeneous) Markov chain over states $\{1,...,m\}$, with transition ...
1
vote
0answers
37 views

steady state of a continuous-time birth-death process

we consider a continuous-time birth-death process $\{X(t),t\geq 0\}$ with discrete state space taking non0negative integer values $\{0,1,2,3,...\}$. The transition rates of the process $\{X(t)\}$ are ...
3
votes
1answer
95 views

Similarity transformation of transition matrix of reversible Markov chain (reference request)

If $P$ is the transition matrix of a reversible Markov chain, and $\pi$ is its stationary distribution, and let $R$ be defined by: $$R_{ij} = \sqrt{\frac{\pi_i}{\pi_j}}P_{ij}~.$$ By reversibility, ...
2
votes
0answers
44 views

Spectral gap of two step Markov chain

Suppose $X_1,X_2,\ldots$ is a reversible Markov chain with state space of size $k$ and absolute spectral gap $\gamma_*.$ What is the spectral gap of the (non-reversible) Markov chain $Y_1,Y_2,\ldots,$ ...
0
votes
0answers
32 views

steady state distribution for a jump Markov chain

Consider a queueing process with the following transition matrix: $\mathbf{P}=\left( \begin{smallmatrix} 1-\lambda & \lambda & & & & & & &\\ \mu & 1-\...
0
votes
1answer
87 views

Finite hitting time implies hits at any finite time?

I was wondering about the following problem: Assume we have a state space $S:=\mathbb{Z}$ and a Markov chain, such that we can go from any state $x$ to some state $y$ with positive probabilities, i.e....
0
votes
0answers
26 views

steady state distribution of the following infinite-state Markov chain

Given the following state transition equation: $P_0(n+1)=P_0(n)(1-\lambda \Delta t)+ P_1(n)\mu \Delta t$ $P_j(n+1)=P_{j}(n)(1-\lambda \Delta t-\mu \Delta t)+\lambda \Delta t P_{j-1}(n)+ \mu \Delta t(...
0
votes
1answer
111 views

Markov chain with Feller property

Does anybody know whether there is an analysis of when the monotone decreasing chain has the Feller-property? The monotone decreasing is defined as a chain on $\mathbb{N}$ and the rate of going down $...
0
votes
0answers
192 views

Calculate the KL divergence between two transition matrices

I want to calculate how different two markov transition matrices are. For example: $\begin{pmatrix} .2 & .8 \\ .1 & .9 \end{pmatrix}$ and $\begin{pmatrix} .3 & .7 \\ .1 & .9 \...
3
votes
0answers
39 views

Memorylessness of residence times for a Markov process

I'm stuck on the trivial problem of showing memorylessness of holding (residence) times for a continuous time homogeneous Markov chain on finite state space. I have a homogeneous Markov process $x(t),...
8
votes
1answer
154 views

Equalizing Geometric means of Graph Cycles

Consider a strongly connected directed graph $G$. I have been stuck on the following question: can you assign real numbers in $[0,1]$ to each edge of $G$ so that the geometric mean of all cycles are ...
0
votes
0answers
47 views

positive Harris recurrent, aperiodic, stationary Markov chain

How to proof that every positive Harris recurrent, aperiodic, stationary Markov chain is alpha-mixing (strong-mixing)?
1
vote
1answer
131 views

Two types of random walkers on square lattice

Consider a two dimensional square lattice ($n$ by $n$), which is our space $S$ (each point labelled by an index $1\to n^2$), containing two types of particles, distinguished here by either an index $1$...
3
votes
1answer
106 views

Markov-semigroup sobolev inequality

I have a question about the following definition: A probability measure $\mu$, such that the Markov semi-group $e^{Lt} \in L(L^2)$ exists and is symmetric, satisfies the Sobolev inequality iff for ...
3
votes
1answer
95 views

How much larger than the relaxation time can the mixing time be?

The notation is mostly taken from the book "Markov chains and mixing times" by Levin, Peres, and Wilmer. Consider an irreducible, aperiodic, time-reversible, discrete-time Markov chain on a finite ...
1
vote
1answer
69 views

General Markov Chains on same Probability Space?

A Markov chain $(X_i)_{i\in \mathbb{N}}$ on a measurable space $(E,\Sigma)$ is (see e.g. Revuz or Meyn/Tweedie) constructed on the following probabilty space. $$ \Omega = \{ (x_l)_{l \in \mathbb{N}} \...
0
votes
0answers
38 views

Validating a probability density distribution forecast model for a Markov process

Let's say we have a Markov process $X_t$, and we come up with a forecast model that takes some information from outside world and says: "value $X_{t+1}$ has probability density distribution $P_t(x)$". ...