I am reading Introduction to Algorithms by CLRS and saw the probabilistic analysis of the Hiring assistant problem
Problem : $n$ people appear randomly for a job interview for an assistant . We hire person $i$ if the person is better than all the persons before him i.e $0-(i-1)$ . Calculate the average number of times a new assistant is hired ?
The problem was solved using Random indicator variables given below :
Now from
\begin{align} E\left[ X\right] =\sum _{x=1}^{n}xP\left( X=x\right) \\=\sum _{i=1}^{n}E\left[ X_{i}\right] \\. \end{align}
\begin{align} E\left[ X\right] =\sum _{i=1}^{n}i\cdot P\left( X=i\right) =\sum E\left[ X_{i}\right] \\=\sum _{i=1}^{n}\frac {1} {i} \end{align}
Changing variable from \begin{align} x\rightarrow i \end{align}
\begin{align} \Rightarrow \sum i\cdot P\left( x=i\right) =\sum i\cdot \frac {1} {i^{2}}\\\Rightarrow P\left( X=i\right) =\frac {1} {i^{2}}\\. \end{align} But \begin{align} \forall iP\left( X=i\right) =\frac {1} {i^{2}}\\, \end{align} seems wrong
Can someone explain :
1.How to calculate \begin{align} P\left( X=i\right) \exists i\leq n \end{align}
2.In the method given in Cormen can someone explain intuitively how the Expected value of $X$ is given by $ \sum _{i=1}^{n}P(i)$ . That is sum of probabilities of hiring candidate $i$
3.Also in a broader aspect what is the use of indicator random variables and how should they be used in problems