
Even though this is a combinatorial distribution, the
normalization constant can be computed exactly. We state this well
known fact (e.g., see [1]}) separately because it is crucial
for proving our main result.
[Normalization]
For a \(d\times d\)  matrix \(\) ,

S[d](SS) = (+).


Note that the distribution samples out of a power set of \([d]\) .
While cardinality constrained versions have also been used,
they lack certain properties such as a simple normalization
constant. Even though the subset size of \(()\)  is a random
variable, it is highly concentrated around its mean, and it can also
be easily adjusted by replacing the matrix with a rescaled version
\(\frac{1}{\alpha }\) , where \(\alpha >0\) . This only affects the
distribution of the subset sizes, with the expected size given by the following
lemma [1]}.
[Subset Size]
If \(\hat{S}\sim \left(\frac{1}{\alpha }\right)\) , then
\( [|\hat{S}|] = ((\alpha + )^{-1}).\) 
