Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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? – Henry Mar 31 '11 at 22:18
@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 ... – Darqer Mar 31 '11 at 22:36
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. – joriki Mar 31 '11 at 22:42
@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. – Darqer Mar 31 '11 at 22:50

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$.

share|cite|improve this answer
Thank you. You have got the point. I think that proper version will assume that all elements are the same and unrecognizable – Darqer Mar 31 '11 at 23:53

Your Answer


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.