SFM sketch randomized merge results in upward cardinality bias

There is a typo in the mathematical formulas used to determine the probability of flipping a bit during the randomized merge in SfmSketch, which results in too many 1-bits in the sketch. This results in sketches that appear to have more elements than they should (i.e., an upward bias in cardinality).

The bug is present in both Java and Velox. A fix for Velox is available at https://github.com/facebookincubator/velox/pull/18790.

Your Environment

n/a

Expected Behavior

Merging two noisy sketches should result in a sketch that is distributionally equivalent to the sketch of their union, but with higher noise.

Current Behavior

The merged sketch has excessive 1-bits due to a typo in the formula, resulting in upward bias in cardinality estimation that is particularly notable at epsilon <= 1.

Possible Solution

See fix in https://github.com/facebookincubator/velox/pull/18790.

Steps to Reproduce

1. Create two noisy SFM sketches with, e.g., epsilon=1.
2. Merge them together.
3. Estimate cardinality.
4. On average, this will overshoot the true cardinality of the set union.

Screenshots (if appropriate)

n/a

Context

Fixed in Velox: https://github.com/facebookincubator/velox/pull/18790