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?
Answer
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)$.
No comments:
Post a Comment