Whilst working on random test data generation I came across the following problem,
I have a List of Lists, L, where each list contains objects an object is either a "thing" or a group of things ( $t$ or $\{t,...\}_g$ ). Initially there are no groups in L.
$$ L = [ l_0, ..., l_n ] $$ $$ l_i = [ t_0, ... ]$$
Then for all $i$ in $[0,n-1]$ I do the following:
- Make a group of all objects in $l_i$, call this group $g_i$
- Add $g_i$ to a random $l_j$ where $j$ is uniformly chosen out of $[i+1,n]$
Add the end $l_n$ contains a list of random object ( containing random groups as well )
My question is then, What is the expected value of the maximum nesting of an object in $l_n$?
( With nesting I mean that, a "thing" has zero nesting, a "thing" inside a group has 1 nesting, etc. )