Binomial-Like Distribution with Changing Probability

Question

The Question

Assume we have $n$ multiple choice questions, the $k$-th question having $k+1$ answer choices. What is the probability that, guessing randomly, we get at least $r$ questions right?

If no general case is available, I am OK with the special case $r = \left\lfloor\frac{n}{2}\right\rfloor + 1$.

Example

Assume we have four different multiple choice questions.

1. Question 1

   • Choice A
   • Choice B

2. Question 2

   • Choice A
   • Choice B
   • Choice C

3. Question 3

   • Choice A
   • Choice B
   • Choice C
   • Choice D

4. Question 4

   • Choice A
   • Choice B
   • Choice C
   • Choice D
   • Choice E

If we choose the answer to each question at random, what is the probability we get at least three right? (By constructing a probability tree, I get the answer as $11/120$.)

Answer 1

Let $U_k$ be an indicator random variable, equal to 1 if the $k$-th question has been guessed correctly. Clearly $(U_1, U_2,\ldots,U_n)$ are independent Bernoulli random variables with $\mathbb{E}\left(U_k\right) = \frac{1}{k+1}$.

The total number of correct guesses equals: $$ X = \sum_{k=1}^n U_k $$ The moment generating function of $X$ is easy to find: $$ \mathcal{P}_X\left(z\right) = \mathbb{E}\left(z^X\right) = \prod_{k=1}^n \mathbb{E}\left(z^{U_k}\right) = \prod_{k=1}^n \frac{k+z}{k+1} = \frac{1}{z} \frac{(z)_{n+1}}{(n+1)!} = \frac{1}{(n+1)!} \sum_{k=0}^n z^k s(n+1,k+1) $$ where $s(n,m)$ denote unsigned Stirling numbers of the first kind. Thus:$$ \mathbb{P}\left(X=m\right) = \frac{s(n+1,m+1)}{(n+1)!} [ 1 \leqslant m \leqslant n ] $$ The probability of getting at least $r$ equals: $$ \mathbb{P}\left(X \geqslant r\right) = \sum_{m=r}^{n} \frac{s(n+1,m+1)}{(n+1)!} $$

This reproduces your result for $n=4$ and $r=3$.

In[229]:= With[{n = 4, r = 3}, 
 Sum[Abs[StirlingS1[n + 1, m + 1]]/(n + 1)!, {m, r, n}]]

Out[229]= 11/120

Here is the table for $1 \leqslant n \leqslant 11$: