A symmetric entropy bound on the non-reconstruction regime of Markov chains on galton-watson trees.

Külske, Christof; Formentin, Marco

Displaying similar documents to “A symmetric entropy bound on the non-reconstruction regime of Markov chains on galton-watson trees.”

Large deviations of Markov chains indexed by random trees

Amir Dembo, Peter Mörters, Scott Sheffield (2005)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

The combinatorics of evolutionary trees---a survey.

Székely, Laszlo A., Erdős, Péter L., Steel, M.A. (1992)

Séminaire Lotharingien de Combinatoire [electronic only]

Similarity:

Asymptotic evolution of acyclic random mappings.

Evans, Steven Neil, Lidman, Tye (2007)

Electronic Journal of Probability [electronic only]

Similarity:

Relative entropy and waiting times for continuous-time Markov processes.

Chazottes, Jean-René, Giardina, Cristian, Redig, Frank (2006)

Electronic Journal of Probability [electronic only]

Similarity:

Gibbs–non-Gibbs properties for evolving Ising models on trees

Aernout C. D. van Enter, Victor N. Ermolaev, Giulio Iacobelli, Christof Külske (2012)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

In this paper we study homogeneous Gibbs measures on a Cayley tree, subjected to an infinite-temperature Glauber evolution, and consider their (non-)Gibbsian properties. We show that the intermediate Gibbs state (which in zero field is the free-boundary-condition Gibbs state) behaves differently from the plus and the minus state. E.g. at large times, all configurations are bad for the intermediate state, whereas the plus configuration never is bad for the plus state. Moreover, we show...

Mixing time for a random walk on rooted trees.

Fulman, Jason (2009)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Random perturbations of stochastic processes with unbounded variable length memory.

Collet, Pierre, Galves, Antonio, Leonardi, Florencia (2008)

Electronic Journal of Probability [electronic only]

Similarity:

Constructing Binary Huffman Tree

Hiroyuki Okazaki, Yuichi Futa, Yasunari Shidama (2013)

Formalized Mathematics

Similarity:

Huffman coding is one of a most famous entropy encoding methods for lossless data compression [16]. JPEG and ZIP formats employ variants of Huffman encoding as lossless compression algorithms. Huffman coding is a bijective map from source letters into leaves of the Huffman tree constructed by the algorithm. In this article we formalize an algorithm constructing a binary code tree, Huffman tree.

A note on naturally embedded ternary trees.

Kuba, Markus (2011)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Perfect matchings and $k$ -decomposability of increasing trees.

Kuba, Markus, Wagner, Stephan (2006)

Séminaire Lotharingien de Combinatoire [electronic only]

Similarity:

Average convergence rate of the first return time

Geon Choe, Dong Kim (2000)

Colloquium Mathematicae

Similarity:

The convergence rate of the expectation of the logarithm of the first return time $R_{n}$ , after being properly normalized, is investigated for ergodic Markov chains. I. Kontoyiannis showed that for any β > 0 we have $l o g [R_{n} (x) P_{n} (x)] = o (n^{β})$ a.s. for aperiodic cases and A. J. Wyner proved that for any ε >0 we have $- (1 + ε) l o g n \leq l o g [R_{n} (x) P_{n} (x)] \leq l o g l o g n$ eventually, a.s., where $P_{n} (x)$ is the probability of the initial n-block in x. In this paper we prove that $E [l o g R_{(L, S)} - (L - 1) h]$ converges to a constant depending only on the process where $R_{(L, S)}$ is the modified first return...