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 .

  • 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*.2011-06-19
  • 0
    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.2011-06-19
  • 0
    You tell me what you mean by "exactly random," and I'll tell you how to generate things exactly randomly.2011-06-19
  • 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$?2011-06-19
  • 0
    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.2011-06-20
  • 0
    To: Andrew , Yes . So I can generate a random sequence S simply by chosing S[i] randomly from all elements in the 4 sets. But if I can chose a set randomly first then the things would be very simple in my actual case.2011-06-20
  • 0
    To : Didier Piau , I am sorry. The first fact is the original explanation . And the second contradictory fact is an amendment.2011-06-20
  • 0
    To : Listing , does n mean the length of the sequence S? If so , do you mean that the length of S affects the random choice of the first term of S?2011-06-20
  • 0
    To : Gerry Myerson , I mean some mathematicians use the word , random. And as mathematics must be exact always , "random" must be same as "exactly random".2011-06-20
  • 0
    @seven_swodniw, yes, mathematicians use the word random, but they use it carefully, so that it is possible to tell exactly what a mathematician means when she uses the word. Non-mathematicians use it carelessly, so no one can tell what they mean, except possibly the person using the word. So I'm asking: what do **you** mean when you write about something being "exactly random"? Unless I know what **you** are trying to do, I can't begin to answer your question.2011-06-20
  • 0
    To :Gerry Myerson , maybe to define my question mathematically is beyond my mathematics. Roughly,the 4 four sets represent the 4 faces of a tetrahedron . And members represent some finite points on the 4 faces drawn by a simple formula ( somhow like lattice points ). So points on edges belong to 2 sets except that points on vertices belong to 3 sets. And you can distinguish a face from other faces only by their ID , because they are symmetrical in any way.2011-06-20
  • 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