Estou interessado em propriedades de gráficos direcionados aleatórios com grau externo fixo . Estou imaginando um modelo de gráfico aleatório em que cada vértice escolhe d vizinhos (digamos, com substituição) uar
Pergunta : Sabe-se alguma coisa sobre a distribuição estacionária e os tempos de mistura de passeios aleatórios nesses gráficos aleatórios (para vários valores de )?
Estou particularmente interessado no caso em que , que corresponde a um modelo de autômato aleatório sobre um alfabeto booleano. (Sim, percebo que esses gráficos geralmente não estão conectados, mas o que acontece em um determinado componente?) Estou feliz com resultados parciais e com outras propriedades desses gráficos.
Parece que a maior parte da literatura sobre gráficos aleatórios se concentra no modelo Erdős – Rényi, que possui propriedades muito diferentes do modelo em que estou pensando.
fonte
Respostas:
No caso não direcionado, os gráficos regulares aleatórios são expansores com alta probabilidade (não para d = 2 , mas acho que d ≥ 3 é suficiente), o que implica que o tempo de mistura dos passeios aleatórios é O ( log n ) . Não me lembro o suficiente dessas provas para saber se tudo passa no caso direcionado (certamente algumas propriedades são diferentes: a distribuição uniforme não é mais estacionária), mas pode valer a pena investigar. Boas referências para gráficos expansores são Expander Graphs e suas aplicações de Hoory, Linial e Wigderson e Pseudorandomness de Vadhan.d d= 2 d≥ 3 O ( logn )
fonte
Você conhece o seguinte trabalho (e suas referências)? (Também está disponível no arXiv.)
Bohman, T. e Frieze, A. (2009), Hamilton pedalam em três saídas. Random Structures & Algorithms, 35: 393–417. doi: 10.1002 / rsa.20272
fonte
Você ainda está investigando o problema? Este artigo é realmente um pouco relevante: Alan Frieze, Páll Melsted e Michael Mitzenmacher, " An Analysis of Random-Walk Cuckoo Hashing ", 2009.
fonte