Expected value for advent of code (average case complexity)

Answer: The expected number of objects looked at is $\frac23(n-2)+2$.

Call the special objects you need to collect $A$ and $B$, and let $X$ be an arbitrary other object. What is the probability that you will look at $X$ before looking at both $A$ and $B$? The answer is $2/3$. This can be seen by listing all $3!=6$ orderings for the objects $A$, $B$, and $X$, and counting that there are $4$ orderings where $X$ is not last.

Since there are $n-2$ other objects besides $A$ and $B$, and each has a probability of $2/3$ of being looked at, linearity of expectation implies that the expected number of other objects seen is $\frac23(n-2)$. To get the total number of objects looked at, we add two to that, for $A$ and $B$.

Define $P(k)$ to be the probability that it takes $k$ searches to find both items of interest. There are $n!$ ways to arrange the $n$ objects. You will find $A$ and $B$ in exactly $k$ searches if one of $A$ or $B$ is the $k^\text{th}$ object you search and the other is searched before. There are $2$ ways to choose which special item is the $k^\text{th}$ object searched, and there are $k-1$ ways to choose where to put the other special item. There are $(n-2)!$ ways to arrange the other items.

Hence, $P(k)=\frac{2(n-2)!(k-1)}{n!}=\frac{2(k-1)}{n(n-1)}$. The expected value is $$\sum_{k=1}^n P(k)k$$ $$=\sum_{k=1}^n \frac{2k(k-1)}{n(n-1)}$$ $$=\frac{4}{n(n-1)}\sum_{k=2}^n \frac{k(k-1)}{2}$$ $$=\frac{4}{n(n-1)}\sum_{k=2}^n \binom{k}{2}$$ $$=\frac{4}{n(n-1)}\binom{n+1}{3}$$ $$=\frac{2(n+1)}{3}$$