this is for holding javascript data
Jeremy Ting added p6.tex
about 10 years ago
Commit id: 4a9e649bd87b223593463d752f91b0fcaa28168f
deletions | additions
diff --git a/p6.tex b/p6.tex
new file mode 100644
index 0000000..ea50e8e
--- /dev/null
+++ b/p6.tex
...
\section{Problem 6}
\begin{itemize}
\item
\em{Consistent}: fix an M that way each time you do the calculation you will get he same value
Random: For the Matrix m which we fix we must make sure every single bit is randomized. So all the 256 spots are randomly chosen. When a vector x is sampled uniformly at random and multiplied it to M we get an 8 bit number that will be uniformly distributed between (0,255).
The reason the 8 bit number is uniformly distributed is because the 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 is 1/256.
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 the probability of a 0 showing up to be 7/24 and the probability of 1 to be 17/24. The reason for this is because 0*0,0*1 and 1*0 get you the value 0 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 the multiplication. (Clarification: more 1s will be int he M matrix but after the multiplication with vector x 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.
Then if you use this reasoning for the other 7 bits you can see each spot has .5 chance of being 1 and .5 chance of being 0. So that means any unique 8 bit number has a (1/2)^8 chance of occurring which is equal to 1/256.
So in summary for any vector x the probability of it going into any single bucket is 1/256 because the probability of (M*x)mod2 being equal to any particular number is (1/2)^8=1/256.
This shows that this hashing function is random.
\end{itemize}
