# Expected value from popping bubbles [duplicate]

This is a fairly simple math problem from a programming challenge but I'm having trouble wrapping my head around it. What follows is a paraphrase of the problem:

Kundu has a Bubble Wrap and like all of us she likes popping it.
The Bubble wrap has dimensions NxM, i.e. it has N rows and each row has
M cells which has a bubble. Initially all bubbles in filled with air and
can be popped.

What Kundu does is randomly picks one cell and tries to pop it,
there might be a case that the bubble Kundu selected is already popped.
In that case he has to ignore this. Both of these steps take 1 second of
time. Tell the total expected number of seconds in which Kundu would
be able to pop them all.


So I know that the expected value is the sum of the product of the random variable x and the probability of that instance of x occurring but I'm having trouble parameterising the problem statement. What's the x and how does time play into it?

## marked as duplicate by Did probability StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Sep 11 '15 at 5:52

• For a discussion, please see the Coupon Collector's Problem (Wikipedia). – André Nicolas Aug 12 '15 at 0:38

One approach, which I like because it is rather general, is to use a Markov chain.

There are $B$ total bubbles. After $t$ attempts, $U(t)$ of them are left. She pops a bubble with probability $U(t)/B$ and finds a popped bubble with probability $1-U(t)/B$. Call $\tau$ the random number of attempts that it takes to pop all the bubbles. Let $F(u)=E_u(\tau)$, where $E_u$ means that we take the expectation with $U(0)=u$. Then by the total expectation formula

$$F(u)=(F(u-1)+1)(u/B)+(F(u)+1)(1-u/B).$$

This is coupled to the natural boundary condition $F(0)=0$. This recurrence for $F$ turns out to be very easy to solve, as you can see by rearranging it. Your solution is $F(B)$.

Let $T_i$ be the time to pop the ith bubble, for $i=1,..,MN$. Then $T_1=1$, so $E(T_1)=1$.

Note each $T_i$, $i>1$ has a geometric distribution w/ p=$\frac{MN-i}{MN}$, so E($T_i$)=$\frac{MN}{MN-i}$. Thus, the expected total time is (by the linearity of expectation) $$\sum_{i=1}^{MN} \frac{MN}{MN-i} = MN \sum_{i=1}^{MN}\frac{1}{MN-i} = MN \sum_{i=1}^{MN}\frac{1}{i} \approx MN\cdot \log(MN)$$

reference: Partial Sums