edited by
1,336 views
15 votes
15 votes

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$
edited by

2 Answers

Best answer
14 votes
14 votes
$\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*}$

Correct Answer: $C$
edited by
3 votes
3 votes

000 : Result = 0    |    Given that output should be 1
001 : Result = 0    | Therefore consider only values result 1 and calc probability
010 : Result = 0    |---------------------------------------------------------------------------
011 : Result = 1    | (1-x) * x * x   +
100 : Result = 0    |
101 : Result = 1    |  x * (1-x) * x  +
110 : Result = 1    |  x * x *(1-x)   +
111 : Result = 1    |  x * x * x

=>p(x) = 3x2-2x3
=>p`(x) =6x-6x2 option C

Answer:

Related questions

25 votes
25 votes
7 answers
2
Arjun asked Oct 19, 2015
2,869 views
Three dice are rolled independently. What is the probability that the highest and the lowest value differ by $4$? $\left(\dfrac{1}{3}\right)$ $\left(\dfrac{1}{6}\righ...
12 votes
12 votes
6 answers
4
go_editor asked Dec 23, 2016
2,245 views
Which of the following regular expressions correctly accepts the set of all $0/1$-strings with an even (possibly zero) number of $1$s?$(10^*10^*)^*$$(0^*10^*1)^*$$0^*1(10...