(Cross-posted from math-SE for visibility) self studying some probability theory and found this problem:
Michael Banks randomly selects cubes from Mary Poppins' magical bag (an infinite urn). In each random draw, a black cube is selected with probability $p$, and a white cube is selected with probability $q = 1 − p$.
For their magical task, Michael wants to have a sample with at least $b$ black cubes and at least $w$ white cubes. Let $S_{b,w}$ be the number of samples needed to ensure this. Clearly, $S_{b,w}$ is a random variable.
Your job is to help Mary and Michael derive a recurrence relation to compute $E[S_{b,w}]$ for any $b, w > 0$ and then proceed to do the same for the second moment $E[S^2_{b,w}]$ for any $b, w > 0$.
Now suppose there exists an upper limit to the sampling budget, i.e., Michael will stop sampling once he reaches his goal of $b$ black cubes and $w$ white cubes, or once Michael has collected $c$ cubes in total, whichever comes first. Let $S_{b,w,c}$ be the number of samples drawn. Derive a recurrence relation to compute $E[S_{b,w,c}]$ for any $b,w,c > 0$.
I'm pretty sure I have the first two parts fine. What I did for the first part was this:
$E[S_{b,w}] = \sum_{k = b+w}^{\infty}kP(S_{b,w} = k)$ and by the law of total probability (LOTP), we get
$E[S_{b,w}] = \sum_{k = b+w}^{\infty}k[P(S_{b-1,w} = k-1)P(S_{b,w} = k | S_{b-1,w} = k-1) + P(S_{b,w-1} = k-1)P(S_{b,w} = k | S_{b,w-1} = k-1)]$ which distributes into
$E[S_{b,w}] = \sum_{k = b+w}^{\infty}kP(S_{b-1,w} = k-1)P(S_{b,w} = k | S_{b-1,w} = k-1) + \sum_{k = b+w}^{\infty}kP(S_{b,w-1} = k-1)P(S_{b,w} = k | S_{b,w-1} = k-1)$ which comes out to be
$E[S_{b,w}] = \sum_{k = b+w}^{\infty}kP(S_{b-1,w} = k-1)p + \sum_{k = b+w}^{\infty}kP(S_{b,w-1} = k-1)q = [E[S_{b-1,w}]+1]p + [E[S_{b,w-1}]+1]q$. Thus, the final answer for this first part is
$E[S_{b,w}] = 1 + E[S_{b-1,w}]p + E[S_{b,w-1}]q. \square$ As for the second part, it starts like this:
$E[S^2_{b,w}] = \sum_{k = b+w}^{\infty}k^2P(S_{b,w} = k)$ and to save some space because the computations are largely the same as above mutatis mutandis, the answer actually comes out to be the same as for the first part (though I wouldn't mind if someone checked this for me). The algebra was pretty similar. I did a little substitution to change the index by one in the summation part to make things a bit easier but perhaps there was a better way.
Now where I'm completely lost and hopeless is for the last part. I've spent the last day or two to no avail trying to solve this last part. I don't know why I'm struggling with it so hard and would love someone to explain it to me. Someone gave me the solution which I know to be $E[S_{b,w,c}]=1+pE[S_{b-1,w,c-1}]+qE[S_{b,w-1,c-1}]$ but I don't understand how they got there or how you would start this problem. Thank you!
