Combinatorics, expected value, drawing balls from a bag, and customer support It's been a few years since I've done my CS combinatorics stuff so I'm having a major brain fart here.
You put n red balls into a bag. Every t hours you select (n/100) balls from the bag. If a selected ball is red, you swap it out for a green ball. If a selected ball is green, you leave it as is. You put all the selected balls back into the bag. After x hours (where x is some exact multiple of t; alternatively, we can consider this as after i iterations of the process), what is the expected number of green balls in the bag? What's the standard deviation for distribution of green balls? What's the equation that models this?
So the first iteration is obvious. You take out (n/100) red balls, they are replaced by green balls. The second iteration will end with 2(n/100) - the expected number of green draws in the second iteration. This is where my head is starting to go soupy.
The original issue here is trying to model a customer service followup system at a mid-level software company. I have a simulator written to simulate the process, but would appreciate this expressed mathematically.
Any tips?
 A: Here is some elementary analysis. To follow your notation, let $n$ be the number of balls in the bag, let $i$ be the number of iterations of replacing the selected red balls with green balls, and let $s$ (instead of $\frac n{100}$) be the number of balls you select on each iteration. Also, let's define $p(i,g)$ to be the probability that after the $i^{\text{th}}$ iteration the bag contains exactly $g$ green balls. For the expectation and standard deviation, let $\mu_i$ be the expected number of green balls in the bag after the $i^{\text{th}}$ iteration (so, $\mu_i=\sum_{g\ge0} g\cdot p(i,g)$), and let $V_i$ be the associated variation (so, $V_i=\sum_{g\ge0} (g-\mu_i)^2 p(i,g)$ ).
There is a recurrence relation among the $p(i,g)$'s. In the base case before any iterations, all the balls are red, so $p(0,0)=1$ and $p(0,g)=0$ for each $g>0$. In the general case, suppose you start with $g'$ green balls (and consequently $n-g'$ red balls) after the $i^{\text{th}}$ iteration, and you want to get $g$ green balls (and consequently $n-g$ red balls) on the next iteration. To do this, out of the $\binom ns$ ways to choose $s$ balls out of the bag after the $i^{\text{th}}$ iteration, you have to choose $g-g'$ of the $n-g'$ red balls that will become green and you have to choose $s-(g-g')$ of the $g'$ green balls that will stay green. So,
$$p(i+1,g)=\sum_{g'=g-s}^g p(i,g')\frac{\binom{n-g'}{g-g'}\cdot\binom{g'}{s-(g-g')}}{\binom ns}.$$
This recurrence relation allows you to express the expectations and variances as infinite series, which you can at least approximate. The next step would be to solve the recurrence relation explicitly. The usual method to do this would be with generating functions. Unfortunately, at least at first glance, I don't see how to do this (with generating functions or otherwise). Maybe at this point someone else can help.
It might also be useful to compare this problem with others. There is a similar problem in Wilf's wonderful book on generating functions about flipping coins until they all turn up heads (or getting a Yahtzee or however else you want to phrase it). See problem 20 at the end of chapter 4 (page 164 in the second edition).
