## 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 :

### 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