Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
358 views

MCMC with progressive demollification of delta distributions

Edit: I simplified the example to a canonical case for clarity. Given an integral $\int_{\Omega}{g(\mathbf{x})}$ with a well-posed integrand $g(\mathbf{x})$ defined on some multidimensional space ...
4
votes
1answer
288 views

Combinatorial descriptions of the stationary distribution of a Markov chain

When I say "Markov chain" I think of a directed positively weighted (finite) graph, such that the sum of all edges going out of a vertex equals 1. Also I assume that it is aperiodic and irreducible. ...
14
votes
1answer
597 views

Convexity of spectral radius of Markov operators, Random walks on non-amenable groups

Let $P_1,P_2$ denote stochastic transition matrices on a countable set $I$. Consider $P_1,P_2$ as operators on $\ell^2(I)$ given by multiplication. Question Under which conditions can we show that ...
5
votes
1answer
303 views

Elementary Markov Chain Question

Are any general conditions known on a finite transition nxn matrix that ensure that there exists at least one mth root which is also a transition matrix? It is easy to construct a 3x3 , diagonally ...
1
vote
1answer
87 views

Continuous-time Markov chain to sample Bayesian posterior distribution

Given a Bayesian network and evidence for the values of a subset of the variables, a standard question is to compute the posterior distribution on the remaining variables. The Gibbs sampling technique ...
4
votes
0answers
389 views

The spectrum of a Markov Operator and Invariant Measures

Suppose I have a discrete-time Markov Chain (in an infinite dimensional state space $\Omega$) with Markov operator $P$, a linear operator on the space of bounded measurable functions on $\Omega$. (Or ...
2
votes
1answer
195 views

Stochastic processes having Markov kernels

Let $(\Omega_1, \mathcal{F}_1, P_1)$ and $(\Omega_2, \mathcal{F}_2, P_2)$ be probability spaces and suppose $(X_t)$ and $(Y_t)$ are real-valued stochastic processes defined on the respective spaces. ...
3
votes
1answer
596 views

Difference in probability distributions from two different kernels

Let $(E,\mathscr E)$ be a measurable space and $P,\tilde P$ be two stochastic kernels on that space. I wonder how the induced measures $\mathsf P_x$ and $\tilde{\mathsf P}_x$ differ on the space of ...
1
vote
1answer
203 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
1answer
372 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
1answer
388 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
2answers
418 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}$ ...
8
votes
2answers
619 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
1answer
228 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
1answer
249 views

Connectivity of a graph with fixed number of vertices and edges

Hi, first of all I want to mention, that I'm pretty new to graph-theory. Currently I'm about to write a path search algorithm and I want to take advantage of previous knowledge. So this is the ...
1
vote
1answer
520 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
0answers
162 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
2answers
576 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
5answers
423 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
1answer
316 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
1answer
202 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
1answer
665 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
3answers
690 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
1answer
139 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
2answers
319 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
1answer
296 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
0answers
116 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
1answer
456 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
2answers
462 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 ...
10
votes
4answers
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
2answers
450 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
3answers
482 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
0answers
180 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
1answer
252 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
1answer
427 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
1answer
128 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
2answers
556 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
0answers
333 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
1answer
581 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
0answers
320 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
2answers
527 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
2answers
608 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 $$ ...
1
vote
1answer
400 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
3answers
856 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
1answer
156 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
1answer
506 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
1answer
646 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
2answers
988 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
2answers
817 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
1answer
96 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 ...