Research often takes twisty little paths, and as the result of a recent attempt to gain understanding about a problem I was trying to understand the difference between the following two systems with balls and (ordered) bins:
- Synchronous: take all of the top balls in each bin and reassign them randomly and uniformly to the bottoms of the bins.
- Asynchronous: pick a random bin, take the top ball in that bin, and reassign it randomly and uniformly to the bottom of a bin.
These processes sound a bit similar, right? The first one is a batch version of the second one. Sort of. We can think of this as modeling customers (balls) in queues (bins) or balls being juggled by hands (bins).
Each of these processes can be modeled as a Markov chain on the vector of bin occupation numbers. For example, for 3 balls and 3 bins we have configurations that look like (3,0,0) and its permutations, (2,1,0) and its permutations, and (1,1,1) for a total of 10 states. If you look at the two Markov chains, they are different, and it turns out they have different stationary distributions, even. Why is that? The asynchronous chain is reversible and all transitions are symmetric. The synchronous one is not reversible.
One question is if there is a limiting sense in which these are similar — can the synchronous batch-recirculating scheme be approximated by the asynchronous version if we let or get very large?