1
$\begingroup$

I want to generate a sequece S[ ] of members chosen randomly from 4 finite sets, namely set1 ,set2,set3 and set4. Where all sets have the same size and are not empty.

Basically,for each i , I can chose randomly a set then can chose randomly the term S[i] from the chosen set.

But I know it is not random enough because , some members belong to 2 sets . Call the set of such members as Border . I know no member belongs to 3 or more sets.

Finally ,I concluded that , I must check , for each i , that if the chosen term S[i] is in Border.

If it is then I probabilistically discard this S[i] on the chance of ( 1 on 2 ) and chose new S[i] again , allowing the discarded S[i] = the new S[i]. And checking must be done exactly once for each i.

Is this algorithm exactly random?

Thank you very much .

PS, I noticed one point . Some members belong to 3 sets at most. So let me call the sets of such members as Border2 and Border3 respectively. Where the post fixes indicate the number of sets to which members belong . Please let me know how to generate S[] exactly randomly .

  • 0
    @seven: Your "To: Name" do not signal "Name" that a comment is directed at him/her, in fact this has no effect at all. Please use "@Name" to start your comment when you want "Name" to be signalled.2011-06-21

1 Answers 1

4

I'm still not sure exactly what OP wants, but I think the only way to make any progress here is to post an answer and refine it if OP has any objections.

Suppose your 4 sets are $\lbrace a,b\rbrace,\lbrace a,c\rbrace,\lbrace d,e\rbrace,\lbrace f,g\rbrace$. All told, there are 7 elements, and you want to choose each with probability $1/7$. You could just lay out the 7 elements and choose one uniformly at random, but for some reason you would rather choose one of the four sets uniformly at random, then choose an element uniformly at random from that set, and if the chosen element is in more than one set (in our case, if the chosen element is $a$), then with probability $1/2$ you want to discard it and try again. So let's see what happens with that procedure.

The probability of winding up with $d$ is the probability of getting $d$ in one go, plus [the probability of getting $a$, times the probability of discarding $a$, times the probability of then getting $d$ on the second go]. This is $(1/8)+(2/8)(1/2)(1/8)=9/64\ne1/7$.

So already we see that we're not getting the desired $1/7$.

The results for $e$, $f$, and $g$ will be the same as for $d$.

Now that I think of it, the same calculation applies to $b$ and to $c$. Let's look at $a$. The probability of getting $a$ is $(1/4)(1/2)+(1/4)(1/2)(1/4)=5/32$.

So if "exactly random" means "each outcome equally likely" (and Gauss knows I've tried to extract that piece of information, with no success whatsoever), then the protocol described in the question fails.

  • 0
    I am very surprised to know my algorithm is not exactly random . Thank you very much.2011-06-21