Problem
There are $x$ red and $y$ blue candies in a jar. A child randomly eats one candy everyday. If a child eats a red candy, the child will put a blue candy into the jar. If a child eats a blue candy, the child doesn't put another candy into the jar.
Let $X$ denote the number of blue candies in the jar, after the child ate the last red candy and puts another blue candy into the jar. Find $\mathbb{E}[X]$.
Why I'm Stuck
This question has just completely struck my brain.
I've approached the quick-sort algorithm and have defined $x+y$ indicator variables.
I'm stuck in the process of writing the formula... Anybody can help?
The expected value of $B$, the number of remaining blue candies just after all red candies are replaced, if we start with $x$ red candies and $y$ blue candies appears to be $$\mathbb{E}_{x,y}[B] = \frac{y}{x+1} + H_x \approx \frac{y}{x + 1} + \log(x)$$ where $H_x$, the $x$th harmonic number, is equal to $\sum_{i = 1}^x \frac{1}{i}$.
To prove its correctness, note that the expectation $\mathbb{E}_{x, y} [B]$ satisfies the recurrence $$\mathbb{E}_{x, y}[B] = \frac{x}{x + y} \mathbb{E}_{x - 1, y + 1} [B] + \frac{y}{x + y} \mathbb{E}_{x, y - 1} [B] $$ And indeed, \begin{align} \frac{x}{x + y} \mathbb{E}_{x - 1, y + 1} [B] + \frac{y}{x + y} \mathbb{E}_{x, y - 1} [B] &= \frac{x}{x+y} \left[\frac{y + 1}{x} + H_{x-1} \right] + \frac{y}{x+y}\left[\frac{y - 1}{x+1} + H_x\right] \\ \\ &= \frac{(y + 1)(x+1) + y(y-1)}{(x + y)(x + 1)} + H_{x-1} + \frac{y}{x(x + y)} \\ \\ &= \frac{x^2y + xy^2 + x^2 + x + xy + y}{x(x+y)(x+1)} + H_{x - 1} \\ \\ &= \frac{(x + y)(x + 1) + x^2y + y^2x}{x(x+y)(x+1)} + H_{x - 1} \\ \\ &= \frac{(x + y)xy}{x(x+y)(x+1)} + H_{x-1} + \frac{1}{x} \\ \\ &= \frac{y}{x + 1} + H_x = \mathbb{E}_{x, y}[B] \end{align} I'm not completely sure how to solve the recurrence without guessing though!