Replacement only when 'prize' is found

Question

There are $a$ balls in a jar. One is gold, the rest are black. Balls are taken from the jar. If a black ball is taken, it is not replaced. If a gold ball is taken, all balls are replaced.

I am interested in finding a closed form solution for the expected number of gold balls taken after $k$ balls have been taken in total.

---

My approach so far is to form a recurrence relation with $E_n =$ the expected number of gold balls taken after $n$ balls have been taken in total.

The starting condition is

$$E_0 = 0$$

Conditioning on getting the gold ball on the $i$th try (probability $\frac{1}{a}$),

For $0 < k < a$, $$E_k = \left(\frac{1}{a}\right)\left(\sum^{k}_{i=1}1+E_{k-i}\right)$$ For $k \geq a$, $$E_k = \left(\frac{1}{a}\right)\left(\sum^{a}_{i=1}1+E_{k-i}\right)$$

The relation can be simplified to

$$E_{<0} = -1, E_0 = 0$$ $$E_{k>0} = 1+\left(\frac{1}{a}\right)\left(\sum^{a}_{i=1}E_{k-i}\right)$$

I'm not sure where to go from here, or if this is the best approach.

---

Another thing I'm a bit confused on is some intuition. When $a=2$ and the jar is full, the expected number of balls it takes to get the golden ball is $\frac{1}{2}+\frac{2}{2}=\frac{3}{2}=1.5$, I believe.

On the other hand, if the above recurrence is correct, then for $a=2$, $E_3=\frac{15}{8}=1.875$. So you expect $1.875$ gold balls after taking $3$ balls.

I can't figure out why this is less than $2$, intuitively, which leads me to be unsure about my recurrence. On the other hand, I notice as $k$ grows large (from plotting the recurrence), the difference between the expected number of gold balls every $3$ balls taken tends to $2$ from below.

What I've said above seems to generalise for all $a$.

Table of recurrence for $a=2$. Left column is $k$, right is $E_k$.

Answer 1

Let $E_{a,b,k}$ be the expected number of gold balls drawn when you have $a$ balls total, $b \le a$ balls in the jar, and $k$ draws. Then $E_{a,b,0} = E_{a,0,k} = 0$ and for $b>0$ and $k>0$ conditioning on the next ball drawn (gold or black) yields recurrence $$E_{a,b,k} = \frac{1}{b}(1 + E_{a,a,k-1})+\frac{b-1}{b}E_{a,b-1,k-1}$$

Here are the resulting values of $E_{a,a,k}$ for $a,k \le 10$: \begin{matrix} a\backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 0 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 \\ 1 & 0.000 & 1.000 & 2.000 & 3.000 & 4.000 & 5.000 & 6.000 & 7.000 & 8.000 & 9.000 & 10.000 \\ 2 & 0.000 & 0.500 & 1.250 & 1.875 & 2.563 & 3.219 & 3.891 & 4.555 & 5.223 & 5.889 & 6.556 \\ 3 & 0.000 & 0.333 & 0.778 & 1.370 & 1.827 & 2.325 & 2.841 & 3.331 & 3.832 & 4.335 & 4.833 \\ 4 & 0.000 & 0.250 & 0.563 & 0.953 & 1.441 & 1.802 & 2.190 & 2.596 & 3.007 & 3.399 & 3.798 \\ 5 & 0.000 & 0.200 & 0.440 & 0.728 & 1.074 & 1.488 & 1.786 & 2.103 & 2.436 & 2.777 & 3.118 \\ 6 & 0.000 & 0.167 & 0.361 & 0.588 & 0.853 & 1.161 & 1.522 & 1.775 & 2.043 & 2.324 & 2.613 \\ 7 & 0.000 & 0.143 & 0.306 & 0.493 & 0.706 & 0.950 & 1.228 & 1.546 & 1.767 & 2.000 & 2.241 \\ 8 & 0.000 & 0.125 & 0.266 & 0.424 & 0.602 & 0.802 & 1.027 & 1.281 & 1.566 & 1.762 & 1.966 \\ 9 & 0.000 & 0.111 & 0.235 & 0.372 & 0.524 & 0.694 & 0.882 & 1.091 & 1.323 & 1.581 & 1.757 \\ 10 & 0.000 & 0.100 & 0.210 & 0.331 & 0.464 & 0.611 & 0.772 & 0.949 & 1.144 & 1.358 & 1.594 \\ \end{matrix}

---

For fixed $a$, your boundary condition is $E_0=0$ and recurrence is $$E_{k} = \frac{1}{a}\sum_{i=1}^{\min(a,k)}(1+ E_{k-i}) \quad\text{for $k>0$}\tag1$$ Let $f(z)=\sum_{k=0}^\infty E_k z^k$ be the ordinary generating function of $E_k$. Then $(1)$ implies \begin{align} f(z) &= \frac{1}{a}\sum_{k=1}^\infty \sum_{i=1}^{\min(a,k)} z^k + \frac{1}{a}\sum_{k=1}^\infty \sum_{i=1}^{\min(a,k)} E_{k-i} z^k \\ &= \frac{1}{a}\sum_{i=1}^a \sum_{k=i}^\infty z^k + \frac{1}{a}\sum_{i=1}^a z^i \sum_{k=i}^\infty E_{k-i} z^{k-i} \\ &= \frac{1}{a}\sum_{i=1}^a \frac{z^i}{1-z} + \frac{1}{a}\sum_{i=1}^a z^i f(z) \\ &= \frac{1}{a(1-z)} \frac{z-z^{a+1}}{1-z} + \frac{f(z)}{a}\frac{z-z^{a+1}}{1-z} \\ &= \frac{z-z^{a+1}}{a(1-z)^2} + f(z)\frac{z-z^{a+1}}{a(1-z)} \end{align} Solving for $f(z)$ yields $$f(z) = \frac{\frac{z-z^{a+1}}{a(1-z)^2}}{1-\frac{z-z^{a+1}}{a(1-z)}} = \frac{z-z^{a+1}}{a(1-z)^2-(1-z)(z-z^{a+1})}$$

For $a=2$, we have \begin{align} f(z) &= \frac{z-z^3}{2(1-z)^2-(1-z)(z-z^3)}\\ &= \frac{z(1+z)}{(1-z)^2(2+z)}\\ &= \frac{2/3}{(1-z)^2} - \frac{7/9}{1-z} + \frac{2/9}{2+z}\\ &= \frac{2}{3}\sum_{k \ge 0} \binom{k+1}{1}z^k - \frac{7}{9}\sum_{k \ge 0} z^k + \frac{1}{9}\sum_{k \ge 0} \left(\frac{-z}{2}\right)^k\\ &= \sum_{k \ge 0}\left(\frac{2}{3} \binom{k+1}{1} - \frac{7}{9} + \frac{1}{9}\left(\frac{-1}{2}\right)^k \right) z^k, \end{align} which immediately implies that $$E_k = \frac{2}{3} \binom{k+1}{1} - \frac{7}{9} + \frac{1}{9}\left(\frac{-1}{2}\right)^k = \frac{6k - 1 + (-1/2)^k}{9}$$