CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Generating stationary random graphs on Z with prescribed independent, indentically distributed degrees

Maria Deijfen (Institutionen för matematiska vetenskaper, matematisk statistik) ; R. Meester
Advances in Applied Probability (00018678 ). Vol. 38 (2006), 2, p. 287-298.
[Artikel, refereegranskad vetenskaplig]

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.



Denna post skapades 2009-12-01.
CPL Pubid: 102542

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematisk statistik (2005-2016)

Ämnesområden

Matematik

Chalmers infrastruktur