I have following problem. I have set of objects, there is N objects. These object might join with each other. Two objects might join with probability $p_{join}$. In every computations step I take all possible couples of objects and put them into queue. For each couple from the queue I draw a number (from (0...1)) if number is smaller than $p_{join}$ then I join these two objects, I get one object and I do not use these connected objects in computations any more (so if object belongs to different couple that I have in queue for computation I discard this couple). This new object will be used in computation in the next step (but not in the current one).

I need equation (it might be some recurrence equation) for the number of connected objects in one step (at the beginning I have N object and I want to know how many of them joined after one step). I also need equation of probability of the event that tow objects join with other.

Currently I try to count it in the following way, however I'm unable to create one coherent equation:

$p_{N} = (1-(1-p_{join})^{N-1}$ At the beginning I have N objects I count possibility that object N do not connect with any other object $1-p_{j}^{N-1}$ and then I subtract it from $1$ in order to get possibility that N will join with something.

$p_{N-1} = p_{N}(1-(1-p_{join})^{N-3}) + (1-p_{N})(1-(1-p_{join})^{N-1})$ Then I take object $N-1$, depends on this what happened with object N I have $N-1$ (if object N did not join with other object) or $N-3$ (if object N join with something, then it removed two objects from set of objects and I do not have $N^{th}$ object and some other object)

$p_{N-2} = p_{N}p_{N-1}(1-(1-p_{join})^{N-5}...$

All object are the same and not recognizable.

Example for 4 objects (for convenience we introduce A B C D as a representation of objects (but all object are the same and there is no possibility to recognize them so these names are introduced just for clarity of example): At the beginning I take A object then I have three couples (AB AC AC) so three times I draw number (float value) (0...1) and compare with $p_{join}$. If any of this drew numbers is smaller than $p_{join}$ then I assume that A connected with some other object for example D. Then I take next strand that is still free. It will be B, now if A connected with other strand (for example D) I have only one couple to check BC, if A did not connected with other strand then I have to check couples BA, BC and BD. For C if A and B connected with other objects then C is connected so I have $0$, if A did not connect but B connected I can connect C with A, and if A and B did not connect I can connect C with A B or D. Etc.

so it is getting more and more complicated.

  • $\begingroup$ I think you may need to explain this some more. What is $j$? What is the difference between $n$ and $N$? If there are $N(N-1)/2$ potential couples, then why is this not the exponent in the probability that no couples are formed? $\endgroup$
    – Henry
    Mar 31, 2011 at 22:18
  • $\begingroup$ @Henry Thank you. $p_{j}$ is a symbol that represents probability that two strands join for example $0.1$. and $n$ I introduced by mistake should be $N$ all the time. I thought that there is $(N-1)*(N-1)/2$ potential couples because the first object I can create has $N-1$ couples, then for the second one I can create $N-1$ possible couples too, etc. But there is a possibility that my equations are wrong ... $\endgroup$
    – Darqer
    Mar 31, 2011 at 22:36
  • $\begingroup$ It seems that $p_N, p_{N-1}, \ldots$ refer to something different from $p_j$? Then they should be denoted by a different letter. Also, it seems the $j$ is not an index but stands for 'j' as in "join"? Then it would seem advisable to denote it differently, because $p_j$ looks very much like a $j$-th probability. (Also, technically, if $j$ is a name and not a variable, it shouldn't be italicized.) But even after taking all this into account, I don't quite see how you arrived at the equations you wrote. $\endgroup$
    – joriki
    Mar 31, 2011 at 22:42
  • $\begingroup$ @joriki yes they differ $p_{N}$ is the probability that object N might be connected with some other strand from N-1 strands, and p_{j} is used when I have this couples it is the probability that two strands (from this couple) connects with each other (I should denote it as p_{join}). I put explanation of equations under equations. $\endgroup$
    – Darqer
    Mar 31, 2011 at 22:50

1 Answer 1


My understanding of what a "step" constitutes is this. You take all $N(N-1)/2$ pairs of objects, and go through them one at a time (in some order). Each pair has probability $p_j$ of being joined, as long as neither member of the pair has already been joined. For simplicity, let me write $p_j = p$ and $1-p_j = q$. However, the result will depend on the order in which you take these pairs.

For example, if N=4 you might take the 6 pairs in the following order: (1,2), (1,3), (2,3), (1,4), (2,4), (3,4). In that case the probability that you end up with two joined pairs is $p^2 (1 + q + q^2)$, corresponding to the following scenarios:

a) join (1,2), discard all the rest except (3,4), join (3,4): probability $p^2$.

b) don't join (1,2), join (1,3), discard the rest except (2,4), join (2,4): probability $q p^2$.

c) don't join (1,2), don't join (1,3), join (2,3), discard the rest except (1,4), join (1,4): probability $q^2 p^2$.

On the other hand, suppose you use the following order: (1,2), (1,3), (3,4), (2,4), (2,3),(1,4). Then the probability of ending with two joined pairs is $p^2 (1 + q + q^4)$, since the ways to end up with two joined pairs are

a) join (1,2), discard the rest except (3,4), join (3,4): probability $p^2$.

b) don't join (1,2), join (1,3), discard the rest except (2,4), join (2,4): probability $q p^2$

c) don't join (1,2) or (1,3) or (3,4) or (2,4), join (2,3), join (1,4): probability $q^4 p^2$.

  • $\begingroup$ Thank you. You have got the point. I think that proper version will assume that all elements are the same and unrecognizable $\endgroup$
    – Darqer
    Mar 31, 2011 at 23:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .