Expected Number of Trials

Question

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

Answer 1

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} $$