TARGET SHOOTING WITH PROGRAMMED RANDOM VARIABLES

• 成果类型: Article
• 署名作者: Brightwell, Graham; Ott, Teunis J.; Winkler, Peter
• 署名单位: University of London; London School Economics & Political Science; Telcordia Technologies; Nokia Corporation; Nokia Bell Labs; AT&T
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/aoap/1177004707
• 发表日期: 1995
• 页码: 834-853

摘要

We consider the following distributed optimization problem: Given a set X-1, ..., X-n of pairwise independent random variables and a target value T, a subset of the X-i's must be selected whose sum is close to T. However, no cooperation is permitted in determining the set; each variable must be programmed in advance, joining or not joining according to its own value. Such conditions may arise, for example, when supply of some commodity is controlled at several random sources. Under these general conditions we show that the mean square error in approximating T is always minimized by programming each X-i to join if its value is between 0 and theta(i) for appropriate choice of thresholds theta(i). When in addition the variables are identically distributed, we give conditions under which the theta(i)'s must be equal. The case of uniform distribution on [0, 1] (in which our conditions fail) is analyzed in detail, showing the rather bizarre behavior of the theta(i)'s which may take place in general as the target value is gradually changed. We analyze also the problem in which the variables are permitted to contribute any part of themselves to the sum; here it turns out that in an optimal strategy, each program will be of the form contribute the minimum of X-i and gamma(i), with all the gamma(i)'s equal in the i.i.d. case. Finally, we show how the original target shooting problem can be generalized to a kind of load balancing, where variables are assigned to different buckets, each with its own target, and the penalty is a weighted sum of squared errors. The surprising result here is that when the weights are equal, an optimal solution assigns variables only according to their signs.