Archive for the ‘Uncategorized’ Category

Expected value of minimum of n i.i.d U(0,1) random variables

January 23, 2017

What is the expected value of minimum of n i.i.d random variables that are drawn from U(0,1) distribution

Let u_1, u_2, ... , u_n are the n random variables.

Let X = min(u_1, u_2, ... , u_n)

Plan of Action

  1. Find CDF for X
  2. Find PDF for X using CDF
  3. Compute E[X] = \int_{0}^{\infty} x\, f_X(x) \,dx

\begin{array}{rcl} F_X(x) &=& P(X \leq x) \\ &=& 1-P(X>x) \\ &=&  1- [ P(u_1>x) \wedge P(u_2>x) \wedge \dots \wedge P(u_n>x) ] \\ &=& 1-(1-x)^n \end{array}

Note that F_X(x) = \int_{-\infty}^{x} f_X(t) \,dt

Thus f_X(x) = \frac{d}{dx}F_X(x)

so f_X(x) = n (1-x)^{n-1}

\begin{array}{rcl} E[X] &=& \int_{0}^{\infty} x f_X(x) \,dx \\ &=&n \,\int_{0}^{1} x\,(1-x)^{n-1}\, dx \\ &=&\frac{1}{n+1} \end{array}

Alternative way :

For non-negative random variables, some times it is easy to calculate expected value of random variable using following formula :

E[X] = \int_{0}^{\infty} P(X>x) \,dx

\begin{array}{rcl} P(X>x) &=& P(u_1>x) \wedge P(u_2>x) \wedge \dots \wedge P(u_n>x) \\ &=&  (1-x)^n \end{array}

Since in our case X cannot take value greater than 1

E[X] = \int_{0}^{1} P(X>x) \, dx =\int_{0}^{1}(1-x)^n \,dx = \frac{1}{n+1}


Proof from THE BOOK via vectors

September 3, 2016

Theorem : no matter what quadrilateral you start with, you always get a parallelogram when you connect the midpoints.

Proof : quadrilateral-midpoints-vectors

Distance travelled on average between successive seeks

August 26, 2014

Assuming that next I/O request resides in any cylinder with equal probability, what is the distance travelled by head, on average, between successive seeks on disk with n cylinders.

D = random variable denoting the distance travelled between successive seeks

\begin{array}{rcl} E[D] &=& \sum_{d=0}^{n-1} d . pr(D=d) \\ &=& 0 . \frac{n}{n^2} + \sum_{d=1}^{n-1} d . \frac{2(n-d)}{n^2} \\ &=& \frac{n^2-1}{3n} \\ &\approx& \frac{n}{3} \end{array}

So, if all cylinders have equal probability of access, the average seek distance is 1/3 the maximum seek