>>73
Your post was kind of difficult to read so I will try to summarise the problem and solution in my own words. I also think you made a typo, so my reccurance relation looks very slightly different to yours, but the solution is the same.
Problem
You have two boxes, box #1 and box #2. You also have a bag with an unlimited number of balls. At time 0, box #1 has one ball and box #2 has one ball.
In every iteration:
- Choose a ball at random from the set of balls that are in the boxes.
- Take a new ball from the bag and put it into the box where the chosen ball was.
So at time
, there are
balls in both boxes. Each box has between
and
balls (inclusive).
Let
denote the probability that box #1 has exactly k balls at time t.
So by the initial conditions:
-
if
-
otherwise
Derive a closed form expression for
.
Solution
We know that at time
there were
(t−1)+2=t+1
balls in both boxes.
At time
, how can box #1 come to contain
balls? There are two cases:
- at time
it had
balls and was chosen
- at time
it had
balls and was not chosen
This leads to the following reccurence relation
pt,k=pt−1,k−1t+1k−1+pt−1,kt+1t+1−k
which has the solution by induction on
pt,k=t+11
where
1<=k<=t+1
.
Base case for
is trivial.
=pt−1,k−1t+1k−1+pt−1,kt+1t+1−k
=(t−1)+11t+1k−1+(t−1)+11t+1t+1−k
by inductive assumption and because
so no problems with dividing by 0
=t(t+1)k−1+t(t+1)t+1−k
=t(t+1)k−1+t+1−k
=t(t+1)t
=t+11
which is what we wanted.
Now for some values of
, namely
and
this is somewhat an obvious result because in these cases, we have to look at the probability of choosing one box repeatedly which is just
(t+1)!t!=t+11
, but for the other cases it is not so obvious. Drawing a tree diagram helps verify the result, I did it up to
.
Cool problem overall anon :)
