deletions | additions       diff --git a/p6.tex b/p6.tex  index 518ff46..0ad5b12 100644  --- a/p6.tex  +++ b/p6.tex 
...
\section{Problem 6}  \begin{itemize}  \item  \em{Consistent}: fix an M We need to show  thatway each time you do  the calculation you will get he same value function family \em{M} is universal as long as the $m$ chosen follows two rules.  \em{Random}: For First, $m$ cannot be all zeroes because if that is allowed, then  the Matrix m which we fix we must make sure every single 8  bit is randomized. So vectors you will get, will  all the 256 spots are randomly chosen. When a vector x is sampled uniformly at random be 0  and multiplied it your numbers will all go  to M we get an the same spot. Next, you have to make sure the rows of the matrix are distinct because if some rows repeat, the corresponding spots in the  8 bit numberthat  will always match up. That means you won't  be uniformly distributed between $(0,255)$. able to have your numbers go to certain spots because it would be impossible to get that number using the $m(y)$ formula.  The reason If $m$ follows  the 8 bit number is uniformly distributed is above rules, it will then be universal  becausethe M matrix was random and we randomly sample the 32 bit vector. Then if we we look at each individual bit of the 8 bit vector  we can analyze why the probability of getting a particular 8 bit number show that it  is $1/256$. consistent and random.  So the first bit is determined by multiplying the first row of M with the vector x and then taking that value mod 2. When we create the random M matrix we need \em{Consistent}: If you fix  the probability of a 0 showing up to be $7/24$ and \em{M},  the probability of 1 to be $17/24$. The reason for this is because 0*0,0*1 and 1*0 get $m(y)$ formula will give  you the same  value0 and only $1*1$ get you 1. So if 1 and 0 have an equal chance of occurring then 0s will show up more likely than 1s. With this new probability distribution  for the 1s and 0s we can be sure that 0s and 1s can show up equally after same number $y$ since  the multiplication. (Clarification: more 1s formula  will be int he M matrix but after the multiplication with vector x never change as along as you keep  the 8 bit number will have an equal distribution of 1s and 0s). Since we are multiplying two 32bit numbers and then taking mod2 we have an equal chance of getting a 0 or 1. same \em{M}.  Then \em{Random}: We need to show that  if you use this reasoning randomly sample a number $x$, it has an equal probability of landing at any of the indices  for the other 7 bits you can see each spot hashing table. Since there are 256 different indices we need to show for any 32 bit number it  has .5 a \frac{1}{256} or \frac{1}{2}^8  chance of being 1 landing at any particular spot.   The hashing function takes s 32 bit number  and .5 chance 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 being 0. 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 means any unique 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 has if there is  a $\frac{1}{2} ^8$ 1/2  chance of occurring being 1 or 0 that means the probability of being any particular number is 1/2^8  which is equal to $1/256$. what we were looking for.  So Now to prove that the dot product of two random 32 bit numbers and then taking mod2 of that number results  in summary for any vector a 1/2 chance of 0 and 1/2 chance of 1.   Let us call the first 32 bit number  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 of being 1 or 0.   The probability that x*y=1 is  the probability that there are an odd number  of it going into any single bucket is $1/256$ 1*1 during the dot product. Since we are only counting the 1*1 we only care about the number of bits in x that are 1. Since all the 0 bits in x will just get you 0 no matter what they value in y is. So let us say that there are a total of n 1 bits 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 probability dot product is 1 or 0. If we look at those n positions in y if an odd number  of $(M*x)mod2$ being equal to any particular them are 1 the dot product will be 1 and if an even  number of them  is $(1/2)^8=1/256$. 1 then the dot product is 0. So Probability(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   =(1/2)^n * summation from (i=0,n) of nC(2i+1)  This shows summation is just the sum of odd index binomial coefficients.     We know that the sum of the binomial coefficients from (0,n)=2^n   We also know  that this hashing function the alternation sum of binomial coefficients from (0,n)=0 (which  is random. summation (i=0,n) of (-1)^i * nCi)   If you subtract the second equation from the first you get   2*summation from (i=0,n) of nC(2i+1)=2^n   which implies that summation from (i=0,n) of nC(2i+1)=2^(n-1)   Which means that the sum of the odd index binomial coefficients is 2^(n-1)   So Probability(dot product=1)=(1/2)^n*sum of odd index binomial coefficients=(1/2)^n*(1/2)^(n-1)=1/2   We have shown that the dot product between x and y results in 1 1/2 of the time which means it will result in 0 half the time which proves randomness.  \item  $256$ bits under above reasoning