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 have a set of $N(\geq 2)$ objects which I randomly group in $C(\leq N)$ clusters i.e. all the $C$ clusters have atleast one object and all such clusterings are equally likely.

What is the probability that 2 particular objects from this group of $N$ objects are in same cluster?

share|improve this question
1  
The title says "expectation" and the body says "probability". –  joriki Apr 13 '13 at 6:19
    
If we "throw" the objects at the bins, then some bins may remain empty. A completely different model is that all $(x_1,\dots,x_n)$ such that $x_i\ge 1$ and $\sum x_i=N$ are equally likely. This is an implausible model for any real phenomenon: almost everybody in Bin $1$, and one object in $2$, is far less likely under the throwing model than a more even distribution. –  André Nicolas Apr 13 '13 at 6:25
    
@joriki : corrected the title. –  damned Apr 13 '13 at 6:33
    
@AndréNicolas : I wish to measure performance of my clustering against a random clustering of same granularity and the problem statement is described above. –  damned Apr 13 '13 at 6:34

1 Answer 1

up vote 1 down vote accepted

I don't know if it is what you ask, but the answer with fixed clusters can be derived in this way:

What is the probability that 2 particular objects belong to the kth cluster?

The probability is the number of manners to combine two individuals from cluster $k$ ($C_k$ is the number of objects on the cluster $k$) divided by the number of manners to combine two individuals from $N$ of them (the total number of pairs).

$(_{2}^{C_k})/(_{2}^{N})$.

What is the probability that the 2 particular objects belong to the same cluster? Since the pair belongs to the cluster 1 or cluster 2 or ... or cluster C, we have:

It is the probability that the 2 objects belong to the cluster $1$ (with $C_1$ objects) plus the probability that the 2 objects belong to the cluster 2 (with $C_2$ objects) plus .... plus the probability that the 2 objects belong to in the cluster C (with $C_c$ objects)

$(_{2}^{N})^{-1} \sum_{k=1}^{C} (_{2}^{C_k})$,

where $C$ is the number of clusters.

Edit any error, please!

share|improve this answer
    
Can you explain more clearly please? I am not able to comprehend your explanation. What is C_k? –  damned Apr 13 '13 at 6:48
    
Sure. I will edit the answer. –  Emmanuel Ferreira Apr 13 '13 at 13:22
    
What did you mean with "the clusters are equally likely"? –  Emmanuel Ferreira Apr 13 '13 at 13:41
    
I meant that all "clusterings" i.e distribution of N objects into C clusters are equally likely. –  damned Apr 14 '13 at 6:35
    
thus C is fixed. –  Emmanuel Ferreira Apr 14 '13 at 13:29

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.