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!

  • $\begingroup$ 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\}. $$ $\endgroup$ – Math1000 Mar 19 '18 at 22:08
  • $\begingroup$ @Michael The $X$'s can be 0. $\endgroup$ – Jackie Mar 20 '18 at 4:56
  • $\begingroup$ @Math1000 Yes, thanks for pointing it out! $\endgroup$ – 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$.


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.