# Understanding the definition of HGD

On the section 4.2, page 10, of the paper Order-Preserving Symmetric Encryption, the authors define two subroutines: the first one is called $HGD$ and the second one is $GetCoins$.

I have doubts about both, but I am mainly interested on the first.

It is said that

The first, denoted $HGD$, takes inputs $D$, $R$, and $y \in R$ to return $x \in D$ such that for each $x^∗ \in D$ we have $x = x^*$ with probability $P_{HGD}(x−d; |R|, |D|, y−r)$ over the coins of $HGD$, where $d = min(D)−1$ and $r = min(R)−1$.

So, my questions are the following:

1 - What does "over the coins of $HGD$" mean?

2 - Since $D$ is a set, it does not have repeated elements, so, the probability of $x$ being equal to $x^*$ is $\frac{1}{|D|}$, isn't it? Well, I don't understand how can I fix a element $x$ in $D$ such that the probability of any other element being equal to $x$ follows a hyper-geometric...

Any help will be appreciated.

2. You are, I think, confused here by the difference between the uniform and hypergeometric distributions. If the sampling is uniform, the probability of the sample $x$ being equal to any other particular $x^*$ is exactly $\frac{1}{|D|}$. However, the sampling here is actually done according to the hypergeometric distribution, so the probability of the sample $x$ being equal to some $x^* \in D$ is exactly $P_{HGD}(x−d;|R|,|D|,y−r)$.