Range of cube-indexed random walk

Research output: Contribution to journalArticlepeer-review

21 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 - 2001

All Science Journal Classification (ASJC) codes

  • Mathematics(all)


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

Cite this