A tame sequence of transitive Boolean functions

Abstract

Given a sequence of Boolean functions $(f_n{)}_{n\ge 1}$, $f_n:\{0,1{\}}^n\to \{0,1\}$, and a sequence $(X^{(n)}{)}_{n\ge 1}$ of continuous time $p_n$-biased random walks $X^{(n)}=(X_t^{(n)}{)}_{t\ge 0}$ on $\{0,1{\}}^n$, let $C_n$ be the (random) number of times in $(0,1)$ at which the process $(f_n(X_t){)}_{t\ge 0}$ changes its value. In \cite{js2006}, the authors conjectured that if $(f_n{)}_{n\ge 1}$ is non-degenerate, transitive and satisfies ${\lim }_{n\to \infty }\mathbb{E}[C_n]=\infty$, then $(C_n{)}_{n\ge 1}$ is not tight. We give an explicit example of a sequence of Boolean functions which disproves this conjecture.

arXiv comment7 pages

References in corpus (1)

• Denseness of volatile and nonvolatile sequences of functions