How should a challenge allow floating point imprecision to be ignored?

Question

I wrote a challenge about sampling a probability distribution: Sample the Pareto Distribution

This probability distribution is defined over the real numbers. However, submissions do not have access to true real numbers, but merely imprecise approximations of real numbers. I wanted to allow submissions using floating point numbers. However, I couldn't find a satisfying way to specify what submissions were allowed.

In particular, many submissions would, very rarely, output Infinity or NaN, due to the fact that their randomly sampled floating point number would ocassionally be 0, and 1/0 would be output.

Likewise, in my challenge specification, I said that the output should be greater than 1 with probability 1, which is part of a natural definition of the distribution over the reals. However, many submissions would output exactly 1 with non-zero probability, again due to the fact that the floats are different from the reals.

What's the best way to say in the challenge that it's OK if submissions don't perfectly sample the true distribution due to floating point imprecision?

In general, how should challenges say that floating point imprecision is allowed?

Some options:

• Say that a submission must be written so that if the floating point type was replaced by a true real-number type, and all appropriate built-ins were likewise adjusted, then the program's output would exactly match the specified distribution.

  • This is unsatisfying because it asks about a hypothetical analysis of the program, which isn't testable.

• Specify exactly how far from the idealized output the submission is allowed to be. For instance, it could say that the difference between the probability of the submission outputting a value in an interval of size 1e-6 must not differ from the true probability mass in that interval by more than 1e-6.

  • This is unsatisfying because it's very technical and puts a heavy burden on the answerer. In addition, it might be very hard to come up with a perfect specification. Finally, this doesn't add much to the quality of the question.

• Just handwave it with something like "The submission shouldn't be very far the ideal distribution."

  • This is unsatisfying because it's not objective, and may lead to disagreements that a specification should make clear.

How should challenges specify that floating-point imprecision is allowed?

Answer 1

Allow solutions to assume input will be within their language's bounds

For example, if a language can't represent 2^-20 (~1.035264923841377504347788194211246) (where ^ is exponentiation) as a floating-point number, with any settings set for the particular solution, then the solution can assume it won't be ever needed to be used. However, the algorithm used must theoretically work for all possible inputs.

Another example would be a division by zero that shouldn't happen because normally the divisor wouldn't be 0 but a float which got rounded to 0 because of bounds, or some digits of a float being rounded because of bounds.

However, if the float is rounded because of your algorithm or such rounding is meant to be done in your language and isn't unintended, then your answer would be invalid, since the rounding would be part of your algorithm.

Answer 2

Specify exactly how far from the idealized output the submission is allowed to be

[In this answer, eps (short for epsilon, or error) will refer to the tolerance, which is a small number, up to OP's decision]

It includes:

• For boundary condition: what have probability less than eps can be treated as not being able to happen.
  • This includes whether it is possible to output 1, to error because 1/0, etc.
• For range: Consider a range [a, b]. The probability that the output lies in this range must have absolute or relative error less than eps for all such ranges, which means - let x be the correct answer, and y be the output, (assume x, y > 0) then (x - y) / max(1, x) < eps.

_{Sorry, I confuses the definition... using min implies absolute and relative error less than eps}

I think

it's very technical and puts a heavy burden on the answerer

is not really a problem, because in most cases it is trivial to write. When in doubt, the answerer or someone else (← SE complains this is not a proper English word?) can prove this without too much problem.

For this particular challenge, it means:

• Whether 1 can be returned, or the program can error, it doesn't matter if the probability is < eps.

By default, I think eps = 10-3 is enough. It allows some algorithm that takes time/memory like
eps-2 or even eps-3 to be testable in reality, and yet still relatively precise.