Convergence of sets

  • Thread starter JimmyT
  • Start date
  • #1
2
0

Main Question or Discussion Point

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!
 

Answers and Replies

  • #2
315
1
-------------------------------------------------
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.
 
  • #3
2
0
Thanks heaps. I am clearer now.
 

Related Threads for: Convergence of sets

Replies
2
Views
2K
Replies
6
Views
4K
  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
11
Views
10K
Replies
4
Views
6K
Replies
3
Views
1K
Replies
0
Views
1K
  • Last Post
Replies
1
Views
2K
Top