In order to avoid empty seats on an airplane, an airline will sell more seats (tickets) than available on the flight well aware of the risk of having to compensate passengers that have been overbooked. Suppose on some flight there are $S=555$ seats available. The revenue for every passenger is $\alpha=2659\$$. The cost for compensating an overbooked passenger is $\beta=600\$$. Every person that has booked a flight will turn up with a probability $p$ (independent of every other person). Assume if they don't show up to a flight they don't have to pay. Use the normal approximation to calculate how many tickets the airline needs to sell to maximize profit for the case that $p=0.95$ and $p=0.873$. Let $P_n$ be the profit and $S_n$ the passengers (people that showed up and are on the plane) and $n$ the sold tickets. Hint: Show that: $$E[P_{n+1}-P_n]\ge 0 \iff P(S_n<S)\ge \frac{\beta}{\alpha+\beta}$$
Edit: The problem I am having is the following: How does
$$E\big[S_{n+1}-S_n \big]=P(S_n<S) ?$$
I just wanted to include the rest for context.
What I have done so far: As far as I understand there are two parts to this problem. The first part is showing that the two inequalities are equivalent and that the expected profit from the $n+1$ sold ticket is zero or positive. The second part is using the central limit theorem (CLT) to determine what $n$ actually is. I will start with the second part which I think I have gotten right (please correct me if I made a mistake) and then I will show the first part because that's where I am having difficulties.
Since the r.v. are independent and bernoulli, the sum $S_n$ has mean $p$ and variance $p(1-p)$. Therefore ,
$$\begin{equation*}\begin{split}P\left(S_n \le S\right)&=P(S_n \le 555)\ge\frac{\beta}{\alpha+\beta}\\[10pt] &\iff P\left( \frac{S_n-np}{\sqrt{n}\sqrt{p(1-p)}}\le\frac{555-np}{\sqrt{n}\sqrt{p(1-p)}}\right)\ge\frac{\beta}{\alpha+\beta} \\[10pt] &\iff P\left( \frac{S_n-0.95n}{\sqrt{n}\sqrt{0.95(0.05)}}\le\frac{555-0.95n}{\sqrt{n}\sqrt{0.95(0.05)}}\right)\ge\frac{\beta}{\alpha+\beta} \\[10pt] &\iff
P\left(Z_n \le \frac{555-0.95n}{\sqrt{n}\sqrt{0.95(0.05)}}\right)\ge\frac{600}{3259}\end{split}\end{equation*}$$
I looked up the Z-score for a P-value of $\frac{600}{3259}$ which is $0.89983$.
$$\begin{align}&\implies \frac{555-0.95n}{\sqrt{n}\sqrt{0.95(0.05)}}=0.89983 \\[10pt] &\iff n\approx 583.188 \end{align}$$
So to maximize profit (if the equivalence relation above is true) the airline needs to sell $583$ or $584$ tickets.
Showing the equivalence of the inequalities:
$$\begin{equation*}\begin{split} \text{Profit}&= \text{Revenue}-\text{Cost} \\[10pt] P_n&=S_n \alpha-(n-S_n)\beta \\[10pt] P_n&= S_n(\alpha+\beta)-n\beta \\[10pt] \implies P_{n+1} &=S_{n+1}(\alpha+\beta)-(n+1)\beta\end{split} \end{equation*}$$
Therefore,
$$\begin{equation*}\begin{split} P_{n+1}-P_{n}&=S_{n+1}(\alpha+\beta)-(n+1)\beta-\Big(S_n(\alpha+\beta)-n\beta \Big) \\[10pt] \iff P_{n+1}-P_n &=(S_{n+1}-S_n)(\alpha+\beta)-\beta \\[10pt] \iff E\big[ P_{n+1}-P_{n}\big] &= E\big[ (S_{n+1}-S_n)(\alpha+\beta)-\beta \big]\end{split} \end{equation*}$$
Since I want $E\big[ P_{n+1}-P_{n}\big] \ge 0$ it follow that:
$$\begin{equation*}\begin{split} &\implies E\big[ (S_{n+1}-S_n)(\alpha+\beta)-\beta \big] \ge 0 \\[10pt] &\iff E\big[ (S_{n+1}-S_n)(\alpha+\beta) \big] -E\big[\beta \big] \ge 0 \\[10pt]
&\iff E\big[ S_{n+1}-S_n) \big] (\alpha+\beta)-\beta \ge 0 \\[10pt] &\iff E\big[ S_{n+1}-S_n \big] \ge \frac{\beta}{\alpha+\beta} \\ \color{red}{\vdots} \\ &\iff \color{red}{P(S_n < S)}\ge \frac{\beta}{\alpha+\beta} \end{split} \end{equation*}$$
I feel like I am very close but I can't see how the expected value turns into this probability? What am I missing? In other words how does:
$$E\big[S_{n+1}-S_n \big]=P(S_n<S) ?$$
Best Answer
I'm a little confused by the definitions of $n$ and $S_n$, but it seems $S_n$ is the number of people that get to board the plane, and $n-S_n$ is the number of overbooked passengers that need to be compensated. Or in other words, $S_n = \min\{n, S\}$.
In particular, either two things can happen:
Thus, $$E[S_{n+1} - S_n] = E[(S_{n+1} - S_n)\mathbf{1}_{S_n < S}] + E[(S_{n+1} - S_n)\mathbf{1}_{S_n = S}] = 1 \cdot P(S_n < S) + 0 \cdot P(S_n = S).$$