# Tag Info

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]$$...
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 ...
Accepted

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)^{...
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 . In fact, the cover time can be ...
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 ...