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
\begin{equation} P(S_m<m, \forall\ 1\leq m\leq n | S_n)=\max\{0, 1-S_n/n\} ? \end{equation}
I think that there is something to do with martingales, but I am not really sure where to start. Thanks!
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$.