Best process for drawing numbers

Question

This is a follow up to my previous question.

Assume I want to randomly draw two numbers from the numbers 1 to 8, one even number and one odd number. I would create two urns, one with the even, one with the odd numbers, and draw one number from each. Thus, all numbers have the same probability to be drawn. This was the accepted answer to my previous question.

Now assume I have the numbers from 1 to 9. I want to draw one number that is smaller or equal to 5, i.e. {1,2,3,4,5}, and one number that is larger or equal to 5, i.e. {5,6,7,8,9}. How would I draw them so that all numbers have the same probability to be drawn?

My idea would be to create two urns, one with the numbers {1, 1, 2, 2, 3, 3, 4, 4, 5}, the other with the numbers {5, 6, 6, 7, 7, 8, 8, 9, 9}. If I flip a coin to randomly chose one urn, then randomly draw one number, all numbers have the same probability to be drawn. But if I draw a 5 and then switch to the other urn, there is a possibility that I draw a second 5 -- which is not what I want to allow to happen.

How would you do it?

If you know a more meaningful title for this question, please edit it.

Answer 1

(edited to fix the missed 'equally likely' condition as pointed out by @wannymahoots)

With small numbers of possibilities I'd just list all the possibilities as pairs:

1 5      1 6      1 7      1 8      1 9   
2 5      2 6      2 7      2 8      2 9   
3 5      3 6      3 7      3 8      3 9   
4 5      4 6      4 7      4 8      4 9   
         5 6      5 7      5 8      5 9   

However, these $5\times 5-1 = 24$ possibilities should not be equally likely, because of the condition that the '5' should occur as often as all the other numbers.

If you look, 1-4 and 6-9 all occur 5 times but 5 occurs 8 times. So you need to have different weights on them. One way is to just do a bunch of copies of each:

have 4 copies of each of these:

1 5 
2 5  
3 5   
4 5   
         5 6      5 7      5 8      5 9   

and 7 copies of each of these:

 1 6      1 7      1 8      1 9   
 2 6      2 7      2 8      2 9   
 3 6      3 7      3 8      3 9   
 4 6      4 7      4 8      4 9   

and then each digit occurs 32 times. This makes a total of $4\times 8 + 7\times16 = 144$ pairs.

So generate a number from 1 to 144 and pick that row (equivalently label 144 balls with those pairs of numbers and choose one of the balls at random from the urn)

If you wanted to allow for the possibility that they could occur in either order, you can either list all 288 pairs in either order, or you can draw the 144 and then randomize the order at then end.

Of course, it is also possible to just do weighted selection from the original 24, if you know how to do that - though it will be a little slower.

Answer 2

One solution might be a simple throwback mechanism: First, you draw any of the nine numbers. Then you draw from the remaining ones, and you stop only when you have a valid double draw (you are allowed to remove the "wrong" second draws each time).

This is unlikely to be the best possible way, as it may involve "a lot" of rejected second draws, but (without having done the maths) this should at least be a valid sampling scheme. You can remove the rejections by providing more urns that match the valid second draws depending on your first draw.