Expected value for advent of code (average case complexity)

Question

With the upcoming advent of code I was looking at past problems and noted that one was easily solved with an algorithm such that for a length $n$ array, the algorithm finishes as soon as you encounter the second of two numbers that are randomly distributed within it.

I was trying to figure out the expected value for the number of items you need to look at out of $n$ randomly distributed items before finding two values of interest, but my probability is rusty.

I think I could finish the problem if I could nail down the combinatorics, but my combinatorics is too rusty.

There are clearly $n!$ ways to arrange $n$ items. The number of ways for the two items of interest to be in the first two items you look at is clearly $2$, so the expected value is $2\cdot 2/n!+3\cdot a_3/n!+\cdots +n\cdot a_{n}/n!$

I think if I could figure out the number of ways to arrange the 2 different items in a line of length $k$, then $a_k$ should be that number minus all the ways for $k-1$.

Am I okay so far? Can you help me finish the combinatorics solution?

I'm open to other smarter ways to solve the problem too but I'd like in particular to figure out the combinatorics.

What's the expected value?

Answer 1

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}$$

Answer 2

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$.

Answer 3

Suppose there are $a$ objects of interest among $n$ objects instead of $2$ of interest like in the question. We solve it via linearity of expectation and a different combinatorics approach.

The chance a given object of noninterest occurs after $a$ objects of interest is $1/(a+1)$ so the expectation to encounter any individual object is $a/(a+1)$. By linearity of expectation the expectation for how many of the $n-a$ objects you see is $a(n-a)/(a+1)$. The total number of objects you look at is then $a(n-a)/(a+1)+a$ which simplifies to $a(n+1)/(a+1)$ and answers my question when $a=2$.

Let the binomial coefficient/combination be $C(a,b)$. There are $C(n,a)$ ways to choose which $a$ items are the items of interest. If the last item of interest is at position $k$, there are $a-1$ remaining items of interest to be fit into the previous $k-1$ items, so $C(k-1,a-1)$ is the number of ways to choose them. Therefore the probability $P(k)$ you've found all $a$ items of interest in exactly $k$ items is $C(k-1,a-1)/C(n,a)$. The expectation is therefore $\sum_{k=a}^{n}kC(k-1,a-1)/C(n,a)$ which simplifies to $a(n+1)/(a+1)$.