Probabilistic bins and balls question:

I have n sets of balls, each set consisting of d balls of the same
unique color (so there are n different colors). I throw all balls
randomly and uniformly
into r*n bins.

After I've done this, I follow the following procedure for removing
balls.
Each time I see a bin that has one ball, I remove that ball and the
other
d-1 balls that have the same color.

My goal is to **PROVE** that with arbitrarily high probability (in d)
I can remove all balls. I am expecting that r will be a function of d.
I need a concrete derivation of the relationship between probability
of success
and the values of d and r.

Petar

---

Request for Question Clarification by rbnn-ga on 01 Nov 2002 00:30 PST

Two questions: 

1. What do you mean by "I am expecting that r will be a function of d"
. That is, do you know this function? I don't quite see what you are
getting at here.

2. What is a "concrete derivation"? Do you mean a mathematical proof?
Or would a simulation and graph suffice?

---

Request for Question Clarification by rbnn-ga on 01 Nov 2002 00:34 PST

Another thing I do not understand is the meaning of the phrase 

"My goal is to **PROVE** that with arbitrarily high probablity (in d)
I can remove all balls."

What does "arbitrarily high probability (in d)" mean. For a given r,
n, and d there is a fixed probability P(r,n,d) that you will win. What
property of P(r,n,d) are you asking to be shown?

---

Clarification of Question by petar-ga on 01 Nov 2002 01:34 PST

1: I meant that the goal of this question is to prove some 
theorem which will sound like this: For any desired limit l on the
probability of failure, when d=*** and r=**, and any n, the
probability of failure is less than l.

2: I need a solid mathematical proof to the theorem. No experimental
results.

3: Ansewered in (1)

4: I want for every l to exist d and r, such that for all n: P(r,n,d)<l

---

Request for Question Clarification by rbnn-ga on 01 Nov 2002 01:52 PST

Thank you for the clarification.

It is possible (fairly easy) to show that for any q such that 0<q<1
one can choose r and d such that for all n the probability of winning
is greater than q. One simply chooses d=1 and r sufficiently high that
the probability that some bin initially has exactly one ball is
greater than q . Is this what you are looking for?

---

Clarification of Question by petar-ga on 01 Nov 2002 07:24 PST

This is not what I am looking for. It is fairly obvious that one can
prove that the probabibility of removing one color can be pushed close
to 1 (i.e. the probability that some bi has 1 ball). 

What I am looking for is a proof that **all** colors (i.e. all balls)
can be removed.

It is also as easy to show (using expected value and a simple
martingale)
that regardless of how big d and r are, there will be at least a
constant(dependent on d and r) times n number of
bins that have more than one ball. THerefore, you cannot remove all
balls
at the first step. For your intuition, when d=3 and r=4 the process 
(experimentally) never fails (for any n).

The way the process will go is this:
Immediately after you throw all balls, there will be some number of
bins with one ball and some number of bins with more than one ball.
When you get rid of all balls (and the balls of their color) from
the bins with one balls, then some of the bins that had more than 
one ball will now have one ball and you will be able to remove some
more
colors. This process will continue in this cascading fashion until
completion.

Never forget also, that we are interested in the outcome of the
process
as n is large enough. I.e. we are looking for asymptotic results,
which
makes the situation easier for analysing.

---

Clarification of Question by petar-ga on 01 Nov 2002 07:27 PST

What I meant to say with:
"
It is also as easy to show (using expected value and a simple
martingale)
that regardless of how big d and r are, there will be at least a
constant(dependent on d and r) times n number of
bins that have more than one ball. THerefore, you cannot remove all
balls
at the first step. For your intuition, when d=3 and r=4 the process  
(experimentally) never fails (for any n).
"

The "(for any n)" at the end should say for any n large enough.

---

Clarification of Question by petar-ga on 01 Nov 2002 08:41 PST

Even better, I know it can be proven that, for fixed d=3, r=4
the probability that the process doesn't success is inversely
proportional to a polynomial in n!

---

Clarification of Question by petar-ga on 01 Nov 2002 08:42 PST

So let me phrase the theorem that needs to be proven:

For d=3 and r=4, the process fails to remove all balls with
probability inversely proportional to a polynomial n.

---

Clarification of Question by petar-ga on 01 Nov 2002 08:44 PST

I meant "polynomial in n" above.

Let's assume that the n sets of d balls are independently and
uniformly distributed in the r bins.  If the arrangement of balls is
such that they cannot all be removed through application of the
indicated procedure, let's describe that arrangement as "locked".

It sounds to me as if petar-ga wants an estimate:

Pr( n sets of d balls in r bins are "locked") <= F(d,r)

where F(d,r) has no functional dependence on n, and LIMIT F(d,r) AS r
-> +00 is zero for all d.  In more technical terms, this would be an
estimate of the probability that is uniform in n.  This is stated
quite clearly by petar-ga in point (4) above of a clarification.

Such an estimate cannot be given, essentially because, for given d,r:

Pr( n sets of d balls in r bins are "locked")

tends to 1 with increasing n.  Therefore we cannot, for any given d,
find a value for r that makes the probability of being locked
sufficiently small for _all_ n.

Here's a rough argument.  Consider n = 2m as m pairs of sets of d
balls.  For given d,r the probability that a single pair of sets is
"locked" is positive, and the probability of the pair being "unlocked"
is less than 1.  Since the probability that all m pairs are "unlocked"
is that to the m'th power (by the independence of the distributions),
the probability of the 2m sets being collectively "unlocked" (which is
smaller than for all m pairs considered separately) tends to zero as m
goes to infinity.  Hence the probability of their being "locked" tends
to 1 as m (or n) goes to infinity.

If further details of this (negative) "asymptotic" result are useful
to petar-ga, I would be happy to let rbnn-ga fill them in, if that is
mutually agreeable to you both.

regards, mathtalk-ga

mathtalk-ga: Err, no, since it's your work I'd prefer you submit the
answer actually, if you want . (That I ask for clarification does not
imply I intend to answer the question; I was [and perhaps still am]
trying only to understand the question in order to determine whether I
could or should answer it.)

The mistake in your argument is that you say that there are r bins.
The number of bins is n*r.

Moreover, As I say in one of the clarifications it turns out that the
actual result is stronger. For any well chosen d and r (e.g. d=3 and r=4)
the probabibility that the experiment fails (or locks as you say) decreases
as n increases. More specifically, it decreases as 1/p(n), where
p(n) is a polynomial in n.

The argument tha we are looking for is not at all shallow or very simple.

The result, as I say, is not as easy as computing some probabilities
directly, yet it is a standard result somewhere out there, so it
doesn't involve too
much complication.  To facilitate any further conclusion, concentrate
on
the following specific theorem that needs to be proved.

For d=3 and r=4, the probability of failure to remove all balls is
proportional to 1/p(n), where p(n) is a polynomial in n.

Okay, I see that my mistake in considering r bins instead of rn bins
badly obscured the interesting nature of the problem.

Still, shallow and superficial methods have their place!  I think it
is possible to get an upper bound:

Pr(n sets of d balls in r bins are "locked") <= F(d,r,n)

which is a rational expression F in d,r,n using a recurrence relation
approach.  One might then get the proper limit F(d,r) for F(d,r,rn) as
n tends to infinity, ie. limit F(d,r) tends to zero as r tends to
infinity.

regards, mathtalk-ga

Yes, I will be happy if you get any sort of upper bound like that.
THen you will have to union bound your upper bound over all possibble
subsets of the colors and if that proves to be inversely proportional to
n, you will be done. I will be happy with a result like this.