11
\$\begingroup\$

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?

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ By "input" you probably meant "all numbers in intermediate steps". \$\endgroup\$ – user202729 Dec 22 '17 at 10:46
  • \$\begingroup\$ @user202729 um... \$\endgroup\$ – Erik the Outgolfer Dec 22 '17 at 10:49
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Is that contradictory? Because then, "everything can be treated as not being able to happen" - it's not always clear what is a boundary condition. \$\endgroup\$ – user202729 Dec 16 '17 at 6:11
  • \$\begingroup\$ In the range example, since x <= 1, the min doesn't make sense. \$\endgroup\$ – isaacg Dec 16 '17 at 6:27
  • \$\begingroup\$ That's by definition of absolute-or-relative-error. I just put it there for completion, and in this case it happens that the probability is always ≤ 1. \$\endgroup\$ – user202729 Dec 16 '17 at 6:28
  • \$\begingroup\$ Thanks, that makes sense. \$\endgroup\$ – isaacg Dec 16 '17 at 6:40
  • \$\begingroup\$ Something like this is what I decided to do. \$\endgroup\$ – isaacg Dec 16 '17 at 6:41
  • \$\begingroup\$ I started writing up a long proposal for accuracy on random distributions sampling from floats, but I realized that it would basically just boil down to this. So, have my upvote, and my thanks for letting me not write a thousand words on the topic :) \$\endgroup\$ – Mego Dec 17 '17 at 6:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .