deletions | additions       diff --git a/p6.tex b/p6.tex  index 0391132..d526793 100644  --- a/p6.tex  +++ b/p6.tex 
...
\em{Consistent}: If you fix the \em{M}, the $m(y)$ formula will give you the same value for the same number $y$ since the formula will never change as along as you keep the same \em{M}.  \em{Random}: We need to show that if you randomly sample a number $x$, it has an equal probability of landing at any of the indices for the hashing table. Since there are 256 different indices we need to show for any 32 bit number it has a $\frac{1}{256}$ or $(\frac{1}{2})^8$ chance of landing at any particular spot.  The hashing function takes s 32 bit number and transforms it into an 8 bit number and there are 256 different 8 bit numbers. So we just need to show that using the m(y) formula all of the 32 bit numbers are uniformly distributed into the range of 8 bit numbers. The m(y) formula takes a randomly sampled 32 bit vector and then multiplies it to the Matrix M to make this 8 bit number. So each bit of the 8 bit vector is determined by the dot product of two 32 bit vectors and then taking mod2 of that number.   So if we can show that the dot product of two random 32 bit numbers and then taking mod2 of that number results in a 1/2 chance of 0 and 1/2 chance of 1 we can prove randomness. We can prove this because for each spot of the 8 bit number if there is a 1/2 chance of being 1 or 0 that means the probability of being any particular number is 1/2^8 which is what we were looking for.   The hashing function takes a 32 bit number, transforms it into an 8 bit number, and it results in 256 different 8 bit numbers. Now, we just need to show that using the $m(y)$ formula all of the 32 bit numbers are uniformly distributed into the range of 8 bit numbers. The $m(y)$ formula takes a randomly sampled 32 bit vector and then multiplies it to the Matrix M to make this 8 bit number. So each bit of the 8 bit vector is determined by the dot product of two 32 bit vectors and then taking $mod2$ of that number.     So if we can show that the dot product of two random 32 bit numbers and then taking $mod2$ of that number results in a $\frac{1}{2}$ chance of 0, and $\frac{1}{2}$ chance of 1, we can prove randomness. We can prove this because for each spot of the 8 bit number if there is a $\frac{1}{2}$ chance of being 1 or 0, that means the probability of being any particular number is $(\frac{1}{2})^8$, which is what we were looking for.  Now to prove that the dot product of two random 32 bit numbers and then taking mod2 $mod2$  of that number results in a 1/2 $\frac{1}{2}$  chance of 0 and 1/2 $\frac{1}{2}$  chance of 1. Let us call the first 32 bit number x $x$  and we will fix that 32 bit number to be anything except 0. We will show that if you randomly select another 32 bit number (we will call y) you have a 1/2 $\frac{1}{2}$  of being 1 or 0. The probability that x*y=1 $x*y=1$  is the probability that there are an odd number of 1*1 $1*1$  during the dot product. Since we are only counting the 1*1 $1*1$  we only care about the number of bits in x $x$  that are 1. Since all the 0 bits in x $x$  will just get you 0 no matter what they value in y $y$  is. So let us say that there are a total of n 1 $n$  bits with the value 1  in x. 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 y,  if an odd number of them are 1 1,  the dot product will be 1 and if 1. If  an even number of them is 1 then the dot product is 0. So Probability(dot product=1)=Probability(out So:     $Probability(\dot product\=1)=Probability(out  of a total of n spots an odd number of them are 1s). 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   =(1/2)^n * summation from (i=0,n) of nC(2i+1)