| Abstrakt: | We consider an $n$-ary random Boolean function $f$ such that $|\{\valpha; f(\valpha) = 1\}| = m$ and every such Boolean function has the same probability. We study its geometric model, the so called interval graph. The interval graph of a random Boolean function was introduced by Sapozhenko and has been used in constructions of schemes for realizing Boolean functions. Using this model, we estimate the number of maximal intervals intersecting a given maximal interval of a random Boolean function and proove that the asymptotic bound of the number is $ n^{(1 + \phi(n)) \log _2 \log _{1/p} n} $, where $p = m / 2^n$ and $\phi(n) \to 0$ as $n \to \infty$.
We also study the equality of this model of random Boolean function with another one, where ${\rm Pr}[f(\valpha) = 1] = p$, for $\valpha \in \{0, 1\}^n$. We find the conditions on $m$ under which are these two probabilistic models equivalent, what means that $m/2^n$ can be consider as a equivalent to $p$.
Finally, we started to study the "structure" of the neighbourhood of the first order for the purposes of estimating the size of neighbourhood of second (or higher) order. We also drop a hint how should be obtained results used in next works on this field.
|
|---|