Re: An interesting problem in probability

From: Herman Rubin (hrubin_at_odds.stat.purdue.edu)
Date: 08/30/04 

Date: 30 Aug 2004 08:53:43 -0500

In article <cguosj$d3i$1@newsreader.wustl.edu>,
Sailesh Kumar <sailesh@arl.wustl.edu> wrote:
>Hi,
> I need to do some computation for a cache architecture. I have arrived at
>a simplified model and I need help to get it solved. Here is the problem.

> Balls are being put into and removed from a bucket, one arrival and one
>departure in each unit time. Balls that are arriving have equal probability
>that they can have any color from b different colors.
> The bucket has N balls initially, with equal number of balls of every b
>color. N is divisible by b can be assumed. hence N/b balls of each color.

> Now, when this process is carried out for very long time say T (T is
>trillions), how many times will the bucket be having balls of only c colors
>(c < b).
> In other words, after a long time and in steady state, whats is the
>probability that the bucket will have balls of only c colors (c < b).

The steady state solution does not depend on N/b being
an integer. It is the probability that if N balls are
selected at random, with the probability that only c
colors are present.

The Bonferroni formula is the precise one to use. What
you need to do is to take the sum of the probabilities
that a set of c colors is present; this will, however,
include probabilities for less than c. Thus the
appropriate multiple for c-1 has to be subtracted.
But this overdoes it for c-2, etc.

If the process maintains the number of balls in the
bucket as a stationary Poisson process with mean h, the
probability that any particular color is not present in
the steady state is exactly exp(-h/c), and the number of
colors will have a binomial distribution. This gives an
approximation if h is set equal to N. 

-- 
This address is for information only.  I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@stat.purdue.edu         Phone: (765)494-6054   FAX: (765)494-0558

Relevant Pages

  • Re: A simple but confusing question
    ... In practice, the prior that you use, provided it is relatively flat, ... affects the probability of the next ball being white only for small n. ... knowledge concerning the proportion of white balls in the bucket; ...
    (sci.stat.math)
  • Re: A simple but confusing question
    ... 100 white balls, what is the probability that the next one will ... by the meaning of CIs, and they often feel a measure of post-data ... a ball from another bucket, whose contents are, say, 5 black and 5 ... probability of the above mooted die showing '6' is not exactly 1/6 ...
    (sci.stat.math)
  • Re: Which is rarer?
    ... Comparing actual events to get the probability ... Waqar Younis takes a wicket every 30 balls ... A bowler can bowl a max of 60 deliveries. ... there are always four or more wickets left for him to take. ...
    (rec.sport.cricket)
  • Re: Randomness
    ... the selections are not _independently_ random because once a ball is ... remaining balls is changed. ... Also, re the fair coin, a system can be random even if its states do ... not all have the same probability. ...
    (talk.origins)
  • Re: Probabilities and complex numbers.
    ... > A box contains 2 red balls and 3 white balls. ... > 1) The probability for which two red balls are included in the set of 4 ... A very concrete way to understand it is with a tree diagram showing all ...
    (sci.math)
Loading