Re: An optimization problem

Wen 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,
say X_j is chosen. Then all the random variables whose value is
smaller than or equal to X_j are eliminated from the system, and a
cost of X_j is incurred at this step. Same steps happens to the rest
of the random variables until all the random variables are eliminated
(They all follow the same distribution at each step). The objective is
to minimize the cost.
I model this problem using dynamic programming and theoretically it
can calculate the optimal solution using backward calculation.
However, with the increasing of N, the number of possible states
expands exponentially, making it impossible to enumerate all the
states. For example, if N=100 and the number of possible values X_i
can take is 10, then we are facing a state space of 10^100. Is there
an effective way to approximately solve this problem? Thanks a lot in
advance.

An exact solution is probably too much to ask for but if I understand the problem correctly it is possible to get a good approximation.

Let us call the minimal expected cost for eliminating all of n variables C_n. Clearly C_0 = 0 and C_1 = E(X).

Now suppose we know C_i for all i < n. Then we can express the optimum strategy for eliminating n variables as follows:
Let x_1, x_2, ..., x_n be the outcome of the variables at the current step. Put these in nondecreasing order: y_1 <= y_2 <= ... <= y_n.
The expected cost of eliminating the first k now and the rest later is
y_k + C_(n-k). We want to minimize that cost, so we take
min(k=1..n) (y_k + C_(n-k)).

Now it is clear that the minimal expected cost for n variables
C_n = E(min(k=1..n) (Y_k + C_(n-k))),
where Y_1, .., Y_n are the order statistics of X_1, .., X_n.

In general I don't think it's practical to calculate that expectation exactly, but it's fairly easy to get a Monte Carlo approximation for it.

For example for a uniform distribution on [0, 1] I get
C_1 ~= 0.500
C_2 ~= 0.625
C_3 ~= 0.703
C_4 ~= 0.757
C_5 ~= 0.797
C_6 ~= 0.827
C_7 ~= 0.850
C_8 ~= 0.868
C_9 ~= 0.882
C_10 ~= 0.893

Is this what you would call an effective way?

--
Niels Diepeveen
.

Relevant Pages

  • Re: An optimization problem
    ... generates a realization of the N random variables according to their ... probability distribution. ... Let us call the minimal expected cost for eliminating all of n variables ... but it's fairly easy to get a Monte Carlo approximation for it. ...
    (sci.math)
  • Re: Analysis Tool Pack: Random function help
    ... In Excel Help. ... Click the distribution method you want to use to create random values. ... Characterized by a probability of success on a given trial. ... Bernoulli random variables have the value 0 or 1. ...
    (microsoft.public.excel.programming)
  • Re: Renewal process
    ... be played by a geometric distribution with parameter p? ... studied "compound random variables" yet? ... enough in order to know what to take the Laplace transform? ... discarding arriving customers we put them ...
    (sci.math)
  • Re: MLE Related Proof
    ... #3) The pdfs all have the same common support. ... Lindeberg-Levy thm is invoked to get the limiting distribution of the ... that f represents the distribution of the random variables X1, ... Kullback-Leibler distance ...
    (sci.stat.edu)
  • Re: An optimization problem
    ... generates a realization of the N random variables according to their ... probability distribution. ... but it's fairly easy to get a Monte Carlo approximation for it. ...
    (sci.math)