# Probability of being in same bin in a random clustering scenario

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?

-
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

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.