Proving Set Convergence with Random Procedure

[JimmyT]

Suppose there are n items which are belong to two sets, A and B, such that A intersects B yields a non-empty set C. I apply the following procedure:

-------------------------------------------------
Allocate each of the n items to a single item bin (so there will be n single-item bins).
Repeat the following two steps many times:
(1) From the n items, randomly select two separate items i and j
(2) If items i and j are from the same set, move i to j's bin.
-------------------------------------------------

Questions: Will this procedure always converge to a fixed number of non-empty bins?
If yes, can you provide some clues how I can prove this?

Here are some of my thoughts (pls correct me if I am wrong):

The answer is obvious when A and B are disjoint --- there are two non-empty bins left after many iterations.

I find it a bit tricky if A intersects B yields a non-empty set C, then we may end up with one non-empty bin (especially when |C| is a lot larger than |A| and |B|), or we may end up with two non-empty bins (especially when |C| is a lot smaller than |A| and |B|). In any case, I am just interested to show that the procedure will (almost surely) converge to some constant number of non-empty bins, after many iterations.

Any help will be appreciated.

Thanks!

 

[mXSCNT]

-------------------------------------------------
Allocate each of the n items to a single item bin (so there will be n single-item bins).
Repeat the following two steps many times:
(1) From the n items, randomly select two separate items i and j
(2) If items i and j are from the same set, move i to j's bin.
-------------------------------------------------

I assume from context that "j's bin" does not mean the bin j started in, but the bin j is in now. According to this interpretation, a bin once empty can never become nonempty. Therefore the number of nonempty bins is nonincreasing, but greater than 0, so it has to converge to some value. As you said, if A and B are disjoint, that value will be 2. If they intersect, that value will be 1. With a certain nonzero probability an element c of C can "pull" all the elements of A and B to the same bin that c is in, and once it has finished doing that, there will be only 1 bin left and no more changes.

 

[JimmyT]

Thanks heaps. I am clearer now.