New answers tagged

1 vote
Accepted

Expected value of Markov chain after nth steps

$E[X_3] = 0\cdot P(X_3=0) + 1\cdot P(X_3=1) + 2\cdot P(X_3=2)$ Hence $$E[X_3]= \frac14 P^3_{01} + \frac14P^3_{11} + \frac12P^3_{21} + 2\left[ \frac14P^3_{02} +\frac14P^3_{12} + \frac12P^3_{22}\right]$$...
user avatar
2 votes
Accepted

Time reversible Markov chains question

For this chain, the transition probabilities for $j \ne i$ are are $$p_{ij}=q_{ij}\,\frac{b_j}{b_i+b_j}\,.$$ Thus $\pi_i=b_i/Z$ satisfy $$\pi_i p_{ij}=\frac{b_ib_j}{Z(b_i+b_j)}=\pi_j p_{ji}\,,$$ which ...
user avatar
2 votes
Accepted

Question about Markov Chains

First suppose that $p \ne 1/2$, and let $q=1-p$. If the first step is clockwise, then the problem is a gambler's ruin problem, and the chance of success (visiting all nodes) is $$\frac{1-q/p}{1-(q/p)^{...
user avatar
2 votes
Accepted

How long a graph random walk takes to hit every vertex?

The cover time is at most the maximal hitting time multiplied by the harmonic number $1+\ldots+1/n$. This is the Mathews bound, see, e.g., Section 11.2 in [1]. In fact, the cover time can be ...
user avatar
3 votes

Average vs Worst-Case Hitting Time

This is an addendum to the answer by Yuval Filmus. Indeed $\phi(n)=\Theta(n)$, and the upper bound is explained in that answer. I don't understand the argument for the lower bound given there, but a ...
user avatar
0 votes
Accepted

Average and max. hitting time to a specific vertex

The same question was asked at https://mathoverflow.net/questions/426969/average-and-max-hitting-time-to-a-specific-vertex and for convenience, I reproduce the answer I just wrote there. Perhaps one ...
user avatar

Top 50 recent answers are included