2
$\begingroup$

Given a measure space $\mathcal M$, I am wondering what kind of measure space $\mathcal T(\mathcal M)$ one could associate to the set of binary trees with elements from $\mathcal M$ at each node.

The kind of trees I mean can probably best be described in functional programming syntax:

datatype Tree(a) = Leaf | Node(Tree(a), a, Tree(a))

In particular, I wonder what the $\sigma$-algebra of that $\mathcal T(\mathcal M)$ would look like, and how this generalises to other algebraic datatypes.

Improve this question
$\endgroup$
2
  • $\begingroup$ Hi Manuel, Feel free to ask more or clarify your op further, thanks! $\endgroup$
    – Henry.L
    Commented Apr 11, 2017 at 11:51
  • $\begingroup$ I'm afraid I think my background in probability theory is much too weak to even begin to understand what you have written. I had not expected the solution to be this involved. Regardless, I will try to have a look at it and I should probably accept your answer. $\endgroup$
    – Manuel Eberl
    Commented Apr 11, 2017 at 15:28

1 Answer 1

Reset to default
3
$\begingroup$

The tree structures associated with a partition of the sample space $\mathcal{X}$ is usually discussed along with a Beta process(or in computer engineers' world they refer it as "stick-breaking process"). In statistics, this is very useful in nonparametric estimations. When you try to designate a random measure $m\in\mathcal{M}=\mathcal{M(\mathcal{X})}$ for your model. Since $m$ is random, we can also talk about $m(\omega)$ and the stochastic process that generates $m$ as a sample path $m(\omega),\omega\in \mathcal{X}^{\prod}$. Usually the sample path of the Beta process will give a tree-like structure on the product sample space $\mathcal{X}^{\prod}$. The sigma algebra on this product space correponds to the filtration of the Beta process. That is how the $\sigma$-algebra on $T(\mathcal{M})$ looks like.

For technical details, please refer to Chap3-4 of

Ghosh, Jayanta K., R. V. J. K. Ghosh, and R. V. Ramamoorthi. Bayesian nonparametrics. 2003.

Another useful explnatory paper is http://projecteuclid.org/download/pdfview_1/euclid.cbms/1362163749 which is part of the book https://projecteuclid.org/euclid.cbms/1362163742

Müller, Peter, and Abel Rodriguez. Nonparametric bayesian inference. Institute of Mathematical Statistics, 2013.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Just to make sure whether we are talking about the same thing: By partition of the sample space, do you mean that no two nodes may be given the same element? Because that is not what I meant. I was thinking of e.g. a binary search tree after inserting $n$ independent uniformly random values between 0 and 1. $\endgroup$
    – Manuel Eberl
    Commented Apr 9, 2017 at 9:15
  • $\begingroup$ no, it is more like a binary expansion. tree partition is not like disjoint partition. you can search for "polya tree process or beta process @ManuelEberl $\endgroup$
    – Henry.L
    Commented Apr 9, 2017 at 11:25
  • $\begingroup$ Please read: projecteuclid.org/download/pdfview_1/euclid.cbms/1362163749 $\endgroup$
    – Henry.L
    Commented Apr 9, 2017 at 12:37
  • $\begingroup$ Also check out arxiv.org/abs/0806.3286, which is a widely-used Bayesian regression model that has a very simple prior distribution on the regression trees. Essentially smaller depths are given higher probability. $\endgroup$
    – R Hahn
    Commented Apr 11, 2017 at 14:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .