A tame sequence of transitive Boolean functions

Abstract: Given a sequence of Boolean functions

(f_{n})_{n g e q 1}

,

f_{n} c o l o n {0, 1}^{n} o 0, 1

, and a sequence

(X^{(n)})_{n g e q 1}

of continuous time

p_{n}

-biased random walks

X^{(n)} = (X_{t}^{(n)})_{t g e q 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 g e q 0}

changes its value. In cite{js2006}, the authors conjectured that if

(f_{n})_{n g e q 1}

is non-degenerate, transitive and satisfies

l i m_{n o i n f t y} m a t h b b E [C_{n}] = i n f t y

, then

(C_{n})_{n g e q 1}

is not tight. We give an explicit example of a sequence of Boolean functions which disproves this conjecture.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: A tame sequence of transitive Boolean functions