Arriving at the formula for expected value of a random variable

Question

I was trying to solve this programming problem but I can't solve it since I am not able to arrive at the right formula for it. I dont want the solution using Dynamic Programming. I just want someone to explain how to get the formula for answering that question. This is not a homework problem. Thanks for helping me.

Answer 1

This is a queuing problem with a binomial twist. Wikipedia has some good information about the Binomial Distribution. From this page, we know that the probability of getting exactly $k$ successes in $n$ trials when the probability of success is $p$ is:

$${n \choose k}p^k(1-p)^{n-k}$$

Now, let's assume that $n$ people stand in the queue for the escalator. At each second one of the two following possibilities takes place: either the first person in the queue enters the escalator with probability $p$, or the first person in the queue doesn't move with probability $(1 - p)$, paralyzed by his fear of escalators and making the whole queue wait behind him.

The expected number of people on the escalator after $t$ seconds, then, is:

$$\sum_{x=1}^{\text{min}(n,t)}x \cdot \text{probabilty of $x$ people on the escalator} = \sum_{x=1}^{\text{min}(n,t)} x \cdot {t \choose x}p^x(1-p)^{t-x}$$

Where:

$${t \choose x} = \frac{t!}{x!(t-x)!}$$

Each term in the summation multiplies the probability of $x$ people being on the escalator by $x$. We only sum over the range $1$ to $\text{min}(n,t)$ because once everyone in the queue has been called, no one else can get on the escalator. Similarly, once time $t$ is reached, we are not interested in anyone else who is getting on the escalator.

Of course, this all assumes that the escalator is infinitely long and that no one gets off of it at some later time.

Answer 2

It appears that once you reach a person who is scared of the escalator, then no more people enter...forever. Thus, after $t$ seconds (assume $t$ is integer valued), one of two events can happen:

1. A person with no fear is at the head of the line, call this $N_t$
2. A scared person is at the head of the line, call this $F_t$

$N_t$ can only happen if every person up to time $t$ got on the escalator, so:

$$P(N_t)=p^t$$

$F_t$ will happen the if we encountered a scared person at some point up to time $t$, which is equal to $N_t^c$.

$$P(F_t)=1-P(N_t)=1-p^t$$

Now, given $F_t$, the let $T_t$ be the number of people who got on the elevator before the the scared person moved to the head of the line (which we know occurred in the $t$ intervals before time $t$):

$$P(T_t=a)=p^{a}(1-p)\text{ for }0\leq a\leq t,\text{ and } 0\;o.w.$$

This is just an (unnormalized) conditional geometric distribution with parameter $q:=1-p$

Since $T_t$ is a positive random variable, we can exploit a nice trick for getting the expected value:

$$E[T_t]=\frac{\sum_{i=1}^{t} P(T_t\geq i)}{1-p^{t}}=\frac{\sum_{i=1}^{t} p^i }{1-p^{t}}=\frac{\sum_{i=0}^{t} p^i -1}{1-p^{t}}=\frac{\left(\frac{1-p^{t}}{1-p}\right)-1}{1-p^{t}}=\frac{p-p^{t}}{(1-p)(1-p^{t})}$$

So, we now combine our two results:

The expected number of people on the escalator at time $t$, $Z_t$, is the probability that the person at the head of the line at time $t$ is not scared times $(t)$ (since everyone got on up to this point), plus the the probability that a scared person is at the head of the line at time $t$ times the expected value of the number of people on the escalator given we have a scared person at the head of the line at time $t$ (our second result):

$$E[Z_t]=tp^t+(1-p^t)\left(\frac{p-p^{t}}{(1-p)(1-p^{t})}\right) \;\;\;\;\square$$