128 views

Consider the $majority$ function on three bits, $\textbf{maj}: \{0, 1\}^3 \rightarrow \{0, 1\}$ where $\textbf{maj}(x_1, x_2, x_3)=1$ if and only if $x_1+x_2+x_3 \geq 2$. Let $p(\alpha)$ be the probability that the output is 1 when each input is set to 1 independently with probability $\alpha$. What is $p'(\alpha) = \frac{d}{d\alpha} p (\alpha)$?

1. $3 \alpha$
2. $\alpha^2$
3. $6\alpha(1-\alpha)$
4. $3\alpha^2 (1-\alpha)$
5. $6\alpha(1-\alpha)+\alpha^2$

\begin{align*} &\Rightarrow \left [ \textbf{maj}\left \{ x_i \right \} = 1 \right ] \Leftrightarrow \left ( \left [ \sum_{i=1}^{3}x_i \right ] \geq 2 \right ) \\ &\Rightarrow Prob\left ( \left [ \sum_{i=1}^{3}x_i \right ] \geq 2 \right ) = Prob\left ( \left [ \sum_{i=1}^{3}x_i \right ] = 2 \right ) + \ Prob\left ( \left [ \sum_{i=1}^{3}x_i \right ] = 3 \right )\\ &\Rightarrow Prob\left ( \left [ \sum_{i=1}^{3}x_i \right ] \geq 2 \right ) = \binom{3}{2}*\left \{ \alpha .\alpha .\left ( 1-\alpha \right ) \right \} +\ \alpha ^{3} \\ &\Rightarrow Prob\left ( \left [ \sum_{i=1}^{3}x_i \right ] \geq 2 \right ) = 3.\alpha ^{2}(1-\alpha ) + \ \alpha ^{3} \\ &\Rightarrow Prob\left ( \left [ \sum_{i=1}^{3}x_i \right ] \geq 2 \right ) = 3.\alpha ^2 - 2.\alpha ^3 \\ &\Rightarrow P^{'}\left ( \alpha \right ) = \ \frac{\mathrm{d} }{\mathrm{d} \alpha }\left [ 3.\alpha ^2 - 2.\alpha ^3 \right ] \\ &\Rightarrow P^{'}\left ( \alpha \right ) = 6.\alpha \left ( 1-\alpha \right ) \\ \end{align*}
answered by Veteran (56.9k points) 36 189 500
selected by