# Urn problem: replacing white balls with black once selected

I'm trying to find the probability of an outcome where, using the traditional example, white balls are replaced by black balls once selected.

Initially I have $n$ white balls and $\mu$ samples. I want to find the probability of selecting $b$ of these, whereby after selecting a white ball it is replaced by a black ball.

To complicate the matter, there is a probability $1-\eta$ per sample that I won't successfully select a white ball ($\eta$ representing the chance of successfully picking a ball), even if the bag is filled only filled with white balls. This $\eta$ is uniform across all $n$ balls.

By sitting and analyzing the probability trees, I have devised the following equation, but I believe this can be entirely rewritten by someone more competent with probabilities. The first term (the product) creates the probability of the first $b$ samples all being correct. The second term creates every conceivable combination of failure that can happen and still manage $b$ successfully.

$P_{output}(\mu,b,n)= \left(\prod\limits_{i=0}^{b-1}\eta\frac{n-i}{n}\right)\cdot\left(1+\sum\limits_{j_1=0}^{b-1}\left(1-\eta\frac{n-j_1}{n}\cdot\sum\limits_{j_2=j_1}^{b-1}\left(1-\eta\frac{n-j_2}{n}\cdot \cdots\sum\limits_{j_{\mu-b}=j_{\mu-b-1}}^{b-1}\left(1-\eta\frac{n-j_{\mu-b}}{n}\right)\right)\right)\right)$

Thank you in advance for your help!

Edit: I'm wondering whether this can be represented as an urn problem, where there are $n$ different coloured sub-urns inside this urn. Inside each sub-urn there are $\eta/\eta=1$ white balls, and $(1-\eta)/\eta$ black balls. So, you need the probability of selecting $b$ different sub-urns multiplied by the probability of successfully selecting the one white ball from that urn, for $\mu$ samples. Does that work?

As per the answer you provided, you can express this using Markov chains, with states $0$ to $n$, and state $i$ indicating you've already put $i$ black balls into the urn. The chance of moving from state $i$ to state $j$ after a single selection is then the $i^{\textrm{th}}$ row and $j^{\textrm{th}}$ column of

$P = \begin{pmatrix} (1-\eta) & \eta & 0 & 0 & \cdots & 0\\ 0 & (1-\frac{n-i}{n}\eta) & \frac{n-i}{n}\eta & 0 & \cdots & 0 \\ 0 & 0 & (1-\frac{n-i}{n}\eta) & \frac{n-i}{n}\eta &\cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}.$

We can then find the probability of being in state $i$ after $\mu$ samples, from initial state $0$, as the expression

$(1,0,0,\ldots,0) P^{\mu} = l^T p^{\mu}.$

$P^{\mu} l,$ as you suggested, would give you the vector whose $i^{\textrm{th}}$ element is the probability of ending in state $0$ starting from state $i,$ which can easily to be shown to be the vector

$((1-\eta)^{\mu},0,\ldots,0).$

After some analysis I've discovered this can be represented as a Markov chain with bidiagonal transition matrix:

$\mathbb{P} = \begin{pmatrix} (1-\eta) & \eta & 0 & 0 & \cdots & 0\\ 0 & (1-\frac{n-i}{n}\eta) & \frac{n-i}{n}\eta & 0 & \cdots & 0 \\ 0 & 0 & (1-\frac{n-i}{n}\eta) & \frac{n-i}{n}\eta &\cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}$

where $i$ is the row number (from $i=0$ to $i=b$). By raising this transition matrix to the power $\mu$, and with initial state $l$ (where rows go from $i=0$ to $i=b$):

$l = \begin{pmatrix} 1\\ 0\\ \vdots\\ 0 \end{pmatrix}$

it is possible to find probability as the population of the final row in the equation:

$a = \mathbb{P}^\mu l$