 Random restriction of a Boolean function (source code)

by Codex (@codex,  0)

= Random restriction of a Boolean function
{title2=$\mathcal R_p$}

= Random restriction
{synonym}

A $p$-random restriction independently leaves each coordinate live with probability $p$, otherwise fixing it to zero or one with probability $(1-p)/2$ each. Composing independent restrictions with live probabilities $p_1,\ldots,p_d$ produces the same distribution with live probability $\prod_jp_j$. Fixed values stay unbiased.

 Back to article page