I'm currently stuck on the following problem where we know that for an airline it is a 7% probability that a passenger will not meet up for departure. So to get a better use of the plane capacity the airline overbook the tickets. The plane for this task has 243 seats.

The thing is that the airline loses 1000\$ for each non-used seat in the plane. If a passenger does not get a spot because of the overbooking, the passenger will be compensated with 4000\$. We want to find an expression for the expected loss if we take $n$ orders. And by using the expression/graph we want to find the number of orders such that we minimize the expected loss. The numerical answer is given, which is 258 orders which results a loss of $5564\$$.

I understand that this will be a binomial distribution if we define a stochastic variable $X$ which says how many passengers that really meet ups for departure... but how do I use this fact to get the desired expression? If we do not overbook, i.e. only take 243 orders, the expected loss is to be $243 \cdot 0.07 \cdot 1000 = 17010 \$$, but if I try to do the same for $n = 258$ orders I do not get the same answer as the solution(which would be $5564\$$), why could I do that for $n = 243$, but not for $n= 258$?

  • 1
    $\begingroup$ What happens when $250$ people show up? Does airline compensate anything for the excess people? $\endgroup$ – Sungjin Kim Sep 27 '17 at 2:25

Realize that the two scenarios correspond to different situations

scenario 1: no overbooking

scenario 2: overbooking 258 against 243 seats

For exactly one seat to go vacant in scenario 1, any one among the 243 passengers has to default on making it to the departure with probability $$ ^{243}C_1 \cdot (0.07)^1 \cdot (0.93)^{242}$$

And similarly the probability for two seats to go vacant = the probability that two people fail to arrive at the departure, which would be $$ {243}C_2 \cdot (0.07)^2 \cdot (0.93)^{241}$$ and this binomial series will go on. So you can use the expectation of the binomial random variable to arrive at the expected number of seats that will be vacant at departure which is $n \cdot p$.

But this is not the same for scenario 2. In scenario 2 for exactly one seat to remain empty exactly 16 people will have to fail to show up at the departure which has probability $$ ^{258}C_{16} \cdot (0.07)^{16} \cdot (0.93)^{242}$$ and similarly for two seats to be vacant at least 17 people of 258 would have to miss the flight with probability $= \ ^{258}C_{17} \cdot (0.07)^{17} \cdot (0.93)^{241}$, and so on. Let $k$ denote the number of people who arrive for the flight at departure, $X$ be the random variable denoting vacant seats and $Y$ be the random variable denoting number of people to be compensated because of plane being full at departure.

$$\mathbb{E}[X] = \sum_{k = 1}^{243} (243 - k) \cdot \ ^{258}C_{k} \cdot (0.07)^{258-k} \cdot (0.93)^{k}$$

$$\mathbb{E}[Y] = \sum_{k = 243}^{258} (k - 243) \cdot \ ^{258}C_{k} \cdot (0.07)^{258-k} \cdot (0.93)^{k}$$

and expected loss is $\mathcal{L} = 1000 (\mathbb{E}[X] + 4\cdot\mathbb{E}[Y])$

So you cannot directly use $n\cdot p = 258 \cdot 0.07 \cdot 1000$ to calculate the expected loss in scenario 2, both the cases have different loss functions.

Your original optimization problem is of the form $$\text{arg}\,\min\limits_{n \geq 243}\, \ \sum_{i = 1}^{243} (243-i) \cdot \ ^{n}C_{i} \cdot (0.07)^{n-i} \cdot (0.93)^{i} + \ \sum_{i = 243}^{n} (i-243) \cdot \ ^{n}C_{i} \cdot (0.07)^{n-i} \cdot (0.93)^{i}$$

  • $\begingroup$ I don't really understand how the two scenarios have different binomial distributions. Could you explain a bit more? And why do I have to care about if exactly one passenger has to default on making it to the departure, when we really need to look at the case if at least one person misses the trip? $\endgroup$ – Geir Sep 26 '17 at 18:20
  • $\begingroup$ Check the edits? $\endgroup$ – exp iㅠ Sep 26 '17 at 18:37
  • 1
    $\begingroup$ Yeah, I think I understood it more. But what does the expected value express here? The number of people that is expected not to take their seats? When I put in the numbers for $n = 258$ I get from your formula that the expected value is approx. 3.56 which gives the wrong answer when multiplied by 1000 (as we lose 1000$ per empty seat). $\endgroup$ – Geir Sep 26 '17 at 18:44
  • 1
    $\begingroup$ If $Y$ is the random variable representing number of people who miss their flight and $X$ the number of seats vacant at departure then $X = Y - 15$ whenever $Y \geq 15$ and $0$ otherwise. The above expression for expectation calculates the expectation for $X$. Yes there seems to be a disparity in the calculated value of the expected number of seats vacant. Let me check. $\endgroup$ – exp iㅠ Sep 26 '17 at 18:57
  • $\begingroup$ @expiㅠ This expectation without any other assumptions, will converge to $0$ as the number of booking increases to infinity. I checked with Python that the expected value at $258$ does not equal $5564$. $\endgroup$ – Sungjin Kim Sep 27 '17 at 2:26

Suppose the actual number of seats is $N$, while the allowed number of bookings is $N'\geq N$. Suppose $M$ people book the flight $(0\leq M\leq N')$, while on the day of the flight only $m$ people show up $(0\leq m\leq M)$.

Let $S$ be the money lost if a seat goes vacant. If $m< N$ then the airline loses $(N-m)S$ amount of money. If $m\geq N$ then airline loses no money if it does no more than fully reimburse those who could not obtain a seat due to overbooking.

If $p$ is the probability that a booked person shows up on the day of the flight, then the probability that $m$ people show up, given that $M$ have booked, is: \begin{align} P(m|M)=C^M_mp^m(1-p)^M,\quad 0\leq m\leq M \end{align} and zero otherwise. We assume that total number of bookings has uniform probability distribution: \begin{align} P(M)=\frac{1}{N'+1},\quad 0\leq M\leq N' \end{align} The probability that $m$ people show up irrespective of how many have booked is: \begin{align} P(m)=\sum_{M=m}^{N'}P(M)P(m|M)=\frac{1}{N'+1}\sum_{M=m}^{N'}C^M_mp^m(1-p)^M,\quad 0\leq m\leq N' \end{align} and zero otherwise. The summation begins from $M=m$ because for $M<m,P(m|M)=0$.

The expected loss is therefore: \begin{align} L & =\sum_{m=0}^{N-1}P(m)~(N-m)S \\ & =\frac{S}{N'+1}\sum_{m=0}^{N-1}(N-m)\sum_{M=m}^{N'}C^M_mp^m(1-p)^M \end{align} in which the summation on $m$ ends at $N-1$ because for $m>N-1$ the airline suffers zero loss of money.


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.