For any permutation $\sigma = (\sigma_1,\dots,\sigma_n)$, call $\sigma_k$ a record if $\sigma_k>\sigma_i$ for $1\le i\le k-1$. Let $\alpha_k$ be the indicator for the event that $\sigma_k$ is a record. I know that $P(\alpha_k=1)=\frac{1}{k}$.
My question: how can I show that the collection $\{\alpha_i:1\le i\le n\}$ is independent?
One method I tried was induction on $k$, where $k$ is the number of $\alpha_i$ we show are jointly independent. This got me nowhere. I also know that specifying which of the $\alpha_i$s are 1s uniquely specifies another permutation written in cycle notation (with some conditions on ordering).
Are there some sufficient conditions for independence that can ease the problem? Or equivalent combinatorial reasoning?
I think the straightforward approach is easiest. We know
$$P(\alpha_k=1)=\frac1k,\quad P(\alpha_k=0)=1-\frac1k$$
Let $(a_1,a_2,\ldots,a_n)$ be an $n$-element sequence from $\{0,1\}^n$ and then joint independece of the $\{\alpha_i\}_{1\le i\le n}$ means that we need to show
$$P(\alpha_1=a_1, \alpha_2=a_2,\ldots,\alpha_n=a_n)=P(\alpha_1=a_1)\times P(\alpha_2=a_2)\times\ldots P(\alpha_n=a_n) \tag{1}\label{eq1}$$
for all such sequences.
This can be done via mathematical induction.
Induction start ($n=1)$: Nothing to prove, the left and right hand side of \eqref{eq1} are exactly the same.
Induction step ($n=k\to n=k+1$): If $a_{k+1}=1$, then $\alpha_{k+1}=1$ is equivalent to $\sigma_{k+1}=k+1$. Under the condition $\sigma_{k+1}=k+1$ (with probability $\frac1{k+1}$), we have that ($\sigma_1,\sigma_2,\ldots,\sigma_k$) is a permutation of $(1,2,\ldots,k)$, uniformly distributed. So
$$ \begin{array}{} P(\alpha_1=a_1, \alpha_2=a_2,\ldots,\alpha_{k+1}=1) & = & P(\alpha_1=a_1, \alpha_2=a_2,\ldots,\alpha_k=a_k)P(\alpha_{k+1}=1)\\ & = & P(\alpha_1=a_1)\times P(\alpha_2=a_2)\times\ldots P(\alpha_k=a_k)\times P(\alpha_{k+1}=1) \end{array}$$
where the second equality follows from induction hypothesis. This is what we needed to prove for the induction step in that case $(a_{k+1}=1)$.
If $a_{k+1}=0$, then $\alpha_{k+1}=0$ is equivalent to $\sigma_{k+1}<k+1$. There are $k$ possible values for $\sigma_{k+1}:1,2,\ldots,k$. Then we have
$$P(\alpha_1=a_1, \alpha_2=a_2,\ldots,\alpha_{k+1}=0) = \sum_{i=1}^k P(\alpha_1=a_1, \alpha_2=a_2,\ldots,\alpha_k=a_k,\sigma_{k+1}=i) \tag{2}\label{eq2}$$
For any $i$, this means $(\sigma_1,\sigma_2,\ldots,\sigma_k)$ is a permutation of $\{1,2,\ldots,k+1\}\backslash\{i\}$. This is not the set $\{1,2,\ldots,k\}$ as in the induction hypothesis, but the map
$$r:\{1,2,\ldots,k+1\}\backslash\{i\} \to \{1,2,\ldots,k\}$$
with
$$r(1)=1, r(2)=2, \ldots, r(i-1)=i-1, r(i+1)=i, \ldots r(k+1)=k$$
is an order-isomorphism between those 2 sets. Since the definition of $\alpha_j$ only depends on the order relation between the $\sigma_j, \sigma_l$, we see get
$$P(\alpha_1=a_1, \alpha_2=a_2,\ldots,\alpha_k=a_k,\sigma_{k+1}=i) = \frac1{k+1}P(\alpha_1=a_1, \alpha_2=a_2,\ldots,\alpha_k=a_k)$$
This means the right hand side in \eqref{eq2} is a sum of $k$ identical values, and when we apply the induction hypothesis, we get:
$$ \begin{array} P(\alpha_1=a_1, \alpha_2=a_2,\ldots,\alpha_{k+1}=0) & = & k\frac1{k+1}P(\alpha_1=a_1, \alpha_2=a_2,\ldots,\alpha_k=a_k)\\ & = & P(\alpha_1=a_1)\times P(\alpha_2=a_2)\times \ldots P(\alpha_k=a_k)\frac{k}{k+1}\\ & = & P(\alpha_1=a_1)\times P(\alpha_2=a_2)\times \ldots P(\alpha_k=a_k)\times P(\alpha_{k+1}=0) \end{array} $$
This concludes the induction step for the second case $(a_{k+1}=0)$ and we are done!