Jeremy Ting edited p6.tex  about 10 years ago

Commit id: 15a9575dc761a5044ed7b10816229b27f335f7c9

deletions | additions      

       

So $P(\mbox{dot product}=1)=(\frac{1}{2})^n \sum_{i=0}^{\frac{n}{2}} {{n}\choose{2i+1}} = (\frac{1}{2})^n * (2)^{n-1} = \frac{1}{2}$  We have shown that the dot product between x and y results in 1 1/2 the bit value being 1, $\frac{1}{2}$  of the time time,  which means it will result in 0 half 0,  the time which other half. This  proves randomness. \item  $256$ bits under above reasoning