Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I proved the inequality below using Wald's identity and some tricky but easy manipulation, but I cannot do it using the suggestion from the source: "Hint: optional sampling!"

Here is the problem:

$X_1,X_2,\ldots$ are i.i.d. with $P(X_1>0)=1$. Let $S_n=\sum_{i=1}^nX_i$ and for $x>0$ define:

$$T_x=min\{n\geq1:S_n\geq x\}$$


$$\frac12E[T_x]\leq\frac{x}{E[\min(X_1,x)]}\leq E[T_x]$$

My solution (shown here partially):

Rewrite as: $$x\leq E[\min(X_1,x)]E[T_x]\leq 2x$$

The middle expression is equal to $$E\left[\sum_{i=1}^{T_x}\min(X_i,x)\right]$$ by Wald's identity. Thus we could just prove:

$$x\leq \sum_{i=1}^{T_x}\min(X_i,x)\leq 2x,$$

which is not that hard.

Now how do they do it using optional sampling?

share|cite|improve this question

Adaptation of this

Proof of Wald identity using Optional sampling,

may works.

In fact, it's a clever move to know Wald identity.
Otherwise, one needs to derive it using OST, to establish the equality $$ E\left(\sum_{i=1}^{T_x} \min(X_i,x)\right) = E(T_x) E(\min(X_1,x)). $$
Then the solution proceed, as you showed.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.