Range of cube-indexed random walk

Research output: Contribution to journalArticle

17 Scopus citations


For given finite, connected, bipartite graph G = (V, E) with distinguished v0 ∈ V, set F = {f: V → Z|f(v0) = 0, {x,y} ∈ E ⇒ |f(x) - f(y)| = 1}. Our main result says there is a fixed b so that when G is a Hamming cube ({0, 1}n with the usual adjacency), and f is chosen uniformly from F, the probability that f takes more than 6 values is at most e-Ω(n). This settles in a very strong way a conjecture of I. Benjamini, O. Häggström and E. Mossel [2]. The proof is based on entropy considerations and a new log-concavity result.

Original languageEnglish (US)
Pages (from-to)189-201
Number of pages13
JournalIsrael Journal of Mathematics
StatePublished - Jan 1 2001

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Range of cube-indexed random walk'. Together they form a unique fingerprint.

  • Cite this