Probability of the record, its expected value and variation

Question

I have a problem with evaluating the probability $P(A_k)$, where $A_k$ is a probability of the event that $\pi(k)$ is a record and $\pi$ is uniformly chosen random permutation from a set $\{1,2,\ldots,n\}$. Record occurs when $\pi(k)>\pi(j)$ for $j=1, \ldots, k-1$. We can see that $$P(A_k)=P(\pi(k)>\pi(j), j=1, \ldots, k-1)$$ so I think the probability will be equal to $\left(\dfrac{1}{2}\right)^{k-1}$, in particular we have $P(A_1)=1$, $P(A_2)=\dfrac{1}{2} $, etc. Is this correct?
My second question corresponds to evaluation of $EX_n$ and $VarX_n$ where $X_n$ is an amount of records. I have found something connected here Expected value and variance of records, but I'm not sure if it is right in my case.
Thanks for all advices and help in advance.

Answer 1

I managed to evaluate the expected value, so I'm publishing the solution if someone would be interested.
We have
$EX_1=x_1p_1=1\cdot\frac{1}{1!}=1,$
$EX_2=\sum\limits_{i=1}^{2}x_ip_i=1\cdot\frac{1}{2!}+2\cdot\frac{1}{2!}=1\frac{1}{2},$
$EX_3=\sum\limits_{i=1}^{3}x_ip_i=1\cdot\frac{2}{3!}+2\cdot\frac{3}{3!}+3\cdot\frac{1}{3!}=1\frac{5}{6},$
$EX_4=\sum\limits_{i=1}^{4}x_ip_i=1\cdot\frac{6}{4!}+2\cdot\frac{14}{4!}+3\cdot\frac{3}{4!}+4\cdot\frac{1}{4!}=1\frac{23}{24}.$
So as we can see $EX_n=1\frac{n!-1}{n!}$ which may be easily proven by method of induction.

Answer 2

I think you can apply the solution from Expected value and variance of records. Let's take a closer look. Let $A_k=1$ if $\pi(k)$ is a record and $A_k=0$ else. It holds $$P(A_k=1)=P(\pi(k)=\max(\pi(1),\dots,\pi(k)))=\frac{1}{k}$$ and therefore $$P(A_k=0)=\frac{k-1}{k}.$$ For any $k$ we have $$EA_k=0\cdot P(A_k=0)+1\cdot P(A_k=1)=\frac1k.$$ With $X_n=\sum_{k=1}^nA_k$ we have $$EX_n=\sum_{k=1}^nEA_k=\sum_{k=1}^n\frac1k.$$ Let's now look at the Variance. \begin{align*}\operatorname{Var}(A_k)&=(0-EA_k)^2\cdot P(A_k=0)+(1-EA_k)^2\cdot P(A_k=1)\\&=\frac{1}{k^2}\cdot\frac{k-1}{k}+\left(1-\frac1k\right)^2\cdot\frac{1}{k}\\&=\frac{k-1}{k^3}+\frac{(k-1)^2}{k^3}\\&=\frac{k-1}{k^2}\\&=\frac1k\left(1-\frac1k\right)\end{align*} and therefore we have $$\operatorname{Var}(X_n)=\sum_{k=1}^n\operatorname{Var}(A_k)=\sum_{k=1}^n\frac1k\left(1-\frac1k\right).$$