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$:

Sequential binomial sampling with n = 100, k = 7

  • 1
    $\begingroup$ 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. $\endgroup$ – Mark Wildon Dec 20 '18 at 21:31
  • $\begingroup$ Thanks Mark! Corrected. I would have appreciated an explanation for the downvote as well. $\endgroup$ – Tom Solberg Dec 20 '18 at 21:32
  • $\begingroup$ 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. $\endgroup$ – Anthony Quas Dec 21 '18 at 5:14

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.