A tame sequence of transitive Boolean functions

Given a sequence of Boolean functions $(f_n)_{n \geq 1}$, $f_n \colon \{ 0,1 \}^{n} \to \{ 0,1 \}$, and a sequence $(X^{(n)})_{n\geq 1}$ of continuous time $p_n$-biased random walks $X^{(n)} = (X_t^{(n)})_{t \geq 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 \geq 0}$ changes its value. In \cite{js2006}, the authors conjectured that if $(f_n)_{n \geq 1}$ is non-degenerate, transitive and satisfies $\lim_{n \to \infty} \mathbb{E}[C_n] = \infty$, then $(C_n)_{n \geq 1}$ is not tight. We give an explicit example of a sequence of Boolean functions which disproves this conjecture.

No reviews yet.

No comments yet.