Jeremy Ting edited p6.tex  about 10 years ago

Commit id: 07f0360078bc009a8afd310d090ad7f83b81b7bc

deletions | additions      

       

Now we look at the n positions in y that line up with the 1s in x because those values will determine if the dot product is 1 or 0. If we look at those n positions in y, if an odd number of them are 1, the dot product will be 1. If an even number of them is 1 then the dot product is 0. So:   $Probability(\dot product\=1)=Probability(out $Probability(\mbox{dot product}=1)=Probability(out  of a total of n spots an odd number of them are 1s)$. Probability(dot product=1)=P(there is one 1 in n bits)+P(there are 3 1s in n bits)+P(there are 5 1s in n bits)+...  Probability(dot product=1)=summation from (i=0,n) of nC(2i+1)*(1/2)^n