Sunday, December 31, 2017

probability - Expected value from popping bubbles




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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...