Re: An optimization problem

On 7月6日, 下午9时48分, Chip Eastham <hardm...@xxxxxxxxx> wrote:
On Jul 2, 3:22 am, Wen <huangwe...@xxxxxxxxx> wrote:

On 7月2日, 上午3时39分, Chip Eastham <hardm...@xxxxxxxxx> wrote:

On Jul 1, 9:01 am, Wen <huangwe...@xxxxxxxxx> wrote:

I have N i.i.d. random variables X_i, i=1,...,N
following certain discrete distribution. We proceed
as follows: initially the system generates a
realization of the N random variables according to their
probability distribution. Observing this, we choose
one among them,

[snip]

Hi Chip,
It actually grows as a power of the number of the
possible values that X can take because we have to
enumerate all possible value combinations

Hi, Wen:

One approach to enumerating "all possible value
cominations" is to check the sequences of length
N at stage N, which gives an event space of M^N
where M is the number of discrete costs possible.

But we can do the checking in a different way to
get O(N^M) complexity. Consider the ways of
expressing N as a sum of M nonnegative integers,
and let these represent the number of times each
cost appears in an outcome. This is no longer a
"uniform" probability space (assuming the i.i.d.
user costs were even uniform to begin with), but
the probabilities can be easily obtained from the
given i.i.d. chances by considering all possible
permutations of the M summands. So the space of
outcomes is now polynomial in N (M fixed) rather
than exponential in N.

What I had in mind, though, was that it is not
necessary to enumerate the whole outcome space
at each stage. As N grows, the expected cost of
eliminating N users grows monotonically. For a
bounded distribution on cost X, one intuitively
thinks the expected cost will tend to the
maximum value of that distribution. As we get
to these later stages, most outcomes will fall
into the case of paying Y_N to elimate all users
at once. The computational work can be done by
enumerating only over the smaller number of cases
in which paying a lesser Y_i is optimal.

I have in mind to use your example of uniform
probabilities for X in {1,2,5,10} to illustrate
the complexity of an exact computation. But the
use of the Monte Carlo simulation suggested by
Niels Diepeveen is an attractive one.

regards, chip

Hi, Chip:

I understand the intuition that with the increasing of N, it tends to
eliminate all the users at once. However, I don't quite understand the
part that how to shrink the enumerating space to O(N^M). Can you
illustrate your idea with an example? Thanks a lot!
.

Relevant Pages

  • Re: An optimization problem
    ... following certain discrete distribution. ... cost appears in an outcome. ... "uniform" probability space (assuming the i.i.d. ... necessary to enumerate the whole outcome space ...
    (sci.math)
  • Re: Ask for help on sample size decision for a non-normal distribution
    ... ranther than infinity due to the cost and time. ... sysmmetric distribution with mean=0. ... The answer is: infinity. ... The probability ...
    (sci.stat.math)
  • Re: Ask for help on sample size decision for a non-normal distribution
    ... I should find a minimum sample size rather than the inifinite ... due to cost and time. ... sysmmetric distribution with mean=0. ... The probability ...
    (sci.stat.math)
  • Re: Pigeons, People, and Priors
    ... the variance of the probability generator go to zero you have a continuum ... a random-interval 60 s schedule is not. ... The Exponential Distribution ... I probably should have used the phrase "statistical learning theory" rather ...
    (comp.ai.philosophy)
  • Re: So called "stimulus/response" models
    ... Instead of answering to each misunderstood, ironic and out of context ... Sorry, you exhibit a simplistic view of probability theory, and an even more ... of acquiring the consequences of responses. ... distribution over consequences of a given act. ...
    (comp.ai.philosophy)