Non-recursive solution to expected size of set

Question

Let $F(A)$ be a function on an ordered set $A = \{A_1, A_2, \dotsc, A_n\}$ that outputs a set $B$ such that the elements of $B$ are determined as follows.

$A_i\in B$ if $A_i > A_{i-1}, A_{i-2}\dotsc ,A_1$. That is, an element is in $B$ if it is larger than all of its preceding elements.

Given that an ordered set $A$ has cardinality $n$, what is the expected value of the cardinality of $F(A)$?

I have a recursive solution; if $A$ has cardinality $n = 1$, $E[|F(A)|] = 1$. When looking at $n = 2$ it's equivalent to taking $A$ and randomly inserting a larger element $a_2$ into $A$. From $\{a_1\}$ we have either $\{a_1, a_2\}$ or $\{a_2, a_1\}$. We can reduce the case into either $E[|F(1)|] + 1$ or $1$ all with equal probability giving us an expected value of $\frac{1}{2}(E[|F(1)|] + 1 + 1) = 1 + \frac{1}{2}(E[|F(1)|])$. We can extend this to any cardinality $n$ as just expressing it as $1 + \frac{1}{n}(E[|F(n-1)|] + E[|F(n-2)|] \dotsb + E[|F(1)|])$.

I'm asking if there's a solution that does not rely on knowing the expected values of $F(1)$ to $F(n-1)$.

Answer 1

Your recurrence has explicit solution: $$E[|F(n)|] = H_n,$$ where $H_n$ is the $n$th harmonic number.