  We present a nonparametric prior over reversible Markov chains. We use
completely random measures, specifically gamma processes, to construct a
countably infinite graph with weighted edges. By enforcing symmetry to make the
edges undirected we define a prior over random walks on graphs that results in
a reversible Markov chain. The resulting prior over infinite transition
matrices is closely related to the hierarchical Dirichlet process but enforces
reversibility. A reinforcement scheme has recently been proposed with similar
properties, but the de Finetti measure is not well characterised. We take the
alternative approach of explicitly constructing the mixing measure, which
allows more straightforward and efficient inference at the cost of no longer
having a closed form predictive distribution. We use our process to construct a
reversible infinite HMM which we apply to two real datasets, one from
epigenomics and one ion channel recording.
