I came up modeling this urn problem, which I am not able to entirely solve. Here is the problem.
Problem statement:
Initially: Suppose we have an urn containing $n$ balls. At first, we have $1$ black ball, and $n-1$ white balls. We denote by $\mathcal{N}_b^t$ and $\mathcal{N}_w^t$ the number of black balls in the urn at time $t$ and the number of white balls at time $t$ respectively. We always have $\mathcal{N}_b^t + \mathcal{N}_w^t = n$.
How the game is played: The player chooses one ball uniformly at random, we suppose that all balls can be selected with probability $n^{-1}$. The player paints this ball in red, and puts it back in the urn. The player can repeat this $1$ or more times. This process is considered to be 1 round. We denote by $\mathcal{N}_r^t$ the number of red balls at the end of round $t$.
Before the next round, all red balls are painted in black, all black balls remain black, and all white balls remain white.
At round $1$, the player is allowed to choose $f \geq 1$ balls from the urn. At round $t+1$, the player is allowed to choose $f \cdot \mathcal{N}_r^t$ balls with replacement from the urn. The game stops when $\mathcal{N}_b^t = n$.
Quantities of interest:
- What is the proportion of black balls, i.e., $\frac{\mathcal{N}_b^t}{n}$ at each round?
- What is the proportion of red balls, i.e., $\frac{\mathcal{N}_r^t}{n}$ at the end of each round?
- What is the expected time $\mathbb{E}[T]$ for which $\mathcal{N}_b^t = n$?
My work so far:
I started with the second question, the proportion of red balls. I started to look at the probability that $P(\mathcal{N}_r^0 = i)$ when $i = 1, \ldots, f$. This probability is computed as follows. The total number of balls that can be selected is $n^f$. We choose $i$ balls among $n$ to be red, which is given by $\binom{n}{i}$. We are allowed to pick $f$ balls, of which exactly $i$ must be red. We partition the $f$ balls we pick into $i$ subsets that will represent the $i$ red balls. Denoting by $S(\cdot, \cdot)$ the Stirling numbers of the second kind, we have $S(f, i)$ different partitions. And finally for each subset, we assign one red ball, we have $i!$ ways to do this. Hence $$P(\mathcal{N}_r^0 = i) = \frac{\binom{n}{i} \cdot i! \cdot S(f, i)}{n^f}.$$ Writing $(n)_i = n \cdot (n-1) \cdots (n-i+1)$, we have $$P(\mathcal{N}_r^0 = i) = \frac{(n)_i \cdot S(f, i)}{n^f}.$$
When $i = 0$, $S(f, i) = 0$ and when $i > f$, $S(f, i) = 0$. Hence we can quickly verify that the sum of the probabilities is equal to $1$. $$\sum_{i = 1}^{f} P(\mathcal{N}_r^0 = i) = \frac{1}{n^f} \sum_{i=1}^f (n)_i \cdot S(f, i) = \frac{1}{n^f} \cdot n^f = 1.$$
More generally, the probability of having exactly $i$ red balls at round $t+1$ is given by $$P(\mathcal{N}_r^{t+1} = i) = \frac{(n)_i \cdot S(f \cdot \mathcal{N}_r^{t}, i)}{n^f}.$$ We can go a bit further than this by using the law of total probability, $$P(\mathcal{N}_r^{t+1} = i) = \sum_{i_t=1}^{f \cdot \mathcal{N}_r^{t}} P(\mathcal{N}_r^{t+1} = i \mid \mathcal{N}_r^{t} = i_t) \cdot P(\mathcal{N}_r^{t} = i_t).$$ Going even further up to $\mathcal{N}_r^{0}$, we obtain $$P(\mathcal{N}_r^{t+1} = i) = \sum_{i_t=1}^{f \cdot \mathcal{N}_r^{t}} \sum_{i_{t-1}=1}^{f \cdot \mathcal{N}_r^{t-1}} \cdots \sum_{i_2=1}^{f \cdot \mathcal{N}_r^{2}} \sum_{i_1=1}^{f \cdot \mathcal{N}_r^{1}} P(\mathcal{N}_r^{t+1} = i \mid \mathcal{N}_r^{t} = i_t) P(\mathcal{N}_r^{t} = i_t \mid \mathcal{N}_r^{t-1} = i_{t-1}) \cdots P(\mathcal{N}_r^{2} = i_2 \mid \mathcal{N}_r^{1} = i_1) \cdot P(\mathcal{N}_r^{1} = i_1),$$ where $P(\mathcal{N}_r^{1} = i_1)$ is entirely determined by the initial condition that we can choose $f$ balls. I don't want to write the probabilities in the expression I found above, because I did not find a nicer form.
So we can compute the expected value of $\mathcal{N}_r^{t+1}$. We have $$\mathbb{E}[\mathcal{N}_r^{t+1}] = \sum_{i = 1}^{f^{t+1}} i \cdot P(\mathcal{N}_r^{t+1} = i).$$ The sum goes up to $f^{t+1}$ because in the first round, we can pick at most $f$ red balls, in the second round $f^2$, and so on. This is not a really nice form to compute... So as before, using the total expectation law, we obtain
$$\begin{align*}\mathbb{E}[\mathcal{N}_r^{t+1}] &= \sum_{i=1}^{f^t} \mathbb{E}[\mathcal{N}_r^{t+1} \mid \mathcal{N}_r^{t} = i] \cdot P(\mathcal{N}_r^{t} = i)\\ &= \sum_{i=1}^{f^t} n \left( 1 - \left( 1 - \frac{1}{n} \right)^{f \cdot i} \right) \cdot P(\mathcal{N}_r^{t} = i) \end{align*}$$
I quickly explain how to obtain this formula for the conditional expected value. The player is allowed to draw $f \cdot i$ balls from the urn. Consider the random indicator variable $X_j$ that returns $1$ if the $j$-th ball is picked, $0$ otherwise. We have $P(X_j = 0) = \frac{n-1}{n} = 1 - \frac{1}{n}$. Now the probability that $P(X_j = 0)$ after $f \cdot i$ picks is $\left( 1 - \frac{1}{n} \right)^{f \cdot i}$. So the probability that $P(X_j = 1)$ after $f\cdot i$ picks is $1 - \left(1 - \frac{1}{n} \right)^{f \cdot i}$. Now $\mathcal{N}_r^{t+1} = \sum_{j = 1}^n X_j$, thus (as the probability of $X_j$ depends on $\mathcal{N}_r^{t}$) $$\mathbb{E}[\mathcal{N}_r^{t+1} \mid \mathcal{N}_r^{t} = i] = \mathbb{E}\left[\sum_{j=1}^{n} X_j \right] = \sum_{j=1}^n \mathbb{E}[X_j] = n \left( 1 - \left( 1 - \frac{1}{n} \right)^{f \cdot i} \right).$$
Okay so now we have established that $$\mathbb{E}[\mathcal{N}_r^{t+1}] = \sum_{i=1}^{f^t} n \left( 1 - \left( 1 - \frac{1}{n} \right)^{f \cdot i} \right) \cdot P(\mathcal{N}_r^{t} = i).$$ Define $\varphi: \mathbb{R} \to \mathbb{R}$, $x \mapsto n\left( 1 - \left( 1 - \frac{1}{n} \right)^{f \cdot x} \right)$. Then clearly $$\mathbb{E}[\mathcal{N}_r^{t+1}] = \sum_{i=1}^{f^t} \varphi(i) \cdot P(\mathcal{N}_r^{t} = i) = \mathbb{E}[\varphi(\mathcal{N}_r^{t})].$$ Now $\varphi$ is a concave function, hence by Jensen's inequality we have that $$\mathbb{E}[\mathcal{N}_r^{t+1}] = \mathbb{E}[\varphi(\mathcal{N}_r^{t})] \leq \varphi \left( \mathbb{E}[\mathcal{N}_r^{t}] \right) = n\left( 1 - \left( 1 - \frac{1}{n} \right)^{f \cdot \mathbb{E}[\mathcal{N}_r^{t}]} \right).$$ Now I would like to show that the difference $\varphi \left(\mathbb{E}[\mathcal{N}_r^{t}]\right) - \mathbb{E}[\mathcal{N}_r^{t+1}] $ is small.
Conjecture: For every $n \geq 1$, for every $f \geq 2$, $$\varphi \left(\mathbb{E}[\mathcal{N}_r^{t}]\right) - \mathbb{E}[\mathcal{N}_r^{t+1}] \leq 1.$$ (The bound may be tighter than this, but it would be enough. Even if my bound is wrong, and it is $10$ instead of $1$ I would be satisfied).
This is where I am stuck, I have no idea how to prove this.
If you have read this post until here, thank you. And if you find the time to help, thank you even more :).
For the other questions, I have not given much thought yet, and this post is already long.