 Subject: Lower and upper bound of variables (1D and 2D cases)
Date: Mon, 21 Feb 2000 18:46:33 PST
From: john lee

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 Ci, i=1,2,...N. Ci is a real number. At the beginning, Ci is 0 for all i.

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

At the beginning of every second, Ci increase by pi, i.e., Ci = Ci + pi.

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

So, we know that at the end of every second, the summary of all Ci is exactly 0. But for every individual Ci, 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 [Ci,j]. Ci,j is real number for all i,j. At the beginning, Ci,j is 0 for all i,j.

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

At the beginning of every second, Ci,j increases by pi,j, i.e., Ci,j = Ci,j + pi,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 Ci,j.

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

So, at the end of every second, the summary of Ci,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. 