Distribution of random variable 'Time to n-th maximum'

110 Views Asked by At

Let $\{X_1, X_2, ...\}\overset{iid}{\sim}~\mathcal{D}$ is a time series of iid random variables drawn from a continuous distribution $\mathcal{D}$.

How can I calculate the distribution of a random variable $T(n)$, the time to the $n$th maximum, where $T(n)$ is constructed as follows:

$T(1) = 1$

$T(2) = \text{ The lowest index }k\text{, where } X_k > X_1$

$\vdots$

$T(n) = \text{ The lowest index }k\text{ , where }X_k > X_{T(n-1)} $

1

There are 1 best solutions below

0
On BEST ANSWER

Since the $X_i$ are idd and continuous, every of the $n!$ orderings of the vector $(X_1,X_2,\dots,X_n)$ are equally likely. Given a permutation $\pi_1,\pi_2,\dots,\pi_n$ of $\{1,2,\dots,n\}$, call an index $i$ a record if $\pi_i>\pi_j$ for all $j<i$, with the convention that $1$ is always a record. Then $P(T(k)=n)$ is equal to the number of permutations $\pi$ of $\{1,2,\dots,n\}$ which have exactly $k$ records where one of the records is $n$, divided by ($n!$). There permutations all have $\pi_n=n$, so that we can instead count the number of permutations of $\{1,2,\dots,n-1\}$ with exactly $k-1$ records.

It turns out that there is not a nice closed formula for the number of these permutations. They are known as the Stirling numbers of the first kind, written either as $s(n,k)$ or $n\brack k$. That is, $$ \boxed{P(T(k)=n)=\frac1{n!}{n-1\brack k-1}.} $$ The Stirling numbers can be computed recusively using $$ {n\brack k}={n-1\brack k-1}+(n-1){n-1 \brack k},\\{0\brack0}=1,\qquad{0\brack n}=0\quad\text{ for }n>0. $$


Fun fact: the expected value of $T_2$ is infinity. Therefore, if you are selling your car and $X_i$ is the amount of money that the $i^\text{th}$ person you talked to offered for the car, then the expected time it takes to get an offer better than your first offer is infinite!