Probability to draw a black ball in a set of black and white balls with mixed replacement conditions

When a black ball is drawn, it is not replaced in the set, but white balls are replaced.

I have thought of this, with the notations:

  • b, w the initial number of black and white balls
  • xi=(bi)/(b+wi)

The probability of drawing a black ball Pb(n) after n draws:

Pb(0)=x0Pb(1)=(1x0)x0+x0x1Pb(2)=(1x0)2x0+x0x1(1x0)+x0x1(1x1)+x0x1x2Pb(n)=n1k=0(ki=0xink termsi<=k1xi)

This sum seems infinite with n, even if some terms are null since xib=0

Except b=1:
Pb(n)=(1x0)nx0

For b=2:
Pb(n)=x0(1x1)n+x0x1i+j=n1(1x0)i(1x1)j

Is there a known solution to this problem?

Answer

Let the initial number of white balls be w and black balls be b. The question describes a Markov chain whose states are indexed by the possible numbers of black balls i{0,1,2,,b}. The transition probabilities are

pw(i,i)=ww+i,pw(i,i1)=iw+i.

The first describes drawing a white ball, in which case i does not change, and the second describes drawing a black ball, in which case i is reduced by 1.

From now on let us drop the explicit subscript "w," taking this value as fixed throughout. The eigenvalues of the transition matrix P are

e=(ww+bi, i=0,1,,b)

corresponding to the matrix Q given by

q_{ij} = (-1)^{i+j+b} (j+w) \binom{b}{j} w^{j-b} \binom{b-j}{i} (b-i+w)^{b-j-1}

whose inverse is

(q^{-1})_{ij} = \frac{w^{b-i} \binom{j}{b-i} (b-j+w)^{i-b}}{\binom{b}{b-i}}.

That is,

\mathbb{P} = \mathbb{Q}\ \text{Diagonal}(\mathbf{e})\ \mathbb{Q}^{-1}.

Consequently the distribution after n transitions out of the state b is given by the vector of probabilities

\mathbf{p}_n = (0,0,\ldots,0,1) \mathbb{P}^n = (0,0,\ldots,0,1)\mathbb{Q}\ \text{Diagonal}(\mathbf{e}^n)\ \mathbb{Q}^{-1}.

That is, the chance there are i black balls left after n draws is

p_{ni} = \sum_{j=0}^b q_{nj} e_j^n (q^{-1})_{ji}.

For example, starting with any number of white balls and b=2 black balls, the probability distribution after n \ge 1 draws is

\eqalign{
\Pr(i=2) &= p_{n2} &= \frac{w^n}{(2+w)^n} \\
\Pr(i=1) &= p_{n1} &= \frac{2w^{n-1}}{(1+w)^{n-1}} - \frac{2 w^{n-1}(1+w)}{(2+w)^n} \\
\Pr(i=0) &= p_{n0} &= 1 - \frac{2 w^{n-1}}{(1+w)^{n-1}} + \frac{w^{n-1}}{(2+w)^{n-1}}.
}

Figure

The curves in this figure track the probabilities of the states i=0 (blue), i=1 (red), and i=2 (gold) as a function of the number of draws n when w=5; that is, the urn begins with two black balls and five white balls.

The state i=0 (running out of black balls) is an absorbing state: in the limit as n grows without bound, the probability of this state approaches unity (but never exactly reaches it).

Attribution
Source : Link , Question Author : caub , Answer Author : whuber

Leave a Comment