# Showing $P(S_m<m, \forall\ 1\leq m\leq n | S_n)=\max\{0, 1-S_n/n\}$

Let $X_1, X_2,\ldots$ be a sequence of iid random variables such that for each $i$, $X_i$ takes value as nonnegative integer and is in $L^1$. Let $S_n = \sum_{i=1}^n X_i$. How to show that

$$P(S_m<m, \forall\ 1\leq m\leq n | S_n)=\max\{0, 1-S_n/n\} ?$$

I think that there is something to do with martingales, but I am not really sure where to start. Thanks!

• By $\mathbb P(S_m<m, \forall 1\leqslant m\leqslant n\mid S_n)$ do you mean $$\mathbb E\left[\mathsf 1_{S_m<m, \forall 1\leqslant m\leqslant n}\mid \sigma(S_n) \right]\; ?$$ Since the $X_i$ are discrete it would be clearer to write the statement as $$\mathbb P\left( \bigcap_{m=1}^n \{S_m<m\} \mid S_n = j\right) = \max\{0, 1-j/n\}.$$ – Math1000 Mar 19 '18 at 22:08
• @Michael The $X$'s can be 0. – Jackie Mar 20 '18 at 4:56
• @Math1000 Yes, thanks for pointing it out! – Jackie Mar 20 '18 at 4:58

Let $E_n = \bigcap_{i=1}^n \{S_i<i\}$. We will prove $P(E_n|S_n=k)=(1-k/n)^+$ by induction on $n$, where $x^+=\max(0,x)$.
Given a list of numbers $X = (X_1,\dots,X_n)$, let $Y = (Y_1,\dots,Y_n)$ be the same list rearranged in weakly increasing order. We will prove the stronger fact that for any deterministic $y=(y_1,\dots,y_n)$, where $y_1\le y_2\le \dots\le y_n$, that
$$P(E_n|Y=y)=(1-k/n)^+, \text{ where }k=y_1+\dots+y_n$$ In other words, we are conditioning on everything except the order of the $X_i$, but the resulting probability only depends on the sum of the values, so it is still true when you only condition on the sum.
The result is obvious when $k\ge n$ since in that case, $S_n=k\ge n$, so assume $k<n$. Given that the sorted list of $(X_1,\dots,X_n)$ equals $(y_1,\dots,y_n)$, $X_n$ is equally likely to be any of the $y_i$. Therefore, $$P(E_n|Y=y) = \sum_{i=1}^nP(E_n|Y=y,X_n=y_i)\cdot\tfrac1{n}$$ Now, when we are given that $X_n=y_i$, the remaining numbers $(X_1,\dots,X_{n-1})$ are equally likely to be any rearrangement of the list $y$ with $y_i$ removed. Letting $\hat y_i$ be this list, and letting $\hat Y$ be the weakling increasing rearrangement of $(X_1,\dots,X_{n-1})$, $$P(E_n|Y=y) = \sum_{i=1}^nP(E_{n-1}|\hat{Y}=\hat y_i)\cdot \tfrac1n=\sum_{i=1}^n\left(1-\frac{k-y_i}{n-1}\right)^+\cdot \frac1n$$ where the last equality follows by the induction hypothesis. Since we assumed $k<n$, it follows each $1-\frac{k-y_i}{n-1}\ge 0$, so we can remove the $^+$ from the above: $$P(E_n|Y=y) =\sum_{i=1}^n\left(1-\frac{k-y_i}{n-1}\right)\cdot \frac1n$$ After some algebra, and recalling that $\sum_{i=1}^n y_i=k$, the above simplifies to $1-k/n$.