Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Recently I realized that lost all computing skill in probability. Please take a look at the following problem.

There are $b$ balls that are thrown one by one and bounce from top to bottom on the $n$ steps of stairs. The balls are thrown one by one with one unit of time interval when the previous ball touches the first step the next ball is thrown. Reaching the next step takes the same one unit of time. The probability that the ball miss the step is $p$. The goal is achieved when at least one ball touches the last step.

What is the maximum running time of the process till the success in the worst case?

I think the worst case is when we lost first $b-1$ balls on the first step, all $b-1$ balls missed the first step and the last $b$th last successfully reached the last step, therefore the worst running time is $b-1+n$.

What is the probability of a success (at least one ball reached the last step)?

$P(success)=1-p^b$

What is the smallest number of balls should be thrown to guarante that the probability of success is at least $1 - \frac{1}{n}$.

$$1-p^b \geq 1 - \frac{1}{n}$$

$$p^b \leq \frac{1}{n}$$

$$b \cdot \log p \leq - \log n$$

$$b \leq - \frac{\log n}{\log p}$$

I am not sure if I get it correct.

Give an upper bound on the expected running time.

Let try to use a Geometric distribution

$$E=\sum_{i=1}^{b-1} i \cdot p^i \cdot (1-p)^n$$

I still not sure if I get it right with expected running time

share|improve this question

1 Answer 1

Answer to part 1 is spot on.

Answer to part 2, the trick is to realise that these are independent events- each ball hits the last step with probability $p$.

So the chance that at least 1 ball hits is the opposite that none hit i.e. $1-(1-p)^b$

Use this for Part 3 and post what you get.

share|improve this answer
    
Great, thanks. I updated the question, and $P(success)=1-p^b$, $p$-probability of miss. Do you know how to find expected running time? –  tam Jun 16 '13 at 13:07
    
Yes - have a look at en.wikipedia.org/wiki/Geometric_distribution which is directly applicable. Do you see why? If you see why, can you use this? –  Dale M Jun 17 '13 at 2:07
    
I see your point, I have edited the question, could you please take a look. –  tam Jun 17 '13 at 2:53
    
@tam What you have written is the expected value for which ball hits the stair - you need to add the time that it takes to bounce down to that stair. –  Dale M Jun 17 '13 at 5:02
    
I took you comment very seriously and changed the question, please take a look, and in your opinion answer to $3$th question is correct? –  tam Jun 17 '13 at 10:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.