TY - JOUR
T1 - Generating stationary random graphs on \Bbb Z with prescribed independent, identically distributed degrees
AU - Deijfen, M.K.
AU - Meester, R.W.J.
N1 - MR2264945
PY - 2006
Y1 - 2006
N2 - Let F be a probability distribution with support on the nonnegative integers. We describe two algorithms for generating a stationary random graph, with vertex set ℤ, in which the degrees of the vertices are independent, identically distributed random variables with distribution F. Focus is on an algorithm generating a graph in which, initially, a random number of 'stubs' with distribution F is attached to each vertex. Each stub is then randomly assigned a direction (left or right) and the edge configuration obtained by pairing stubs pointing to each other, first exhausting all possible connections between nearest neighbors, then linking second-nearest neighbors, and so on. Under the assumption that F has finite mean, it is shown that this algorithm leads to a well-defined configuration, but that the expected length of the shortest edge attached to a given vertex is infinite. It is also shown that any stationary algorithm for pairing stubs with random, independent directions causes the total length of the edges attached to a given vertex to have infinite mean. Connections to the problem of constructing finitary isomorphisms between Bernoulli shifts are discussed. © Applied Probability Trust 2006.
AB - Let F be a probability distribution with support on the nonnegative integers. We describe two algorithms for generating a stationary random graph, with vertex set ℤ, in which the degrees of the vertices are independent, identically distributed random variables with distribution F. Focus is on an algorithm generating a graph in which, initially, a random number of 'stubs' with distribution F is attached to each vertex. Each stub is then randomly assigned a direction (left or right) and the edge configuration obtained by pairing stubs pointing to each other, first exhausting all possible connections between nearest neighbors, then linking second-nearest neighbors, and so on. Under the assumption that F has finite mean, it is shown that this algorithm leads to a well-defined configuration, but that the expected length of the shortest edge attached to a given vertex is infinite. It is also shown that any stationary algorithm for pairing stubs with random, independent directions causes the total length of the edges attached to a given vertex to have infinite mean. Connections to the problem of constructing finitary isomorphisms between Bernoulli shifts are discussed. © Applied Probability Trust 2006.
U2 - 10.1239/aap/1151337072
DO - 10.1239/aap/1151337072
M3 - Article
SN - 0001-8678
VL - 38
SP - 287
EP - 298
JO - Advances in Applied Probability
JF - Advances in Applied Probability
IS - 2
ER -