1
$\begingroup$

If you have a tree, there are two common ways to select a random leaf node from the tree:

  • You can "flatten" out the tree, so that each leaf node gets selected with the same probability.

  • You can traverse/walk the tree from the root, at each level selecting from that node's children with equal probability, until you hit a leaf node. This method will favor some leaf nodes over others (e.g. if a tree has only two branches, but one branch has only 1 leaf but the other branch has 10 leaves, then the lone leaf is 10 times more likely to be selected than any individual/single leaf of the other branch).

Are there common terms to refer to each of these two methods of selection/traversal? I'm struggling to discuss and/or write about these methods without having to awkwardly explain the whole method each time rather than just naming it.

I've seen people refer to the former method as "selecting a leaf uniformly at random," but even that is a bit of a mouthful of a phrase.

Furthermore, extrapolating from that description to its opposite doesn't give a way to unambiguously refer to the latter method: "selecting a leaf non-uniformly at random" is ambiguous as there are many other possible ways to select a leaf non-uniformly at random other than the way I've described above.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

"Selecting a leaf uniformly at random" without ambiguity signals to the reader that each leaf is selected with equal probability. On the other hand, the second approach is what you would call "sampling a leaf by taking a random walk from the root." Of course, to make it unambiguous, you would have to define what a random walk from the root means. But I think as the notion is usually used, it would naturally mean: you sample a leaf by starting from root, each time you are at an internal node, you flip a fresh unbiased coin, if it comes heads you go to the left child, and if tails you go to right; you halt and report the leaf when you reach one.

So in my opinion "selecting a leaf uniformly" and "selecting a leaf by taking a simple random walk from the root" fit the two ways you mentioned, respectively.

See here for an example for the definition of a random walk on a graph.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.