1
$\begingroup$

Suppose we have $n$ balls in a basket, labeled $1, 2, \dotsc , n$. We continuously take out balls from the basket, until we have two consecutive balls in our possession (in other words, we stop after we've taken out both balls $k$ and $k+1$). What is the expected numbers of balls we take out?

Edit: One approach is use summation by computing probability for $k$ balls. That gives answer of $\sum_{k=2}^n \frac{(k-2){n-k+2\choose k-1}+k{n-k+1\choose k-1}}{{n\choose k}}$ but it is very difficult for simplifcation.

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Xander Henderson
    Oct 20, 2021 at 14:28

1 Answer 1

1
$\begingroup$

The underlying assumption behind your question is that your summation can be simplified, and you ask asking how. I argue it cannot be significantly simplified.

Letting $X$ be the number of balls drawn, $$ E[X]=\sum_{t=0}^\infty P(X>t)=\sum_{t=0}^{\lceil n/2 \rceil}\frac{\binom{n-t+1}t}{\binom nt} $$ The first equation is a well known way to write the expected value of a positive discrete random variable, while the second follows from the fact that the number of ways to select $t$ non-adjacent elements from $\{1,\dots,n\}$ is $\binom{n-t+1}t$, which can be proven with stars and bars.

If we run the function ${\binom{n-t+1}t}/{\binom nt}$ through Zeilberger's algorithm, we see that $S_n:=\sum_{t=0}^{\lceil n/2\rceil} {\binom{n-t+1}t}/{\binom nt}$ satisfies the recurrence $$ (n+3)S_n+(2n+5)S_{n+1}-3(n+2)S_{n+2}=1 $$ Then, using Petkovšek's algorithm, you can show that the above recurrence equation does not have any hypergeoemtric solutions. This heavily suggests that there is no closed form at all, since pretty much every closed form in combinatorics is hypergeometric.

One last point; technically, there are other closed forms $S_n$ could have besides hypergeometric. For example, expressions involving $n\log n$ and $n^n$ are not ruled out by my algorithm. Roughly, I have only ruled out expressions involving addition/subtraction, multiplication/division, exponentiation with constant bases, and factorials (and more generally, multifacotrials). Still, all of the summands of $S_n$ are hypergeometric terms, and in my experience sums like this either have a hypergeometric closed form or none.

$\endgroup$
2

You must log in to answer this question.