Among N machines, there are up to k machines in bad / unacceptable condition.
After a primitive testing over the N machines, given the probability 
of the N machines in bad condition is (p_1, p_2, ..., p_N). 
Question: If we randomly select m machines from N, the probability at least 
one machine is in bad condition?

---

Clarification of Question by dogwood-ga on 05 Sep 2004 04:31 PDT

Hi, Rececar,

Thanks for your another try. My intension is to prove that with the
primitive test, the bad machine will be selected in lower probability
than without knowing the individual probability (p_1,..p_N). I hope to
know the advantage with the individual probability over without that
parameter.

I knew, without the individual probability, the probability of that
one machine is bad among the m is

Min(k,m)   (j,k)*((m-j),(N-k))
  SUM   ________________________
  j=1       (m,N)

With only the individual probability but no constraint in k,  the probability 
           m
is   1 - PRODUCT(1-p_j)
          j = 1

I'm trying to find a probability formula of combining both individual
probability p_i and constraint (k,N) in order to prove my intension in
the above.

Honestly, I didnot understand why your question is different from mine.
Thanks again for your help.

Regards,

---

Request for Question Clarification by mathtalk-ga on 05 Sep 2004 08:15 PDT

Hi, dogwood-ga:

In stating the probability for "no constraint in k" as:

           m
    1 - PRODUCT (1 - p_j)
         j = 1

it appears that you are perhaps using knowledge of the "primitive
test" results to choose the m machines with the least probability p_j.
 If the m machines are selected "at random" without using such
knowledge, your chance of getting at least one bad machine would
instead be an average (mean) of expressions like the above, but taking
into account all possible choices of m machines out of N.

So a clarification on your part of how the "primitive test" results
are to be used is needed, even to resolve the simpler question with
"no constraint in k".

regards, mathtalk-ga

---

Clarification of Question by dogwood-ga on 07 Sep 2004 11:18 PDT

Hi, mathtalk-ga,

Thanks for your question.

As you said, my thought is to pick up the m machines with the least
individual probability because it makes the chance of selecting one
bad machine lower than other options. Because of the varied m,k,N, I
may not be able to prove my intent of that there exists the advantage
with the individual probability over without that parameter.

I'm thinking, though the primitive testing doesnot consider the constraint k,
we may be able to can adjust the individual probability with the
consideration of constraint k after then. For example, treating the
primitive testing has the error, the constraint (N & k) can be used to
correct the error. By doing that, maybe we can associate the (p_1,
..., p_N) with the constraint k. Am I in the right track?

Regards,

---

Clarification of Question by dogwood-ga on 15 Sep 2004 12:39 PDT

Hi, 
Any further thoughts? Thanks,

Regards,

---

Request for Question Clarification by mathtalk-ga on 15 Sep 2004 18:37 PDT

Hi, dogwood-ga:

I think my initial focus was on trying to pin down what "the" problem
is here, but my conclusion, which I hope you share, is that there is
enough room for interpretation to make several problems... which of
course is what makes it interesting.

I could post an Answer that analyzes one quite specific interpretation
of the data in a way that I think is consistent with your
understanding.  If you wish, I'll be glad to proceed.

regards, mathtalk-ga

---

Clarification of Question by dogwood-ga on 16 Sep 2004 07:16 PDT

Hi, Mathtalk-ga,

As you know that I'm looking for a probability solution which takes
into account both the individual probability and the constraint (k,N).
I'm glad that you understand the point. Would you please share your
specific interpretation of the data and your question behind the
interpretation. Thanks,

Regards,

---

Request for Question Clarification by mathtalk-ga on 16 Sep 2004 19:52 PDT

Hi, dogwood-ga:

Well, here's the story I built around your problem.  It's got
unnecessary details, of course, but it puts each piece of the data in
a context.

Your company has N PC's (machines) which are known to be in working
order at the end of the business day, dedicated to the computation of
digits of Euler's constant.

Overnight k persons come into the facility and log onto the Internet
with their respective random choices of k machines in order to play a
Doom 3 tournament.  As they are eliminated they leave and the machine
is disconnected from the Internet.

In the morning the breach of security is detected, and their exists a
risk of viral contamination for each unauthorized use of a machine. 
The machines risk of infection, conditioned on having been used, can
be estimated accurately (the values p_1,..,p_N), but it is not known
which machines were used.

Therefore at most k machines are now in an unusable state, depending
on whether the corresponding risk of viral contamination was realized.

We can now compute the likelihood that at least one of m machines
chosen at random is infected, as well as the likelihood that at least
one of the m machines with the smallest probability values p_j is
infected.

Your thesis is that you are better off using the information about the
p_j's than choosing machines at random.  Of course the improved risk
mitigation from using this information depends on the p_j's, and
specifically the improvement is nil if all the p_j's are equal.

regards, mathtalk-ga

---

Clarification of Question by dogwood-ga on 17 Sep 2004 04:08 PDT

Hi, mathtalk-ga,

Your interpretation and question are very close to mine. Please go
ahead to proceed it. Thanks,

Regards,

---

Clarification of Question by dogwood-ga on 22 Sep 2004 07:00 PDT

Hi, mathtalk,

I'm looking forward to your answer. Thanks,

Regards,

---

Clarification of Question by dogwood-ga on 27 Sep 2004 14:44 PDT

Hello,

I wonder if the question is unsolvable or the list price
underestimates the time on it. If it is the second case, I'll willing
to know the reasonable time to solve this question and may readjust
the price with my budget. Thanks,

---

Request for Question Clarification by mathtalk-ga on 29 Sep 2004 10:39 PDT

Hi, dogwood-ga:

Let's spell out the results for the case K = 1.  Similar but more
complicated results can be given for larger K, but this gives a
qualitative feel for the situation.  Please confirm whether or not
such results are useful to you.

Assuming that the probabilities p_i are labelled in increasing order
and independent of the chance of a machine being chosen for
"unauthorized use", then the chance of picking that machine in your
group of M is M/N.  The chance of picking "at least one machine" in
"bad condition" is then:

   P  =  (M/N) * (1/N) * SUM p_i FOR i = 1 to N

      =  (M/N) * AVERAGE {p_1,..,p_N}

if no use is made of the "susceptibility" probabilities p_i, versus:

   P' =  (M/N) * (1/M) * SUM p_i FOR i = 1 to M

      =  (M/N) * AVERAGE {p_1,..,p_M}

if the probabilities p_i are used to select the M machines with least
"susceptibility".

The reduction of P' with respect to P is proportional to the average
of the M least susceptibility values divided by the average of all of
them.

Since we know nothing about the probabilities {p_1,..,p_N}, the
formulas which can be given for larger values of K cannot be
simplified very far.  However one can certainly show that P' is less
than or equal to P, with equality only in the case that all the p_i's
are equal.  The case K = 1 is typical in this respect.

regards, mathtalk-ga

It's hard to know from the problem's wording how to combine the
information that "up to k" machines are in bad shape with the
estimated probabilities on individual machines.  Yet the way of
combining them seems central to this question.

Knowing that at most k machines are in bad shape, for k < N, implies
that the actual probabilities of specific machines being "out of
service" are not independent.  For example, any one machine presumably
has a positive probability of being in bad shape but the probability
that all are (k < N) is zero.  So the probability of the conjunction
event is _not_ the product of the individual probabilities (hence not
independent).

If one ignores the constraint that at most k machines are in bad
shape, one might proceed as follows.  The probability at least one of
the chosen machines is in bad shape is complementary to the
probability that all the chosen machines are in good shape.  For any
particular choice of m machines, the probability of all being in good
shape, assuming independence of those events, is the product of the
individual machines being in good shape, i.e.

PRODUCT (1 - p_i(j)) where j = 1,..,m

and i(j) denotes the j'th choice out of m in this particular
selection.  These products then have to be averaged over all possible
choices of m machines out of N.  Assuming that all machines are
equally likely to be chosen, without replacement, this gives a simple
equiprobability model for the chances of selection; the averaging is
then an "equally weighted" mean.

The constraint of at most k machines being in bad condition can be
worked into the solution, but more careful wording is needed to
understand how that relates to the values p_i "given".  For example,
we could have a model in which one independently selects m machines
"to use" and k machines to (potentially) be out of service, followed
by applying the probabilities p_i shown to determine (for any machines
chosen for both groups) if at least one is actually bad.  If this were
a homework problem, most likely that would be the interpretation the
student was expected to pursue.

Of course if one already had the "primitive testing" results, in a
practical sense that knowledge might bias the selection of machines to
use (toward those with the smallest chance of being in bad shape).

regards, mathtalk-ga

Good analysis. The central point is how to combine the k into the 
probabilities of the selected machines. My feeling is that both
k and N could affect the overall probability of that at least one 
machine in bad shape is among the selected m machines even if the 
individual probability is not based on the k and N. Of course, 
0<m<N and 0<k<N, but both m>k or m<k may be true. Thanks,

Regards,

dogwood--

There is a problem.  You have provided two pieces of information:

1) The probablity each machine is in bad condition is (p_1, p_2, ..., p_N).
      (presumably none of the p's are equal to zero).

2) At most k machines are in bad condition.

These are inconsistent with each other.  Unless you allow that N-k of
the p's are equal to zero, or that the p for each machine depends on
the conditions of the others, this question is unanswerable.

Here is a question that doesn't contradict itself:

The probablities of badness are known to be (p_1, p_2, ..., p_N).  One
day, the machines are checked, and X of them are bad.  I won't tell
you what X is, but I will tell you that X is less than or equal to k. 
Now, if we select m machines at random, what is the probablity that at
least one is bad?

Is this what you mean?

Note: I haven't said anything here that mathtalk didn't already say,
but maybe it's a useful rephrasing.