Limit laws for terminal nodes in random circuits with restricted fan-out: a family of graphs generalizing binary search trees

摘要

We introduce a family of graphs C(n,i,s,a) that generalizes the binary search tree. The graphs represent logic circuits with fan-in i, restricted fan-out s, and arising by n progressive additions of random gates to a starting circuit of a isolated nodes. We show via martingales that a suitably normalized version of the number of terminal nodes in binary circuits converges in distribution to a normal random variate.