7
$\begingroup$

I have an ordered set $S = \langle S_1, S_2, .., S_M \rangle$ from which I want to draw a sample of $N$ elements in such a way that the sample is non-strictly totally ordered (as with $\leq$ and the integers), and all the possible occur with equal probability. The sample must be taken with repetition.

For example, let's say $S = \langle 1, 2, 3, 4 \rangle$ and $N=3$, the samples: $[1, 1, 1]$, $[1,2,3]$, $[2,3,3]$ would be valid, but $[3,2,1]$ or $[2,1,1]$ would be invalid.

A simple way to generate this set would be to just randomly sample from $S$, and then sort the resulting sequence. However, please note that the following approach is biased ($[1,1,1]$ is less likely to occur than $[1,2,3]$, for example).

This question is related to one of the answers given in this StackOverflow question:https://stackoverflow.com/questions/26467434/generating-random-number-in-sorted-order. Note that the algorithm proposed there is to generate such a sample without repetition, whereas I want my sample to be generated with repetition.

$\endgroup$
11
  • $\begingroup$ Is it easy to compute precisely how biased this "simple" method is? (As an example, $[1,2,3]$ is six times more likely than it should be in your case.) If so then you can achieve an unbiased method by randomly rejecting some of the outputs of this "simple" method. This would probably be rather slow, but if you don't really need particularly high speed then that's not a problem. If you need faster than you'll need to be a bit more clever. $\endgroup$
    – Ian
    Commented May 8, 2019 at 19:00
  • $\begingroup$ In any case, does the simple algorithm "randomly pick $s_1$ from $S_1,\dots,S_M$, randomly pick $s_2$ from $s_2,\dots,S_M$, ..." give a biased result as well? (By the way, are you sure it makes sense to do this problem in the setting of just a partial order? For a partial order not all samples can be sorted...) $\endgroup$
    – Ian
    Commented May 8, 2019 at 19:10
  • $\begingroup$ @Ian, this "correction" method is something I've been thinking of. However, I couldn't figure out how to compute this bias in the general $N$, $M$ case. Any help with that would be much appreciated! As for your second comment, I do not understand the sample techniques you're describing. It appears to me as if you are just picking the elements in order, but that wouldn't be a random sample. Finally, by partial order, I meant something like <= for integers (which is actually the real problem I'm trying to solve). Please let me know if my naming is incorrect so I can adapt the question. $\endgroup$
    – Setzer22
    Commented May 8, 2019 at 19:22
  • $\begingroup$ If you're talking about a totally ordered set then the bias is straightforward to compute: a particular sample will have its probability multiplied by the number of permutations of that sample that exist, which is easily obtained by using factorials. As for my second idea, the point is to randomly select elements of your sample in order from among those that you're still allowed to select based on the sorting requirement. Again this is reliant on the order being total. $\endgroup$
    – Ian
    Commented May 8, 2019 at 19:24
  • $\begingroup$ @MarcusRitt Note that the interval is always closed, so $\langle 1,2 \rangle$ can indeed give $[1,1]$ in that approach. $\endgroup$
    – Ian
    Commented May 8, 2019 at 19:26

2 Answers 2

5
$\begingroup$

It's enough to pick $N$ random elements from $\{ 1, 2, \ldots, M+N-1 \}$ without replacement and then do a postprocessing step. Say you pick $T_1 < T_2 < \ldots < T_N$; then let $S_K = T_K - K + 1$. For example with $M = 4, N = 3$, this is like picking $3$ random elements from $\{1 ,2 , \ldots, 6\}$. So for example you might pick $T = \langle 1, 4, 5 \rangle$ and then $S = \langle 1 - 1 + 1, 4 - 2 + 1, 5 - 3 + 1 \rangle = \langle 1, 3, 3 \rangle$.

So you need an algorithm for picking random subsets of a given size.

To pick a random subset of size $k$ of the set $\{1, 2, \ldots, n\}$, there's a nice recursive algorithm. Such a set includes $n$ with probability $k/n$. If it includes $n$, then take the set to be a subset of $\{1, 2, \ldots, n-1\}$ of size $k-1$, with $n$ adjoined; if it does not include $n$, then the remainder is a subset of $\{1, 2, \ldots, n-1 \}$ of size $k$. (I learned this algorithm from the late Herb Wilf's notes "East Side, West Side", available online at https://www.math.upenn.edu/~wilf/eastwest.pdf - see page 16 for code. It's in Maple, but should be reasonably understandable.)

$\endgroup$
4
  • $\begingroup$ Must the $T_K$ be sorted? If not then $T_2$ could be $1$ and then you have a problem. $\endgroup$
    – Ian
    Commented May 8, 2019 at 20:25
  • 1
    $\begingroup$ Also you should obviously have $T_N$ not $T_M$. $\endgroup$
    – Ian
    Commented May 8, 2019 at 20:27
  • $\begingroup$ This is a very elegant solution! As @Ian mentioned, the first random subset must be sorted for this to work, but other than that it worked fine and was very easy to implement in code, thanks! $\endgroup$
    – Setzer22
    Commented May 8, 2019 at 20:57
  • $\begingroup$ I intended for the $T_K$ to be sorted, but it's not obvious from the notation. I will edit accordingly. $\endgroup$ Commented May 9, 2019 at 1:59
2
$\begingroup$

I would just draw $3$ random numbers and only accept ones in ascending order, that way you have equal probabilities (i.e. rejection method as discussed)

Otherwise,

Sample the triples by using monte carlo. I.e. count how many different combinations are permissible, and accept each with equal probability according to different values of a $U[0,1]$, i.e. give $111$ the range $[0,1/n]$, $211$ is $[1/n, 2/n]$. As long as you have some sensible ordering on the set of possible sequences you are in business. You can use for loops to achieve this.

$\endgroup$
3
  • 1
    $\begingroup$ For moderately large $N,M$, the first approach is very slow due to acceptance being rare, while the second approach is slow to get started because there will be many such sorted sequences to handle. $\endgroup$
    – Ian
    Commented May 8, 2019 at 21:56
  • $\begingroup$ Hmm yes agree first approach is kind of standard rejection sampling with low acceptance. For second one you could probably just compute $nU$ with $U$ the standard uniform and then take integer part. Then you can just pass this to an array containing all of the sorted sequences in order. $\endgroup$
    – fGDu94
    Commented May 8, 2019 at 22:25
  • $\begingroup$ Can make function from naturals $\leq n$ to sequences by doing a recursive function $\endgroup$
    – fGDu94
    Commented May 8, 2019 at 23:10

You must log in to answer this question.

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