3
$\begingroup$

How can I pick a random node from a tree, given the following constraints?

  • We are given the root of the tree, and at every node we are given its children nodes. But we do not know what its children nodes are unless we visit the node.
  • We do not know how many nodes are in the tree or any given subtree.
  • We do not know the depth of the tree.

I am trying to write a program to crawl a directory of people's names and choose a random person. The probability of choosing a given person should be 1 over the total number of people, even though I don't know the total number of people.

Thanks!

Edit: the directory has about 10 million names at most, and it's probably 2 million or less.

Edit 2: I'd like to pick 10000 names total, but if that's too computationally intensive I could do 1000 or 100.

$\endgroup$
3
$\begingroup$

A general easy idea to pick $k$ elements from a set of unknown size is to assign a random number from $[0,1]$ to every element, and then pick the top $k$ elements, (with regard to the assigned random numbers). It is worth noting that you want to keep only the current $k$ top entries and their assigned numbers. When a new element is found, assign it a random number (thus get $k+1$ entries) and discard the smallest (along with its assigned random number), hence obtain new $k$ top entries.

For example, to pick 2 random elements from $[A,B,C,D,E]$,

start with first $k$ elements and sort them

$[B \to 0.77, A \to 0.75]$,

add $C \to 0.40$

$[B \to 0.77, A \to 0.75, C \to 0.40]$

discard the smallest

$[B \to 0.77, A \to 0.75]$,

add $D \to 0.04$

$[B \to 0.77, A \to 0.75, D \to 0.04]$

discard the smallest

$[B \to 0.77, A \to 0.75]$,

add $E \to 0.95$

$[E \to 0.95, B \to 0.77, A \to 0.75]$

discard the smallest

$[E \to 0.95, B \to 0.77]$,

nothing more to add, algorithm terminates.

I hope this helps ;-)

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Nevermind guys, I looked up "reservoir sampling." Apparently I can examine each leaf in the tree (using depth first search or something), and for the nth leaf I should select it with probability $1/n$. Stated more precisely, first we choose the first leaf in the tree. Then we replace it with the second leaf with probability $1/2$. Then we replace it with the third leaf with probability $1/3$, until we have crawled the whole tree. You can prove by induction that this selects a random leaf of the tree.

An explanation of why the algorithm works can be found here: http://blog.cloudera.com/blog/2013/04/hadoop-stratified-randosampling-algorithm/

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Also, as implied by the name but maybe not obvious: this is easily extensible to selecting not just a single item but selecting a random group of items (without simply running the algorithm 10,000 times while throwing out duplicates). $\endgroup$ – Steven Stadnicki Jul 11 '13 at 17:58
  • $\begingroup$ @StevenStadnicki: Good to know, thanks. $\endgroup$ – badatmath Jul 11 '13 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.