No expertise, but wondering if we can start with a discrete cycle (perhaps of prime length, or a power of two) and integer speeds...

@EvanJenkins, agreed -- what I mean to say about $\pi$ and $e$ is that although they (seem to) pass "empirical" tests of randomness, they don't pass "algorithmic" tests of randomness.

Or if perhaps you are not familiar with the field of algorithmic randomness (?), then I think it essentially answers your question. It is hard to tell from your post because you touch on most of the fundamental ideas/motivations of algorithmic randomness, but you don't mention it and you talk about how e.g. $\pi$ is "random", when it is definitely not algorithmically random. Sorry if I misunderstood though.

Can you be more specific in contrasting your "generic" numbers to Martin-Lof random numbers? As I understand it, you simply take the definition of Martin-Lof random and change "measure-0" to "meager". But since we understand a lot about algorithmically random sequences, it would be very helpful to understand more about how your notion differs. (Also where it comes from or where it is defined if you did not come up with the definition?)

Maybe this is already obvious, but you can think of this as repeating an "$n$ balls in $N$ bins" process $k$ times, with each process independent, and asking about the number of bins that are nonempty in all $k$ repetitions. Since the $k$ processes are independent, $\Pr[$a bin is nonempty $\forall k] = \Pr[$a bin is nonempty in an $n,N$ process$]^k$.

I wonder if something is lost by thinking of $d$ as a metric on distributions rather than on random variables. In particular, as defined in the original post, when $i=j$ I think we have $d_{ij} = 0$. The point being that even if $i$ and $j$ have equal distributions, they are not equal as random variables (if they are independent). So it really would be a metric.

I think in CS this would be close to what are called "consensus" problems or algorithms. But I don't know any literature unfortunately. Somewhat related are "influence" models, but there I think the labeling is usually stochastic, e.g. to determine $f_t(u)$, pick a neighbor of $u$ uniformly at random and adopt its current label.

Thanks, looks very helpful -- I'll look into it and the references you mentioned!

For a finite probability space such as your examples, the probabilistic method should always immediately give a naive algorithm: Try all possible outcomes of the random choices, and for each check if the condition is satisfied. Of course, with $n$ bits of randomness this takes time $2^n$, and you'd prefer a $poly(n)$-time algorithm. (This is very similar to PvsNP, since you can think of a nondeterministic machine as one that always guesses the "correct" random choices in order to construct the object on the first try. So we might usually expect the search for better algorithms to be hard.)

It might matter how $f$ is given/represented.

You can think of the $n$-length bitstrings as representing subsets of an $n$-element universe ($x_i=1$ iff $i$ is in the subset). So you equivalently want a collection of subsets of $\{1,\dots,n\}$ with pairwise intersection of size exactly one. Perhaps this has been studied?

Thanks very much! The answer is very nice. I'd like to wait to accept for a while longer to see if others have something to add.