Randomly sampling unique subsets of an array

Question

If I have an array:

a = [1,2,3]

How do I randomly select subsets of the array, such that the elements of each subset are unique? That is, for a the possible subsets would be:

[]
[1]
[2]
[3]
[1,2]
[2,3]
[1,2,3]

I can't generate all of the possible subsets as the real size of a is very big so there are many, many subsets. At the moment, I am using a 'random walk' idea - for each element of a, I 'flip a coin' and include it if the coin comes up heads - but I am not sure if this actually uniformly samples the space. It feels like it biases towards the middle, but this might just be my mind doing pattern-matching, as there will be more middle sized possiblities.

Am I using the right approach, or how should I be randomly sampling?

(I am aware that this is more of a language agnostic and 'mathsy' question, but I felt it wasn't really Mathoverflow material - I just need a practical answer.)

Answer 1

Just go ahead with your original "coin flipping" idea. It uniformly samples the space of possibilities.

It feels to you like it's biased towards the "middle", but that's because the number of possibilities is largest in the "middle". Think about it: there is only 1 possibility with no elements, and only 1 with all elements. There are N possibilities with 1 element, and N possibilities with (N-1) elements. As the number of elements chosen gets closer to (N/2), the number of possibilities grows very quickly.