1
$\begingroup$

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.

  • 0
    @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.2011-03-31

1 Answers 1

2

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

  • 0
    Thank you. You have got the point. I think that proper version will assume that all elements are the same and unrecognizable2011-03-31