Ways of specifying random generation in challenges Note: As per consensus on Meta, challenge-writing questions are on topic here.


In light of this "thing to avoid when writing challenges", I started to think about challenges involving random generation of certain kinds of objects.

It sometimes happens that I want to post a code-golf challenge that involves randomly generating a foo, where


it's very easy to check whether a given thing is a foo, and
it's a little harder to quickly generate a "good-quality" random foo.


As an example, a foo might be a binary matrix where there are no segments of 4 equal bits in any direction.
It's easy to check whether a given binary matrix is a foo, but generating a random foo with a nicely spread distribution seems to require a backtracking algorithm or something similar.

Anyway, now I'll need to objectively specify what qualifies as a random foo, and I'd like it to be "unpredictable" in the intuitive sense that when I run the program several times, the results always look different.
The most restrictive approach is to require that the output is uniformly random: all valid foos have the same probability of being generated.
This is usually too restrictive, because I have no idea how to do it save for generating all valid foos, removing duplicates and choosing one, which is boring and slow.

My next idea is to require that all valid foos have a positive probability of being generated.
However, this means that the following approach is valid: generate a random foo-like thing (in our example, a random binary matrix), if it's a foo then return it, otherwise return a hard-coded foo (say, the identity matrix).
This is also somewhat boring, since it's basically just a recognizer of foos tacked to a random matrix generator.

Could there be a nice general definition for an unpredictably random foo?

TL;DR

Is there a good way for specifying an "unpredictable" randomly generated object that doesn't fix the distribution but discourages hard-coding?
Return a thousand different foos

This makes it impossible to return hardcoded values and have a half decent golf. However, a legit foo generator does have a small chance of outputting duplicate foos unless it is actually checking them. To remove the burden of checking, an empirically tested failure rate, say 10%, could be specified as acceptable.

Be aware of the birthday paradox, that the probability of duplicates may be higher than you think. If there are only a million possible foos, a thousand random foos will have a probability of about 0.6 that there is a duplicate in there somewhere, and that's assuming that foo generation is completely uniform. If this could be an issue, require say 900 unique foos for every 1000 generated, which is far more generous for a genuine foo generator but still impractical for hardcoding.

This also allows you to repeatedly generate foo-like things and check fooness until you get foos. I think this is a valid solution myself, but if you don't like it:

Do it quickly

The chances of a completely random foo-like thing being foo are probably quite low, so specifying a time limit is likely to force a genuine attempt at foo generation.

To accomodate the speed differences between different languages, you may want to have different time limits depending on the language like Hackerrank: https://www.hackerrank.com/environment . However if you specify large enough foos the probability of random foo-like things being foo might be really low, so a "before the heat death of the Universe" rule might be sufficient.