What is the distribution of a binomial variable where the number of trials is itself random?

Question

We do the following experiment:

• Select a random element $k$ from $\{1,\dots,n\}$.
• Toss $k$ fair coins.
• Define $X$ = the number of heads.

What is the distribution of $X$?

Given $k$, the variable $X$ is binomial and distributed as $Bin[k,1/2]$. But here, $k$ itself is also selected at random.

So what is the distribution of $X$, as a function of $n$?

EDIT: I now found out that the expected value of $X$ is given by Wald's equation, since both $k$ and the coins have a finite expectation:

$$ E[X] = E[k] \cdot E[coin] = \frac{n+1}{2}\cdot \frac{1}{2} = \frac{n+1}{4}$$

Answer 1

ETA: Did's comment reminds me that the lower limit on the sum should be no lower than $1$.

Let $K$ be the number of coins flipped:

\begin{align} P(X = x) & = \sum_{k=x}^n P(K=k) P(X=x \mid K=k) \\ & = \sum_{k=x}^n \frac{1}{n} \binom{k}{x} \frac{1}{2^k} \\ & = \frac{1}{n} \sum_{k=x}^n \binom{k}{x} \frac{1}{2^k} \end{align}

Wolfram Alpha expands this last as

$$ P(X = x) = \frac{1}{n} \left(2 - \frac{1}{2^{n+1}}\binom{n+1}{x} {}_2F_1\left (1, n+2; n-x+2; \frac{1}{2}\right) \right) $$

where $_2F_1(a, b; c; z)$ is "the" hypergeometric function. So that turned out to be more complex than I had anticipated.

Answer 2

The Moment Generating Function is rather nice.

$$ \mathbb E[e^tX] = \mathbb E\left[ \mathbb E[e^tX \mid K]\right] = \mathbb E \left[ ((1+e^t)/2)^K \right] = \dfrac{1}{n} \sum_{k=1}^n \left(\dfrac{1+e^t}{2}\right)^k = \dfrac{((1+e^t)/2)^{n+1} - (1+e^t)/2}{n(e^t-1)/2}$$