×

A tame sequence of transitive Boolean functions. (English) Zbl 1477.60147

Summary: 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 [J. Jonasson and J. E. Steif, Stochastic Processes Appl. 126, No. 10, 2956–2975 (2016; Zbl 1347.60111)], 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.

MSC:

60K99 Special processes
06E30 Boolean functions

Citations:

Zbl 1347.60111

References:

[1] Bourgain, J., Kahn, J., Kalai, G., Katznelson, Y., Linial, N.: The influence of variables in product spaces. Israel J. Math. 77, (1992), 55-64. · Zbl 0771.60002 · doi:10.1007/BF02808010
[2] Benjamini, I., Kalai, G., Schramm, O.: Noise sensitivity of Boolean functions and applications to percolation. Publ. Math. Inst. Hautes Études Sci. 90, (1999), 5-43. · Zbl 0986.60002 · doi:10.1007/BF02698830
[3] Cerbone, G., Ricciardi, L. M., Sacerdote, L.: Mean variance and skewness of the first passage time for the Ornstein-Uhlenbeck process. Cybernet. Syst. 12, (1981), 395-429. · Zbl 0513.60078 · doi:10.1080/01969728108927683
[4] Forsström, M. P.: Denseness of volatile and nonvolatile sequences of functions. Stoch. Proc. Appl. 128, (2018), no. 11, 3880-3896. · Zbl 1409.60112 · doi:10.1016/j.spa.2018.01.001
[5] Galicza, P.: Pivotality versus noise stability for monotone transitive functions. Electron. Commun. Probab. 25, (2020). · Zbl 1434.60042 · doi:10.1214/20-ECP290
[6] Garban, C., Steif, J. E.: Noise sensitivity of Boolean functions and percolation. Cambridge University Press, New York, (2015). · Zbl 1355.06001
[7] Jonasson, J., Steif, J.: Volatility of Boolean functions. Stoch. Proc. Appl. 126, (2006), no. 10, 2956-2975. · Zbl 1347.60111 · doi:10.1016/j.spa.2016.03.008
[8] Karlin, S., Taylor H. M.: A second course in stochastic processes, Academic press, Inc., New York-London, (1981). · Zbl 0469.60001
[9] Luigi M. Ricciardi and Shunsuke Sato: First-Passage-Time Density and Moments of the Ornstein-Uhlenbeck Process. J. Appl. Probab. 25, (1988), no. 1, 43-57. · Zbl 0651.60080 · doi:10.2307/3214232
[10] Mossel, E., O’Donnell, R., Oleszkiewicz, K.: Noise stability of functions with low influences: Invariance and optimality. Ann. Math. 171, (2010), no. 1, 295-341. · Zbl 1201.60031 · doi:10.4007/annals.2010.171.295
[11] O’Donnell, R.: Analysis of Boolean functions, Cambridge University Press, New York, (2014). · Zbl 1336.94096
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.