Common models for random graphs, such as Erd\H{o}s-R\'{e}nyi and Kronecker
graphs, correspond to generating random adjacency matrices where each entry is
non-zero based on a large matrix of probabilities. Generating an instance of a
random graph based on these models is easy, although inefficient, by flipping
biased coins (i.e. sampling binomial random variables) for each possible edge.
This process is inefficient because most large graph models correspond to
sparse graphs where the vast majority of coin flips will result in no edges. We
describe some not-entirely-well-known, but not-entirely-unknown, techniques
that will enable us to sample a graph by finding only the coin flips that will
produce edges. Our analogies for these procedures are ball-dropping, which is
easier to implement, but may need extra work due to duplicate edges, and
grass-hopping, which results in no duplicated work or extra edges.
Grass-hopping does this using geometric random variables. In order to use
this idea on complex probability matrices such as those in Kronecker graphs, we
decompose the problem into three steps, each of which are independently useful
computational primitives: (i) enumerating non-decreasing sequences, (ii)
unranking multiset permutations, and (iii) decoding and encoding z-curve and
Morton codes and permutations. The third step is the result of a new connection
between repeated Kronecker product operations and Morton codes. Throughout, we
draw connections to ideas underlying applied math and computer science
including coupon collector problems.

用球落和草跳两种方法进行几何随机变量操作，以对稀疏图模型进行公司矩阵采样，其中草跳方法利用 Morton 编码将 Kronecker 产品操作与序列化问题建立了联系。