Let $\mathcal{F}_n$ be the set of all boolean functions of $n$ variables and let $\xi$ be a random variable with values in the set $\mathcal{F}_n$ with the uniform distribution. We define a new random variable $$\eta = \operatorname{max}\{W_{\alpha}(\xi): \alpha\in V_n\},$$ where $W_{\alpha}(\xi)$ is a Walsh-Hadamard coefficient of $\xi$. I want to determine or maybe estimate the value $$ E\eta. $$ I know that there is literature about random mappings, i.e mappings of the form $f: X\to X$. But in this problem we deal with boolean mappings.
$\begingroup$
$\endgroup$
asked Nov 12, 2016 at 7:16
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Firstly, I think you probably meant to take an absolute value in your maximum, otherwise by complementing the functions you'd get zero expectation, no?
F. Rodier has shown the following in the paper here:
Let $\eta$ be the maximum of $|W_{\alpha}(\xi)|$. Then, for almost all functions $\xi$ (under the uniform choice of the $2^{2^n}$ functions) one has $$ \sqrt{2 \ln 2}- \frac{5 \ln n}{n} \leq \frac{\eta}{2^{n/2}\sqrt{n}} \leq \sqrt{2 \ln 2}+\frac{4 \ln n}{n}. $$ Moreover, as $n\rightarrow \infty$ with $q=2^n$ one has: $$ E(\eta)=\int_{\mathbb{R}} \exp\left(-q\frac{t^2}{2}\right) \,dU(t)+ O\left(\frac{\log^2 q}{q}\right), $$ and an expression for $E(\eta^2)$ is also given.
Where does $U(t)$ come from? A function $u(x)$ is constructed by first defining a monotonous infinitely differentiable real function $\alpha$ on $[0, 1]$ such that $\alpha(0) = 0, \alpha(1) = 1$, and such that all the derivatives of $\alpha$ are zero at $0$ and $1.$ Then function $u$ is constructed, such that $0 \leq u(x) \leq 1$ for every $x \in \mathbb{R}$ and obeying some technical properties. Finally $U(t)$ is the Fourier transform of $u(x)$ (as a tempered distribution).
