Consider a sequence of independent $0$-or-$1$ outcomes $X_1, \ldots, X_n,\ldots$, such that $\mathbb{P}(X=1)=p$. The discrete time process $\left(Y_n\right)_{n \geqslant 0}$, such that $$Y_n = \sum_{k=1}^n X_k$$ is called binomial process. Let $\tau_i$ denote ordinal numbers where $X_{\tau_i}=1$. These are event times of the binomial process. Letting $\tau_0=0$, the times between events, $T_i = \tau_{i}-\tau_{i-1}$ are independent and follow Pascal distribution: $$ \mathbb{P}\left(T_i = r\right) = p (1-p)^{r-1} [ r \geqslant 1 ] $$ Clearly $\tau_i < \tau_j$ for all $i<j$.

Q: For a fixed $n > 0$, given $Y_n = m > 0$, I am seeking to determine the distribution of event times $ (\tau_1, \ldots, \tau_m)$.

On other words, for a fixed $0 < m \leqslant n$, I am seeking to determine the distribution of $(T_1, T_1+T_2, \ldots, T_1+\cdots+T_m)$ given that $T_1+\cdots+T_m \leqslant n$ and $T_1+\cdots+T_m +T_{m+1} > n$.

The question is motivated by oft-drawn analogy of binomial process and Poisson process, and the nice corresponding result for the Poisson process, where interarrival times are exponentially distributed, and conditional on there being $m$ events on the interval $(0, \tau)$, arrival times are order statistics of uniform distribution on $(0,\tau)$. I am hoping some similarly neat result could be established for the case of binomial process as well.


Conditionally on $[Y_n=m]$ the set $T=\{\tau_k\mid1\leqslant k\leqslant m\}$ is uniformly distributed on the space $\mathfrak T_m$ of subsets of size $m$ of $\{1,2,\ldots,n\}$.

Proof: for every $t$ in $\mathfrak T_m$, the event $[T=t]$ has absolute probability $p^m(1-p)^{n-m}$. This probability does not depend on $t$ in $\mathfrak T_m$ hence the result follows. In particular, $$ \mathbb P(T=t\mid Y_n=m)=|\mathfrak T_m|^{-1}={n\choose m}^{-1}. $$ For example, the number of $t$ in $\mathfrak T_m$ such that $\min t=k$ is $$ {n-k\choose m-1}, $$ hence $$ \mathbb P(\tau_1=k\mid Y_n=m)={n-k\choose m-1}\cdot{n\choose m}^{-1}. $$

  • $\begingroup$ +1 and Thanks! After seeing your answer, I also came up with more brute-force demonstration. $\endgroup$ – Sasha Feb 28 '13 at 20:09

Although not nearly as elegant as @Did's proof, here is a brute-force one. Denote the event $\mathcal{E}_{n,m} = \{Y_n=m\}=\{ T_1+\cdots+T_m \leqslant n, T_1+\cdots+T_m + T_{m+1} > n \}$. Then we are after $$ \mathbb{P}\left(\tau_1=r_1,\tau_2=r_2,\ldots,\tau_m=r_m \mid \mathcal{E}_{n,m} \right) = \frac{ \mathbb{P}\left(T_1=r_1,T_2=r_2-r_1,\ldots,T_m=r_m-r_{m-1},T_{m+1}>n-r_m\right)}{ \mathbb{P}\left(\tau_m \leqslant n, \tau_m + T_{m+1} > n\right) } \tag{1} $$ Using the independence, the numerator reads: $$\begin{eqnarray} \mathbb{P}\left(T_{m+1}>n-r_m\right) \prod_{k=1}^m \mathbb{P}\left(T_k=r_k - r_{k-1}\right) &=& (1-p)^{n-r_m} \prod_{k=1}^m \left( p (1-p)^{r_k-r_{k-1}-1}\right) \\ &=& p^m (1-p)^{n-m} \end{eqnarray} $$ The denominator reads: $$ \begin{eqnarray} \sum_{k=m}^n \mathbb{P}\left(\tau_m=k\right) \mathbb{P}\left(T_{m+1}>n-k\right) &=& \sum_{k=m}^n \binom{k-1}{m-1} p^m (1-p)^{k-m} (1-p)^{n-k} \\ &=& p^m (1-p)^{n-m} \sum_{k=m}^n \binom{k-1}{m-1} \end{eqnarray} $$ Using $\binom{k-1}{m-1} = \binom{k}{m} - \binom{k-1}{m}$ the sum telescopes to give $\binom{n}{m}$.

Substituting expressions for the numerator and the denominator in eq. $(1)$ we recover @Did's result: $$ \mathbb{P}\left(\tau_1=r_1,\tau_2=r_2,\ldots,\tau_m=r_m \mid Y_n=m \right) = \frac{p^m (1-p)^{n-m}}{\binom{n}{m} p^m (1-p)^{n-m} } = \frac{1}{\binom{n}{m}} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.