Estimate k0 for Elevator Probability of 10 Stops

[sabri]

10 people get on an elevator on the first floor of a seven-story building. Each gets off at one of the six
higher floor chosen at random. What is the expected number of stops the elevator makes? Generalize the
result for a k -store building with k>2: Estimate the value k0 such that the probability that the elevator
will stop exactly 10 times is larger equal than 0.9 for all k>k0.

I've done this so far not sure if it is correct

the Expectation of number of stops = 7 . (1-(6/7)^10)= 5.5

 

[Opalg]

10 people get on an elevator on the first floor of a seven-story building. Each gets off at one of the six
higher floor chosen at random. What is the expected number of stops the elevator makes? Generalize the
result for a k -store building with k>2: Estimate the value k0 such that the probability that the elevator
will stop exactly 10 times is larger equal than 0.9 for all k>k0.

I've done this so far not sure if it is correct

the Expectation of number of stops = 7 . (1-(6/7)^10)= 5.5

Hi sabri, and welcome to MHB.

If the people get on the elevator at one of the seven floors, then there are only six other floors at which they can get off. So I think that your formula for the expected number of stops should be 6 . (1-(5/6)^10), which is approximately 5.03. Apart from that, I believe that your formula is correct.

 

[sabri]

Hi sabri, and welcome to MHB.

If the people get on the elevator at one of the seven floors, then there are only six other floors at which they can get off. So I think that your formula for the expected number of stops should be 6 . (1-(5/6)^10), which is approximately 5.03. Apart from that, I believe that your formula is correct.

thank you for the correction but i still didn't get the second part of the exercise where he asks me to generalize the result for a k -store building with k>=2, and to Estimate the value k0 such that the probability that the elevator
will stop exactly 10 times is larger equal than 0.9 for all k>k0.(Thinking)

 

[Opalg]

i still didn't get the second part of the exercise where he asks me to generalize the result for a k -store building with k>=2, and to Estimate the value k0 such that the probability that the elevator
will stop exactly 10 times is larger equal than 0.9 for all k>k0.(Thinking)

For a seven-storey building, the expected number of stops is $(7-1)\left(1 - \bigl(\tfrac{7-2}{7-1}\bigr)^{10}\right)$. If you replace $7$ by $k$, that gives the expected number of stops in a $k$-storey building as $(k-1)\left(1 - \bigl(\tfrac{k-2}{k-1}\bigr)^{10}\right)$.

The last part of the problem seems quite different to me. It is asking for the probability that all ten people get off at different floors. In a $k$-storey building, with $k-1$ floors for them to get off at, the number of ways that they can choose ten different floors is the binomial coefficient $k-1\choose10$. So the probability that they all get off at different floors is ${k-1\choose10}\big/(k-1)^{10}$. You need to find how large $k$ must be in order that ${k-1\choose10} > 0.9(k-1)^{10}$.

I do not know of any exact way to solve that inequality. But the problem only asks you to "estimate" how large $k$ must be. So you need to have some way of estimating that size of that binomial coefficient. Doing it by trial and error, using a calculator, my estimate is that $k$ must be extremely large (around 450, I think). In any case, the building would have to be a good deal taller than any existing skyscraper.

 

[sabri]

For a seven-storey building, the expected number of stops is $(7-1)\left(1 - \bigl(\tfrac{7-2}{7-1}\bigr)^{10}\right)$. If you replace $7$ by $k$, that gives the expected number of stops in a $k$-storey building as $(k-1)\left(1 - \bigl(\tfrac{k-2}{k-1}\bigr)^{10}\right)$.

The last part of the problem seems quite different to me. It is asking for the probability that all ten people get off at different floors. In a $k$-storey building, with $k-1$ floors for them to get off at, the number of ways that they can choose ten different floors is the binomial coefficient $k-1\choose10$. So the probability that they all get off at different floors is ${k-1\choose10}\big/(k-1)^{10}$. You need to find how large $k$ must be in order that ${k-1\choose10} > 0.9(k-1)^{10}$.

I do not know of any exact way to solve that inequality. But the problem only asks you to "estimate" how large $k$ must be. So you need to have some way of estimating that size of that binomial coefficient. Doing it by trial and error, using a calculator, my estimate is that $k$ must be extremely large (around 450, I think). In any case, the building would have to be a good deal taller than any existing skyscraper.

thank you again for the clarification things are more clear now (Smile)(Yes)

 

[StoneTemplePython]

I do not know of any exact way to solve that inequality. But the problem only asks you to "estimate" how large $k$ must be. So you need to have some way of estimating that size of that binomial coefficient. Doing it by trial and error, using a calculator, my estimate is that $k$ must be extremely large (around 450, I think). In any case, the building would have to be a good deal taller than any existing skyscraper.

$450$ is a good estimate. Here's a mathematically nicer way to finish:
a different way of approaching the second half of the problem is to recognize it is equivalent to a Birthday Problem -- what $k_0$ is required to get probability of no 'collisions' bounded below by 0.9? This is amenable to Poisson approximation. But it also can be done directly with analytical bounds -- we have a lower bond via union bound / generalized Bernoulli inequality and an upper bound from the all important inequality $1 +x \leq e^x$ for any $x\in \mathbb R$

The union bound estimate is a lower bound given basically by a triangular number $\lambda = \frac{\binom{10}{2}}{k_0}$
so

$0.9 \leq 1 - \lambda = 1 - \frac{\binom{10}{2}}{k_0} \leq \text{actual probability} \leq \exp\big( -\frac{\binom{10}{2}}{k_0} \big) = \exp\big(-\lambda\big)$

focusing on the lower bound
$0.9 \leq 1 - \frac{\binom{10}{2}}{k_0} $
we can rescale by $k_0$ and simplify to get

$\frac{1}{10} k_0 \geq \binom{10}{2} $
$ k_0 \geq 10\cdot\binom{10}{2} $

which is satisfied with equality for $k_0 = 450$
= = = =
as for the upper bound
$\text{actual probability} \leq \exp\big( -\frac{\binom{10}{2}}{k_0} \big)$
which is $\approx 0.9048$ for $k_0$ = 450.

Also of interest, the upper bound is $\approx 0.89953$ for $k_0 = 425$

This tells you the estimate is sharp.I left computation of $\text{actual probability} $ as an open item for OP. Hopefully it is clear how to compute it and then arrive at the inequalities. If not, I can fill in more details.

 

[sabri]

$450$ is a good estimate. Here's a mathematically nicer way to finish:
a different way of approaching the second half of the problem is to recognize it is equivalent to a Birthday Problem -- what $k_0$ is required to get probability of no 'collisions' bounded below by 0.9? This is amenable to Poisson approximation. But it also can be done directly with analytical bounds -- we have a lower bond via union bound / generalized Bernoulli inequality and an upper bound from the all important inequality $1 +x \leq e^x$ for any $x\in \mathbb R$

The union bound estimate is a lower bound given basically by a triangular number $\lambda = \frac{\binom{10}{2}}{k_0}$
so

$0.9 \leq 1 - \lambda = 1 - \frac{\binom{10}{2}}{k_0} \leq \text{actual probability} \leq \exp\big( -\frac{\binom{10}{2}}{k_0} \big) = \exp\big(-\lambda\big)$

focusing on the lower bound
$0.9 \leq 1 - \frac{\binom{10}{2}}{k_0} $
we can rescale by $k_0$ and simplify to get

$\frac{1}{10} k_0 \geq \binom{10}{2} $
$ k_0 \geq 10\cdot\binom{10}{2} $

which is satisfied with equality for $k_0 = 450$
= = = =
as for the upper bound
$\text{actual probability} \leq \exp\big( -\frac{\binom{10}{2}}{k_0} \big)$
which is $\approx 0.9048$ for $k_0$ = 450.

Also of interest, the upper bound is $\approx 0.89953$ for $k_0 = 425$

This tells you the estimate is sharp.I left computation of $\text{actual probability} $ as an open item for OP. Hopefully it is clear how to compute it and then arrive at the inequalities. If not, I can fill in more details.

Thank you so much, actually things here are more clear than at school, Happy to use Math Help Boards (heart)