1
$\begingroup$

I have an algorithm problem that I want to share with you and I want to get some idea how can I solve it.

Problem statement: You have to reach th Nth floor of a building by using a particular elevator: there is only one button that will take you from floor i to floor i+1 with probability p(i) or to floor 1 with probability 1-p(i). you are given the number of floor. next you are given N-1 number that represent the probability p(1)...p(n-1) you should output the expected number of turns needed to reach the Nth floor.

INPUT:

3

0.5 0.25

OUTPUT

13

What I know: if you have an event that can happen with a probability p the expected number of turns until this event occur is 1/p.

Now for the questions: Is the probability of getting to the last floor the product of all probabilities? I think this is wrong because we cannot apply it to the example 1/(p1*p2) != 13

What kind of subjects (articles) should I read to solve this problem and problems similar to this.

If you have an idea feel free to share it but, please, don't give me the solution.

Thank you very much

$\endgroup$
  • $\begingroup$ You need to understand basic probability theory. $\endgroup$ – Yuval Filmus Apr 10 '17 at 7:30
  • $\begingroup$ The answer seems to be off by 1, as revealed by experiments: it should be 12 rather than 13. $\endgroup$ – Yuval Filmus Apr 10 '17 at 7:36
  • $\begingroup$ Alternatively, just add 1 to my formula; it just depends on what exactly you're counting. $\endgroup$ – Yuval Filmus Apr 10 '17 at 21:39
0
$\begingroup$

Denote by $E_i$ the expected number of turns it takes get to the $N$th floor from the $i$th floor. You are interested in $E_1$. The numbers $E_i$ satisfy the recurrence $$ E_i = 1 + p_i E_{i+1} + (1-p_i)E_1, $$ valid for $i < N$, with a base case $E_N = 0$.

In order to solve this system of equations, multiply the $i$th equation by $p_1 \cdots p_{i-1}$ to get $$ p_1 \cdots p_{i-1} E_i = p_1 \cdots p_{i-1} + p_1 \cdots p_i E_{i+1} + [p_1 \cdots p_{i-1} - p_1 \cdots p_i] E_1. $$ Summing this for $1 \leq i \leq n-1$, we get $$ E_1 = 1 + p_1 + p_1p_2 + \cdots + p_1 \cdots p_{n-2} + (1 - p_1 \cdots p_{n-1}) E_1, $$ and so $$ \begin{align} E_1 &= \frac{1+p_1+p_1p_2\cdots+p_1\cdots p_{n-2}}{p_1 \cdots p_{n-1}} \\ &= \frac{1}{p_1 \cdots p_{n-1}} + \frac{1}{p_2 \cdots p_{n-1}} + \cdots + \frac{1}{p_{n-1}}. \end{align} $$

$\endgroup$
  • $\begingroup$ Can you please explain to me how the numbers Ei satisfy the recurrence. And how did you find the formula. Thank you for your effort. $\endgroup$ – Mohamed Amine Ouali Apr 10 '17 at 16:31
  • $\begingroup$ The recurrence follows directly from the definition of your process. The 1 corresponds to the current turn. After that turn, you get one floor up or all the way down, with some probabilities, and the other two summands correspond to that. $\endgroup$ – Yuval Filmus Apr 10 '17 at 21:35
  • $\begingroup$ The recurrence itself can be solved in many ways - it's just linear algebra. My solution is particularly quick. $\endgroup$ – Yuval Filmus Apr 10 '17 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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