Let $NB(r,p) \in \{0,1,2,\ldots\}$ be a negative binomial random variable https://en.wikipedia.org/wiki/Negative_binomial_distribution, which has $\mathbb{P}\left( NB(r,p) = k \right) = \binom{k+r-1}{k}(1-p)^k p^r $ $NB(r,p)$ is realized by flipping Heads-$1-p$-and-Tails-$p$-coin until the $r$-th Tails comes up, and then counting the number of heads that appeared until then: $NB(r,p) = \text{Number of heads that appear before the }r\text{-th Tails appears}$ We prove the following about the median of the negative binomial when $p=\frac{1}{2}$ (i.e. the coinflips are ordinary fair coinflips) **Proposition** Define $X_n = NB(n,\frac{1}{2}) - n$ to be the "centered" negative binomial of parameter $\frac{1}{2}$. The median of $X_n$ is 0 in the sense that the following probabilities are *exactly* 50% for any $n \geq 1$: $\begin{align} \mathbb{P}\left( X_n \leq -1 \right) &= 50\% \\ \mathbb{P}\left( X_n \geq \phantom{-}0 \right) &= 50\% \end{align} $ *Remark*: Note that depending on how you "break the tie for the median" so to speak, you can get either $0$ or $-1$ (or anything in between!) as the value of the median. For example the paper "A refined continuity correction for the negative binomial distribution and asymptotics of the median" by Ouimet seems to have the median is either 0 or -1 depending on the parity of $n$. **Lemma 1** : The following identity for binomial coefficients holds for any $n$: $\begin{align} \binom{2n-1}{n} &= \binom{2n-2}{n-1}+\binom{2n-3}{n-1}+\ldots+\binom{2n-1-n}{n-1}\\&=\sum_{k=1}^n \binom{2n-1-k}{n-1}\end{align}$ This identity can be visualized as summing along a diagonal on [[Pascal's Triangle]], for example when $n=4$ there is a sum of four terms along a diagonal leading up to the $7$-th row: ${\displaystyle {\begin{array}{c}1\\1\quad 1\\1\quad 2\quad 1\\\mathbf{+1}\quad 3\quad 3\quad 1\\1\quad \mathbf{+4}\quad 6\quad 4\quad 1\\1\quad 5\quad \mathbf{+10}\quad 10\quad 5\quad 1\\1\quad 6\quad 15\quad \mathbf{+20}\quad 15\quad 6\quad 1\\1\quad 7\quad 21\quad 35\quad \mathbf{=35} \quad 21\quad 7\quad 1\end{array}}}$ *Proof*: We do a proof by [[Double Counting Proofs]] (see also the [Wikipedia Page](https://en.wikipedia.org/wiki/Double_counting_(proof_technique))). Imagine we have a collection of $2n-1$ distinct balls labeled $1,2,3\ldots,2n-1$ . The LHS counts the number of ways to choose any subset with $n$ balls from the collection. The $k$-th term on the RHS, namely $\binom{2n-1-k}{n-1}$ counts the number of ways to choose n balls such that the *label of the lowest numbered ball chosen* is exactly $k$. (To do this: first choose the ball labeled $k$, then choose $n-1$ other balls from the balls labeled $k+1,k+2,\ldots,2n-1$ of which there are $2n-1-k$ to choose from.) Adding up over all such $k$ gives all the possible ways to choose all the subsets of size $n$ (note that the lowest numbered ball *must* be some number from $1$ to $n$ ). **Lemma 2**: Recall the definition of the centered negative binomial variable. $X_n = NB(n,\frac{1}{2})-n$. This satisfies: $\begin{align}\mathbb{P}\left(X_n = 0\right) &= \frac{1}{2}\mathbb{P}\left(X_n = -1\right) + \frac{1}{4}\mathbb{P}\left(X_n = -2\right)+\ldots+\frac{1}{2^n}\mathbb{P}\left(X_n = -n\right) \\ &= \sum_{k=1}^n \frac{1}{2^k}\mathbb{P}\left(X_n = -k\right) \end{align}$ *Direct Proof using the Binomial Idenity*: Using the formula $\mathbb{P}\left( NB(r,p) = k \right) = \binom{k+r-1}{k}(1-p)^k p^r $ we have: $\mathbb{P}\left(X_n = x\right)= \binom{2n+x-1}{n+x}2^{-(2n+x)}$, whence the identity to be proven is equivalent to $\begin{align} \binom{2n-1}{n}2^{-2n} &= \frac{1}{2}\binom{2n-2}{n-1}2^{-(2n-1)} + \frac{1}{4}\binom{2n-3}{n-2}2^{-(2n-2)}+\ldots+ \\ &= \sum_{k=1}^n \frac{1}{2^k}\binom{2n-1-k}{n-k}2^{-(2n-k)} \end{align}$ Multiplying both sides by $2^{-2n}$ , we see this is precisely the result of Lemma 1. *Alternative Sneaky Proof:* The identiy can also be written as $\mathbb{P}(X_n + G =0) = \mathbb{P}(X_n =0)$ for an independet geometric 1/2 , $G \in \{1,2,3\ldots\}$. One can enumerate $\mathbb{P}(X_n + G =0)$ as the ways to arrange $2n$ coins so there are exactly, $n$ Heads and $n$ Tails, and the sequnce ends in a Heads (since $G \geq 1$). On the other hand, $\mathbb{P}(X_n = 0)$ is the number of ways to arrange $n$ Heads and $n$ Tails so that it ends in a Tails. Both these enumerations are equal by the bijection of replacing Heads to Tails and vice versa (or you could count them both to see they are $\binom{2n-1}{n-1}2^{-2n}$ for both) *Proof of Proposition*: We proceed by induction. The base case, when $n=1$ holds because $X_1 \stackrel{d}{=} G - 2$ where $G \sim Geom(1/2) \in \{1,2,\ldots\}$ is a centered geometric random variable and satisfies $\mathbb{P}(X_1 = -1) = 0.5, \mathbb{P}(X_1 \leq -2) = 0$. Now suppose that the statement holds true for $n$. Observe that: $X_{n+1} \stackrel{d}{=} X_{n} + G -2$ where $G \sim Geom(1/2) \in \{1,2,\ldots\}$ is an independent geometric random variable of mean 2. From this, we can observe the change in the probability that $\mathbb{P}(X_n \leq -1)$ by counting the probability flux in vs probability flux out of this event. Observe that the flux in (i.e. $X_n$ to change from being not $\leq -1$ to $X_{n+1}$, being $\leq -1$), can only happen if $X_n = 0$ and $G = 1$ (since the minimum value for $G-2$ is $-1$). Similarly, to see the flux out, we can also enumerate all the ways that $X_n$ can change from being $\leq -1$ to $X_{n+1}$ being not $\leq -1$ as summing over $X_{n} = -k$ and $G \geq k+2$. Hence we can compute the difference as the probability flux in minus probability flux out: $\begin{align} & \mathbb{P}\left(X_{n+1} \leq -1\right) - \mathbb{P}\left(X_{n} \leq -1\right)\\ =& \mathbb{P}\left(X_n =0,G = 1\right) -\sum_{k=1}^{\infty} \mathbb{P}(X_n = -k,G \geq k+2) \\ =& \frac{1}{2} \mathbb{P}(X_n = 0) - \sum_{k=1}^{\infty} \frac{1}{2^{k+1}} \mathbb{P}(X_n = -k)\\ =& 0\end{align} $ where we have used independence of $G$ and $X_n$ and the fact that $\mathbb{P}(G \geq x) = \frac{1}{2^{x-1}}$. The last equality, that this is exactly 0, follows by Lemma 2. Hence, by the induction hypothesis, $\mathbb{P}\left(X_{n+1} \leq -1\right) = \mathbb{P}\left(X_{n} \leq -1\right) = 50\%$, as desired.