1
$\begingroup$

Right now i am looking at the following statement, but i cant grasp why it is correct. Can somebody help?
"If we look at F0 uniformly distributed (and, say, pairwise independent) elements of [0, 1], we expect about t of them to be smaller than t/F0."

Kind Regards, Ilian

$\endgroup$

2 Answers 2

1
$\begingroup$

Consider defining indicator random variables $X_1, X_2, ..., X_{F_0}$ such that

$$ X_i = \begin{cases} 1 \text{ if } x_i < \frac{t}{F_0} \\ 0 \text{ otherwise } \end{cases} $$

Then, we can count the number of elements $< \frac{t}{F_0}$ as follows

$$ [ \text{# of Elements} < \frac{t}{F_0} ]= \sum_{i=1}^{F_0} X_i $$

Thus,

$$ \mathbb{E} [\text{# of Elements} < \frac{t}{F_0}] = \mathbb{E} [\sum_{i=1}^{F_0} X_i] \\ = \sum_{i=1}^{F_0} \mathbb{E}[X_i] $$

By linearity of expectation. Note that by virtue of $X_i$'s being indicator random variables, and independently identically distributed, we have that

$$ \mathbb{E}[X_i] = 1 \cdot \mathbb{P}[X_i=1] + 0 \cdot \mathbb{P}[X_i=0] = \frac{t}{F_0} $$

For all $1 \leq i \leq F_0$. Substituing, we get that

$$ \mathbb{E} [\text{# of Elements} < \frac{t}{F_0}] = \sum_{i=1}^{F_0} \mathbb{E}[X_i] = \sum_{i=1}^{F_0} \frac{t}{F_0} = t $$

$\endgroup$
1
  • $\begingroup$ Thank you very much! $\endgroup$
    – Ilian kurt
    Nov 16, 2022 at 15:22
0
$\begingroup$

If you cut the interval in 5 pieces of length 1/5 and pick one then you would expect an element drawn uniformly at random to have chance 1/5 to belong to it. So for, say t =3, an interval of length 3/N the chance is 3/N. Hence you would expect 3 out of N draws to belong to it. Apply this to the interval with boundary 0 and 3/N.

$\endgroup$
1
  • 1
    $\begingroup$ Also to you: Thank you very much! $\endgroup$
    – Ilian kurt
    Nov 16, 2022 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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