pr.probability - How is a permutation taken as an equivalent of a hash function in MinWise independent permutations?

A permutation is the equivalent of an unbiased "good" hash function because it has even distribution. Since a permutation maps (1,2,...,n) $to$ permuted-list-of(1,2,..., n), if the original set $A$ is an unbiased random selection of the range $1$ to $n$, then the likelihood that the $B$="permutation-hash" of $A$ will contain the minimum-value of $1$ to $n$ is the size of the set $A$ divided by $n$.

If the hash function is equitable and well-distributed, then the range of input values will be "hashed" into and map into the output range in an evenly distributed fashion. If the domain is a group of 256 characters, and the hash is a function which outputs 8 characters, then you want the domain to be partitioned into as closely-equal-sized subsets based on the what the hash of the domain words are.

A hash normally reduces the size of the object being hashed, thus because of the pigeonhole priniciple, at least one element of the range of the hash must map to more than one item in the domain. An equitable hash attempts to minimize the variance in the size of the bins which the domain is partitioned into. An inequitable hash leads to some of the bins being very different in size from the other bins. Thus a hash is usually a one-way mapping: given the hash of a message, it is not possible to determine what the original message consisted of, even though it may be possible to deduce what partition the message is part of (the partition whose hash digest is ...)

For example, the hash function EVEN-ODD, equivalently called REMAINDER-MODULO-2, is easily calculated by looking at the last (lowermost) bit of the message. If the range is a subset of $mathbb{Z}$, e.g. the numbers $1...n$, then EVEN-ODD is an equitable hash, as the size of the partitions will differ by at most $1$.

A permutation is equivalent to performing a hash which does not reduce the size of the domain as it maps into the range, it performs a bijection. As such, the size of each partition is $1$, the variance of the sizes of the partitions is $0$, and these partitions are as equitably sized as possible.