Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 .

share|improve this question
4  
Your post seems inconsistent: compare I know no member belongs to 3 or more sets and Some members belong to 3 sets at most. –  Did Jun 19 '11 at 9:42
    
Certainly you have to reject your term by the probability $1-\frac{1}{n-1}$ where $n$ is the amount of total occurences of your term. –  Listing Jun 19 '11 at 10:16
    
You tell me what you mean by "exactly random," and I'll tell you how to generate things exactly randomly. –  Gerry Myerson Jun 19 '11 at 12:01
2  
It is better to begin with exact formulation. Does it mean that if there are $n$ different elements in four sets when any of those elements has a probability $1/n$? –  Andrew Jun 19 '11 at 12:04
    
To:Gerry Myerson , I do not know how to define randomness. But I know mathematicians use the word,random. So it must have the exact definition. –  seven_swodniw Jun 20 '11 at 7:34
show 7 more comments

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
I am very surprised to know my algorithm is not exactly random . Thank you very much. –  seven_swodniw Jun 21 '11 at 13:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.