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]$$...
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 ...
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)^{...
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 ...
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 ...
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 ...
Top 50 recent answers are included
Related Tags
markov-chains × 72probability-theory × 21
algorithms × 11
graphs × 10
machine-learning × 7
hidden-markov-models × 6
artificial-intelligence × 5
probabilistic-algorithms × 5
optimization × 4
dynamic-programming × 4
model-checking × 4
information-theory × 3
network-flow × 3
matrices × 3
randomness × 3
sampling × 3
reinforcement-learning × 3
random-walks × 3
complexity-theory × 2
automata × 2
reference-request × 2
weighted-graphs × 2
modelling × 2
monte-carlo × 2
time-complexity × 1