New answers tagged markov-chains
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]$$...
- 143
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 ...
- 261
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)^{...
- 261
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 ...
- 261
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 ...
- 261
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 ...
- 261
Top 50 recent answers are included