TIFR CSE 2017 | Part A | Question: 9

Question

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)$?

• A. $3 \alpha$
• B. $\alpha^2$
• C. $6\alpha(1-\alpha)$
• D. $3\alpha^2 (1-\alpha)$
• E. $6\alpha(1-\alpha)+\alpha^2$

Comments

c is the answer

---

$\text{maj(x1,x2,x3)}=1 \,\, \text{iff} x_1+x_2+x_3 \geq 2$

$( x_1+x_2+x_3 =2) + (x_1+x_2+x_3 =2)$

$\text{for} x_1+x_2+x_3 =2, \text{bits will be } (0,1,1) OR (1,0,1) OR (1,1,0)$

$\text{for} x_1+x_2+x_3 =3, \text{bits will be } (1,1,1)$

hence  $P(\alpha)=3 \times \alpha \times \alpha \times (1-\alpha )+ \alpha \times \alpha \times \alpha=3\alpha ^{2}-3 \alpha ^{3}+\alpha^{3}=3 \alpha ^{2}-2 \alpha ^{3}$

 

$\frac{\mathrm{d} }{\mathrm{d} \alpha}(3 \alpha ^{2}-2 \alpha ^{3})=6 \alpha -6 \alpha^{2}=6 \alpha(1-\alpha^{2})$

---

very nicely illustrated in the simplest and minimum words possible.

---

@Anand, Great explaination but slight modification:-

is should be 6α(1−α)

Answer 1

$\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$

Comments

$x_1$	$x_2$	$x_3$	$output$	$Probability(\alpha)$
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1	$(1-\alpha)*\alpha^2$
1	0	0	0
1	0	1	1	$\alpha^2*(1- \alpha)$
1	1	0	1	$\alpha^2*(1- \alpha)$
1	1	1	1	$\alpha^3$

Each variable $x_i$ for i=1,2,3 can be set 1 with probability $\alpha$ and 0 with probability $1-\alpha$

So, I have built all the cases where my output will be 1, hence on that cases I need the value of $p(\alpha)$

So, from above table

$p(\alpha)=3\alpha^2(1-\alpha )+\alpha^3$

$p(\alpha)=3\alpha^2-2\alpha^3$

Derivative of $p(\alpha)=p'(\alpha)=6\alpha-6\alpha^2=6\alpha(1-\alpha)$. Answer is option (C).

Please Note: The above function majority function  also your resembles the function which represents the carry output for a Full adder $(C_{out}=AB+BC+CA)$ will be true when at least 2 of the variables from A,B,C will be true.

---

nice ayush

Answer 2

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) = 3x²-2x³
=>p`(x) =6x-6x² option C