Dada uma caminhada aleatória em um gráfico, o tempo de cobertura é a primeira vez (número esperado de etapas) em que todos os vértices são atingidos (cobertos) pela caminhada. Para gráficos não direcionados conectados, o tempo de cobertura é conhecido por ser superior ao . Existem dígrafos fortemente conectados com tempo de cobertura exponencial em n . Um exemplo disto, é o d�rafo consistindo de um ciclo dirigida ( 1 , 2 , . . . , N , 1 ) , e bordos ( j , 1 ) , a partir de vértices j = . A partir do vértice 1 , o tempo esperado para uma caminhada aleatória atingir o vértice n é Ω ( 2 n ) . Eu tenho duas perguntas :
1) Quais são as classes conhecidas de gráficos direcionados com tempo de cobertura polinomial? Essas classes podem ser caracterizadas por propriedades teóricas dos grafos (ou) pelas propriedades da matriz de adjacência correspondente (digamos ). Por exemplo, se A é simétrico, o tempo de cobertura do gráfico é polinomial.
2) Existem exemplos mais simples (como o exemplo do ciclo mencionado acima) em que o tempo de cobertura é exponencial?
3) Existem exemplos com tempo de cobertura quase polinomial?
Agradeço qualquer indicação de boas pesquisas / livros sobre este tópico.
fonte
Respostas:
O tempo de mistura claramente polinomial implica tempo de cobertura polinomial.(Bem, não em geral. Precisamos da probabilidade estacionária de pelo menos em cada vértice.) Portanto, verifique o papel de Mihail Condutância e convergência das cadeias de Markov - um tratamento combinatório dos expansoresVeja também o artigo Pseudoaleatório em digrafos regulares e o problema RL vs. L de Reingold, Trevisan e Vadhan. Seguindo o trabalho de Mihail. Eles definiram o parâmetro que é equivalente a λ 2 ( G ) , o segundo maior autovalor em valor absoluto, quando o gráfico G é reversível no tempo e permanece bem definido para cadeias gerais de Markov. Este parâmetro é depois usado para limitar o tempo de mistura de G .λπ(G) λ2(G) G G
fonte
Colin Cooper e Alan Frieze têm um conjunto de resultados no contexto de dígrafos aleatórios que podem ser interessantes. Eles estudam as propriedades de uma caminhada aleatória simples no gráfico direcionado aleatório quando n p = d log n , d > 1 . Eles provaram que:Dn,p np=dlogn,d>1
Para , whp o tempo de cobertura de D n , p é assintótico a d log ( d / ( d - 1 ) ) n log n . Se d = d ( n ) → ∞ com n , o tempo de cobertura é assimptótica para n log n .d>1 Dn,p dlog(d/(d−1))nlogn d=d(n)→∞ n nlogn
Se e d > 1 então whp C L n , p ~ d log ( d / ( d - 1 ) ) n log n .p=dlogn/n d>1 CGn,p∼dlog(d/(d−1))nlogn
Seja e deixe x denotar a solução em ( 0 , 1 ) de x = 1 - e - d x . Seja X g o componente gigante de G n , p , p = d / n . Então whp C X g ~ d x ( 2 - X )d>1 x (0,1) x=1−e−dx Xg Gn,p,p=d/n CXg∼dx(2−x)4(dx−logd)n(logn)2
Ifk≥3 and Gr,k is a random geometric graph in Rk of ball size r such that the expected degree of a vertex is asymptotic to dlogn , then whp CGr,k∼dlog(dd−1)nlogn .
See Cooper, C., & Frieze, A. Stationary distribution and cover time of random walks on random digraphs. Journal of Combinatorial Theory, Series B. (2011).
fonte