# 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 $$\ell-X$$, 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$$:

• Maybe the downvoter could explain? It looks like there is a typo $X - \ell$ for $\ell - X$, but otherwise it seems like a sensible and maybe interesting question to me. – Mark Wildon Dec 20 '18 at 21:31
• Thanks Mark! Corrected. I would have appreciated an explanation for the downvote as well. – Tom Solberg Dec 20 '18 at 21:32
• Interesting question. I would expect that the depth is approximately normal with mean a multiple of $\log n$ and variance also a multiple of $\log n$. I would expect to be able to compute these constants based on the assumption that the depth is distributed this way, but I have not been able to do so yet. – Anthony Quas Dec 21 '18 at 5:14