The markov-chains tag has no usage guidance.

**1**

vote

**1**answer

284 views

### One point on $\phi$-irreducibility

Let $P(x,A)$ be a stochastic kernel on a measurable space $(E,\mathcal E)$ and $G = \sum\limits_0^\infty P^n$ be its potential kernel. A $\sigma$-finite measure $\phi$ is called the irreducibility ...

**5**

votes

**1**answer

405 views

### Probability of a set of random vectors over finite field being a spanning set

Suppose I have a set of random vectors $f(a_1, \ldots, a_\ell) := (v_1, \ldots, v_m) \subset F_p^n$, $m \ge n$, given by a matrix valued polynomial function $f$, where the $a_i$'s are independent, ...

**3**

votes

**1**answer

465 views

### stochastic processes conditional on other stochastic processes

Problem: I'm working in reliability field and have seen papers written on the topic like process of failures when systems are functioning under unobservable (or observable) Markov-like environment, ...

**0**

votes

**2**answers

475 views

### Number of transitions of a markov chain in a time interval

Let us consider the homogeneous continuous time Markov chain $(X_t)_{t\ge 0}$ with two states {0,1} and the intensity matrix
$Q=\begin{pmatrix}-\lambda& \lambda\\\ \mu& -\mu\end{pmatrix}$
...

**9**

votes

**2**answers

962 views

### Is this a situation where triple mutual information is always non-negative?

Suppose I have three identically-distributed homogeneous continuous-time discrete state space Markov chains $X_1(t), X_2(t), X_3(t)$, $t\geq 0$. They evolve independently but share a common random ...

**1**

vote

**1**answer

232 views

### Continuous family of Markov chains

Suppose I have a family of countable state-space, discrete-time Markov chains, indexed by a parameter $r \in \mathbb{R}$. The state space is the same for all values of $r$; the transition ...

**1**

vote

**1**answer

623 views

### Ergodicity of a Markov chain

Hi,
I'd appreciate some help on a Markov chain result I'm trying to show. I believe the following is sufficient for a continuous time Markov chain $(X_t)$ with a countable state space to be ergodic:
...

**1**

vote

**0**answers

228 views

### Comparing two Markov chains

I thought that this question is more appropriate for math.stackexchange, where I asked it, but seeing how I got no response, here it goes:
I am interested in the question of the positive recurrence ...

**2**

votes

**2**answers

801 views

### probability distribution of hitting nodes on a finite graph random walk

Consider a finite, undirected, scale-free graph $\{G}$, with uniform edge weights. We define a truncated random walk on $\{G}$ as a random walk that continues for exactly $\{k}$ steps. For an ...

**4**

votes

**5**answers

428 views

### Some questions concerning a random number process

Consider the following Markov process: Start with an integer $N = N_0$. Now repeatedly choose an $N_i$ uniformly at random in the range $[1...N_{i-1}]$ until $N_i = 1$ at which point one terminates ...

**3**

votes

**1**answer

326 views

### Probability-one event for Markov chain

Let $X$ be a Markov chain, with countable state space $I$ and transition probability matrix $P$. $X$ is irreducible, but need not be recurrent. Let $S$ be a fixed subset of $I$.
Define a subset $K$ ...

**1**

vote

**1**answer

217 views

### Product of a transient and a positive recurrent Markov chain

Let $X$ be a transient Markov chain with countable state space $S(X)$. Let $Y$ be a positive recurrent Markov chain with countable state space $S(Y)$. (Time is discrete.)
Let $A \subseteq S(X)$ be ...

**10**

votes

**1**answer

828 views

### Different uses of the word “ergodic”

There appear to be two definitions of the word ergodic.
The dynamical systems definition says that a measure space $(X,\mathit B, \mu)$ and measure preserving transformation $T: X \mapsto X$ is ...

**1**

vote

**3**answers

693 views

### Probability that a certain Markov process has produced a given state

I am looking for advice on the following practical problem. Please keep in mind that this came up in a practical application.
In the context of Markov chains, we have $N$ states, with $N$ very ...

**0**

votes

**1**answer

144 views

### Modification of a Markov process on the real line

Consider a real-valued Markov process $X$ with a transition density $f(x,y)$, i.e.
$$
\mathsf P[X\in A|X_0 = x] = \int\limits_A f(x,y)\,dy.
$$
For this process I want to find
$$
u(x) = \mathsf P[X_n ...

**1**

vote

**2**answers

326 views

### How to determine a specific graph process is Markovian or not ?

Say, here is a min-degree graph process, which starts with G_0 = the complement of K_n. Given G_t, choose a vertex u of minimum degree in G_t u.a.r., then a vertex v not adjacent to u in G_t u.a.r. ...

**1**

vote

**1**answer

303 views

### A bjection between two stochastic processes

Let x(t) be a Markov process. We define the stochastic process y(t) such that :
y(t) = x(f(t))
f : T -> T
T is the parameter set of the process x(t).
If we ...

**1**

vote

**0**answers

119 views

### A M/M/$\infty$ queue of depositors with compound interest

Hello, I'm trying to model a bank's liabilities using a queue. Suppose a bank begins with a cash reserve of $M$. Depositors are a M/M/$\infty$ queue; they arrive with rate $\lambda$ and deposit 1 ...

**12**

votes

**1**answer

484 views

### Random walk origin return monotinicity

Consider a Markov chain on $\mathbb{Z}^d$ with transition kernel $P$ for adjacent vertices (non-diagonal). Essentially this is a $d$ dimensional random walk with the probability of a transition ...

**1**

vote

**2**answers

473 views

### Rate of decay of variance for a tensor product Markov process (100 pt bounty for good answer by 1800 EST Fri)

Let $Q$ be the generator of a well-behaved (not necessarily reversible) Markov process $X$ on $[n] = \{1,\dots,n\}$ and let $Q^\otimes = \sum_{m=1}^N I^{\otimes(m-1)} \otimes Q \otimes ...

**11**

votes

**4**answers

2k views

### What is the cover time of a random walk on a cube?

I can't quite figure this problem yet. There is an ant at one vertex of a cube. The ant goes from one vertex to another by choosing one of the neighboring vertices uniformly at random. What is the ...

**2**

votes

**2**answers

487 views

### Spectral gap of a product of Markov processes

For $m \in [N] \equiv \{1,\dots, N\}$, let $Q^{(m)}$ be the generator of a (well-behaved) continuous-time Markov process on a finite state space $[n_m]$. Write $J \equiv (j_1,\dots,j_N) \in \prod_m ...

**2**

votes

**3**answers

586 views

### Markov random field with continuous index set

Hi
There's Markov random field (MRF) which, by my Wikipedia-based knowledge, is an extension of Markov chain. I'd like to think of it as going from 1D to higher dimensional spaces. Inherent in its ...

**1**

vote

**0**answers

203 views

### Is the variance of an eigenfunction of a finite state space aperiodic irreducible markov chain starting at a single state always non-decreasing?

I am reposting a previous question due to incorrect initial formulation.
Given an ergodic (aperiodic and irreducible) finite state space Markov chain $P$. Let $f$ be an eigenfunction, i.e., $P_t f = ...

**2**

votes

**1**answer

267 views

### is the variance of a test function of a markov chain always increasing?

Edits: Changed function to eigenfunction. I should have stated the problem with more explicit conditions. Anyways I realized the original formulation is not true, even when one starts at a single ...

**1**

vote

**1**answer

457 views

### Markov chain: Obtaining transition matrix from recurrence probabilities

Consider a markov chain with finite space { 0,1,..n} with transition probability matrix whose entries are $P_{ij}$. Let
$f_{ij}^n$ = probability that starting from state $i $ it goes to state $j$ ...

**3**

votes

**1**answer

130 views

### mutual hitting measure between two sets

Given disjoint nonempty subsets $X_1, X_2$ of the state space of a finite irreducible Markov chain, there are unique measures $\mu_1$ on $X_1$ and $\mu_2$ on $X_2$ such that (a) starting from a ...

**1**

vote

**2**answers

626 views

### Borel-Cantelli Lemma on MCs (absorbing states)

hi, I'm sorry if the question is silly, but I couldn't get my head around it for a while now.
In Markov Chains (MC) proving that a state is either recurrent or transient is through Borel-Cantelli ...

**2**

votes

**0**answers

354 views

### How to bound the second largest eigenvalue of a transition matrix of a non-irreducible Markov chain?

I have found several bounds (e.g., Cheeger, Poincare) for the case that the Markov chain is irreducible and reversible, however my Markov chain has one absorbing state. Any bound would be helpful, but ...

**0**

votes

**1**answer

651 views

### Convergence of sets

Let $E$ be a compact subset of $\mathbb{R}^n$. Let the density function $\phi(x,y)$ be Lipschitz continuous and such that
$$
\int\limits_E \phi(x,y)dy=1
$$
for all $x\in E$. Let us consider the ...

**3**

votes

**0**answers

321 views

### maximum variance unfolding

Consider positive weights $\pi_1, \ldots, \pi_n$ (one can suppose that they add up to $1$) and $n-1$ lengths $d_1, \ldots, d_{n-1}$.
Is there an analytical solution to the following problem:
find the ...

**2**

votes

**2**answers

606 views

### Exist closed forms of the distribution of return time in markov chains?

Hi, I am interested in the distribution of return times in simple random walks on finite graphs.
Let $G$ be a connected finite graph with, with two independent random walks. If both random walks ...

**2**

votes

**2**answers

657 views

### Counterexample Markov process

Let $X$ be a homogeneous Markov process in a continuous time with value in the set $E$. Suppose that for some $T>0,x\in E, A\subset E$ we have
$$
P_x[X_t\in A] = 0
$$
for all $t\in [0,T]$ but
$$
...

**2**

votes

**1**answer

434 views

### Reachability for Markov process

Let $X$ be a Markov process (in continuous or discrete time) and define an event
$$
R(T,A) = (\exists t\leq T: X_t \in A).
$$
I have seen in one paper that
$$
\Pr[R(\infty,A)] = \sup\limits_{\tau} ...

**3**

votes

**3**answers

1k views

### Statistics of a simple Markov chain

Imagine a two-state Markov chain which hops between the states $\pm 1$ with probability $p<1/2$, so that the autocorrelation function after $k$ steps is
$\rho_k = (2p-1)^k$
If I take an ...

**2**

votes

**1**answer

159 views

### scalar diffusions are reversible

It is well known that under mild assumptions a scalar diffusion $dX_t = a(X_t) dt + \sigma(X_t) dW_t$ with invariant probability distribution $\pi$ is reversible. This is indeed not true for ...

**8**

votes

**1**answer

567 views

### Bounds on $||P^{k+1} - P^k||$ for $n$ by $n$ stochastic matrix $P$ with trace $n-1$ and integer $k>>n$.

The problem:
We have a $n$-state Markov chain with arbitrary initial distribution and transition matrix $P$ that is arbitrary except that we know that $P$ has trace $n-1$. Of course $P$ is also a ...

**4**

votes

**1**answer

711 views

### A simple problem in markov chains

I'm trying to understand a 1954 paper of Kubo intitled "Note on the stochastic theory of resonance absorption". The specific problem can be stated mathematically as follows: let $X(t)$ be a random ...

**2**

votes

**2**answers

1k views

### Is there MDPs (Markow Decision Process) which have a non deterministic optimal policy ?

I'm working on Markov Decision Process and I have not found yet an example of MDP that has a stochastic (non deterministic) optimal policy. Is there MDPs that have a stochastic optimal policy or is it ...

**6**

votes

**2**answers

863 views

### Expectation of first positive value in random walk

Let $p$ be a parameter in $]0,1[$. Let $(X_k)_{k\geq 0}$ be an independent, identically distributed sequence of random variables, such that each $X_k$ takes values only in
$\lbrace -1, \frac{1-p}{p} ...

**0**

votes

**1**answer

102 views

### how to find a sequence of digits in base b such that each consecutive block of size k appears exactly once?

My question is most precisely stated in the title. As an example, if we consider base 10, and k=4, then I am asking, is it possible to have a sequence of length 10^4 + 3, such that each 4 digit number ...

**1**

vote

**1**answer

2k views

### How to do integration using MCMC?

I want to evaluate $I = \int_V f(\vec{x}) d\vec{x}$. The classical Monte Carlo method is to sample uniformly from within the integration volume $V$, and then compute $I \approx V \frac{1}{N} ...

**8**

votes

**1**answer

388 views

### Potts model simulation

I was wondering what were the state-of-the-art methods to simulate low temperature configurations of Potts-like models that exhibit a discontinuous phase transition. For models with a continuous phase ...

**1**

vote

**2**answers

468 views

### Markov chain convergence problem.

Consider a markov chain matrix P of size n x n (n states).
P is known to be:
1- there are at least two absorbent states. one of them is denoted by null. (thus, we have that P_null,null = 1)
2- For ...

**-2**

votes

**3**answers

745 views

### Convergence of a markov matrix

Consider a markov chain matrix P of size n x n (n states).
P is known to be:
1- Not irreducible (i.e. there exist at least a pair of states i, j such that we cannot go from i to j)
2- Not all ...

**15**

votes

**5**answers

2k views

### Where to publish a paper on the Mafia game?

I wrote a research paper "A mathematical model of the Mafia game" (arXiv:1009.1031 [math.PR]). However, I do not know where to publish it. As an undergraduate studying majorly physics, I have little ...

**1**

vote

**1**answer

341 views

### Lower bound on the convergence rate of a specific Markov chain

I have a Markov chain $\mathbf{A} = (A_0, A_1, \ldots)$ with state space $\{0, \ldots, n\}$ which converges towards a stationary distribution $\pi$. There are a lot of well-known results on ...

**3**

votes

**1**answer

406 views

### (Stochastic) matrix for which a stochastic matrix logarithm exists?

I think this is basically the inverse question of Matrices whose exponential is stochastic.
i.e. what are sufficient conditions on the matrix representation of an evolution operator of a (finite) ...

**13**

votes

**0**answers

704 views

### representation theoretic interpretation of Jack polynomials

Monomial symmetric polynomials on $n$ variables $x_1, \ldots x_n$ form a natural basis of the space $\mathcal{S}_n$ of symmetric polynomials on $n$ variables and are defined by additive symmetrization ...

**13**

votes

**0**answers

722 views

### Diagonalizing some matrices arising from Fourier transform on $S_n$.

Consider the function $f$ on $S_n$ which equals $1/n$ on all adjacent transpositions $(i,i+1)$, where we let $n+1 = 1$, and $0$ otherwise, and its Fourier transform $\hat{f}(\rho)$ evaluated at the ...