3 votes

Effect of self loops on mixing time?

Your question is essentially covered by Cor 9.5 in [1] which implies that as long as the ratio of self-loops to the original degree is bounded above and below, the mixing time of this modified walk is ...
Yuval Peres's user avatar
3 votes

Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?

Before we try to get into ergodic or whatever else, let's try to understand what phenomenon a mathematician or scientist is trying to (or could be trying to) model with AEP. Well Asymptotic for ...
Pedro Juan Soto's user avatar
3 votes

Difference between CTMC, DTMC, and MDP

The "probabilistic" element in probabilistic model checking is that the system being checked is probabilistic, not that we add probabilities to an existing deterministic or non-deterministic system. ...
Shaull's user avatar
  • 5,636
2 votes

Reconstruction of a sequence generated by a Markov chain - reference request

If the number of gaps is small, you can do the following brute force approach. Try every possible way of filling those gaps (there will be exponentially many possibilities, in the number of the gaps). ...
Aryeh's user avatar
  • 10.5k
2 votes

What automorphisms on a Markov Chain imply a uniform limiting distribution?

This is perhaps a nearly trivial observation, but I couldn't think of another general property just of the automorphisms that would ensure the limiting distribution is uniform. If the automorphism ...
Joshua Grochow's user avatar
1 vote

Approximative counting of matchings in a graph

Both Jerrum and Sinclair have written a lot about this kind of topic over the years, and there are more recent references by them that you can check out. In particular, take a look at [1], it ...
acrendic's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible