Variance of Size in Regular Graph Tries
Philippe Jacquet, Abram Magner · 2014
Graph tries are a generalization of classical digital trees: instead of being built from strings, a G-trie is built from label functions on the graph G. In this work, we determine leading order asymptotics for the variance of the size of a G-trie built on a memoryless source on a uniform alphabet distribution, where G is a member of a large class of infinite, M -regular directed, acyclic graphs with M > 1 fixed. In particular, this covers the cases of trees and grids. We find that, in such tries, the variance is of order Θ(nρ′), for some ρ′ depending on G which is minimized when G is a tree. We also give an explicit expression for ρ′ in the case where G is a grid, with M = 2.