Pairwise independence
30 Apr 2018
The subject of this post is to understand the role pairwise independence plays in applications. We all, in our introductory probability courses, have come across this concept and have dished out routine exercises which make us apply its definition: \(Pr(A\cap B)=Pr(A).Pr(B)\) or \(Pr(A|B) = Pr(A)\). Besides trying it out in a few psets and worksheets, the real question to wonder is where such an object can really be used. What application, which we can understand, would make use of this seemingly abstract property. We give it a shot in this post.
The big picture is the following -- we want to design a function which can shrink a domain. That is, given a domain of size \(n\), we want a function to produce values in a co-domain of size much less than \(n\). We also additionally want the function to possess collision-resistance. By collision-resistance, we mean that the function evaluating to the same point for two different inputs happens with as low a probability as your design/creativity can permit. How do we go about doing this? In literature, this pertains to designing hash functions. We will see how the property of pairwise independence helps in this.
Designing a hash function.
The objective here is to design a function, say, \(h(x)\), which when given an \(n\)-length bit vector (called string hereon). We assume we're operating in the binary world of strings - it helps with the analysis. We want \(h(.)\) to map it to a string of length \(m,\text{ such that }m < n \).
to be continued..
The big picture is the following -- we want to design a function which can shrink a domain. That is, given a domain of size \(n\), we want a function to produce values in a co-domain of size much less than \(n\). We also additionally want the function to possess collision-resistance. By collision-resistance, we mean that the function evaluating to the same point for two different inputs happens with as low a probability as your design/creativity can permit. How do we go about doing this? In literature, this pertains to designing hash functions. We will see how the property of pairwise independence helps in this.
Designing a hash function.
The objective here is to design a function, say, \(h(x)\), which when given an \(n\)-length bit vector (called string hereon). We assume we're operating in the binary world of strings - it helps with the analysis. We want \(h(.)\) to map it to a string of length \(m,\text{ such that }m < n \).
to be continued..