I have two problems which are related, one is 1-D case, another is 2-D case. In the problems I want to get the lower and upper bound of variables.

There have N variables C_i, i=1,2,...N. C_i is a real number. At the beginning, C_i is 0 for all i.

Associating with every C_i, there has a p_i, which is a non-negative real number. And the summary of all p_i is exactly 1, i.e., \sum_{i=1}^{i=N} p_i = 1.

At the beginning of every second, C_i increase by p_i, i.e., C_i = C_i + p_i.

Then, the C_i with the maximum value is selected. (Ties are broken randomly) The selected C_i (only one will be selected) will decrease by 1, and all others are unchanged: we select i, where C_i >= C_j, for all j, then let C_i = C_i - 1.

So, we know that at the end of every second, the summary of all C_i is exactly 0. But for every individual C_i, it can be 0, negative, or positive.

I want to know whether we can find the tight lower and upper bound of C. I can prove that the lower bound is -1, and upper bound is N/2. But by simulation, I found the upper bound is very close to 1. (It's larger than 1) Can you show me how to prove a tight upper bound?

There has an NxN array [C_i,j]. C_i,j is real number for all i,j. At the beginning, C_i,j is 0 for all i,j.

Associating with every C_i,j, there has a p_i,j. p_i,j is a non-negative real number. And the summary of p_i,j in every column and every raw is exactly 1, i.e., \sum_{i=1}^{i=N} C_i,j = 1 \forall j, and \sum_{j=1}^{j=N} C_i,j = 1 \forall i.

At the beginning of every second, C_i,j increases by p_i,j, i.e., C_i,j = C_i,j + p_i,j

Then a matching is found. The matching is defined as following: From the NxN array, we select exactly N elements, where in every column there has exactly one element selected, and in every raw there also has exactly one element selected.

There has a large number of possible matchings for a large N. In this problem we try to find the Maximum Weight Matching (MWM). Where from all the matchings, we find the matching that can maximize the summary of C_i,j.

Then, after the matching is selected, C_i,j will decrease by 1, if (i,j) is in the matching.

So, at the end of every second, the summary of C_i,j in every column and raw is exactly 0.

I want to know whether we can find the lower bound and upper bound of C.

By simulations, I found that the lower bound is larger than -2, and the upper bound is about +4.

In the simulations I set N to 16 and 32.

Copyright © 1996-2009 Alexander Bogomolny

33062614