Skip to main content
1 of 2
Tom Solberg
  • 4k
  • 12
  • 25

Distributions of "sequential" binomials

I have come across the following stochastic process which seems very elementary, although I do not know any appropriate terminology for it; I greatly appreciate any suggestions!

Suppose I am given integers $n$ and $k$, with $k\ll n$. I create a binary tree as follows:

  1. Create a root node, with label $n$.
  2. While there exists a leaf $u$ whose label $\ell$ is greater than $k$, add two descendants to $u$ whose labels are $X$ and $X-\ell$, where $X$ is a binomial random variable having parameters $1/2$ and $\ell$ respectively.

I am interested in the basic distributional properties of this tree where $n\to\infty$ and $k$ is fixed, such as the depth and the labels of the leaves at termination. Does this have a name? I created one output below for $n=100$ and $k=7$:

Sequential binomial sampling with n = 100, k = 7

Tom Solberg
  • 4k
  • 12
  • 25