It is not that $h(S_1)=h(S_2)$ is true; in fact $h(S_1)=a$ and $h(S_2)=c$, as explained in the example at pag. 80, where $h$ is the minhash function associated to the permutation $\{abcde\}\mapsto \{beadc\}$ and $S_1$ resp. $S_2$ are given in figure 3.3. What is true is that the probability of having $h(S_1)=h(S_2)$, for generic $S_1$ and $S_2$ obtained by permutations and minhash, is equal to
$$\frac{x}{x+y} $$
which is also the Jaccardi similarity of the 2 column sets. This is the meaning of the paragraph in the OP. To show this, the author imagines to move from the top of the column sets and uses the definitions of $X$, $Y$ and $Z$ classes of entries for both $S_1$ and $S_2$.
Let us discuss the statement " the probability of having $h(S_1)=h(S_2)$, for generic $S_1$ and $S_2$ obtained by permutations and minhash, is equal to $\frac{x}{x+y} $". In order to compute $h(S_1)$ and $h(S_2)$ for any two column sets $S_1$ and $S_2$, we need to identify the position(=row number) of the first $1$, starting from top of the column vectors for both $S_1$ and $S_2$: this is the definition of the minhash function $h(\cdot)$. To simplify the discussion the author introduces three classes of rows in $S_1$ and $S_2$: $X$, $Y$ and $Z$. The classes containing the 1's are $X$ (the element 1 is contained in the given row both for $S_1$ and $S_2$) and $Y$ (the element 1 appears in the given row in $S_1$ or in $S_2$).
Moving from top to down along both $S_1$ and $S_2$ we skip all rows of class $Z$: they contain no 1; we stop the search if we meet a row of class $X$ or class $Y$. We distinguish two cases:
case 1: we meet a row of class $X$: as the element 1 appears in both $S_1$ and $S_2$ in the given row, we can compute $h(S_1)$ and $h(S_2)$; they are equal, i.e. $h(S_1)=h(S_2)$ as the row under examination is the same. The question is: which is the probability of meeting an $X$ row before than an $Y$ row while moving from top to bottom along $S_1$ and $S_2$? This probability is $\frac{x}{x+y}$: you should convince yourself of it by doing some explicit example. An idea would be to write down a simple cases, like
$S_1 = (1,0,1)$ and $S_2 = (0,1,1)$. For the given permutation (leading to the $S_1$ and $S_2$ given above) $x=1$ and $y=2$. In fact, there exists $1/3\sim 33.33%$ of probability of having the unique row of class $X$, i.e. $(1,1)$ in front of the 2 rows of class $Y$ $(0,1)$ and $(1,0)$. Remember that $S_1$ and $S_2$ are subsets whose representation as vectors with 1-0 is given up to permutation.
case 2. we meet a row of class $Y$: as the element 1 appears in either $S_1$ or $S_2$ in the given row, then we can compute either $h(S_1)$ or $h(S_2)$; their values cannot be equal by construction of the class $Y$.
For the configuration shown below
$$
\begin{array}{c|c|lcr}
\text{} & S_1 & S_2\\
\hline
1 & 0 & 0\\
2 & 0& 1\\
3 & 1 & 1
\end{array}
$$
the Jaccard similarity of $S_1,S_2$ is $1/2$.
Start with the identity permutation and permute cyclically. Thus, let permutations $p_1,p_2,p_3$ be such that
\begin{align*}
&p_1(S_1) = [0,0,1]&p_1(S_2) = [0,1,1]\\[6pt]
&p_2(S_1) = [0,1,0]&p_2(S_2) = [1,1,0]\\[6pt]
&p_3(S_1) = [1,0,0]&p_3(S_2) = [1,0,1]
\end{align*}
and let $h_1,h_2,h_3$ be the corresonding hash functions. Then
\begin{align*}
&h_1(S_1) = h(p_1(S_1)) = h([0,0,1]) = 3\\
&h_1(S_2) = h(p_1(S_2)) = h([0,1,1]) = 2
\end{align*}
\begin{align*}
&h_2(S_1) = h(p_2(S_1)) = h([0,1,0]) = 2\\
&h_2(S_2) = h(p_2(S_2)) = h([1,1,0]) = 1
\end{align*}
\begin{align*}
&h_3(S_1) = h(p_3(S_1)) = h([1,0,0]) = 1\\
&h_3(S_2) = h(p_3(S_2)) = h([1,1,0]) = 1
\end{align*}
so $S_1,S_2$ have the same hash value for permutation $p_3$, but not for permutations $p_1,p_2$.
Thus, the average number of hash matches for the $3$ cyclic permutations
is $1/3$, not $1/2$.
Best Answer
It seems like it is an underlying assumption in this formula that different elements map to distinct hashes. Otherwise, just have your hash function map everyone to 0. The probability you are looking at would be 1 regardless of any sets.