Número de nós distintos em uma caminhada aleatória

O tempo de comutação em um gráfico conectado é definido como o número esperado de etapas em uma caminhada aleatória iniciando em , antes que o nó seja visitado e o nó seja alcançado novamente. É basicamente a soma dos dois tempos de acerto e .i j i H ( i , j ) H ( j , i $G=(V,E)$$i$$j$$i$$H(i,j)$$H(j,i)$

Existe algo semelhante ao tempo de deslocamento (não exatamente o mesmo), mas definido em termos de nós? Em outras palavras, qual é o número esperado de distintas nós um passeio aleatório a partir de e retornando pelo vai visitar?$i$$i$

Atualização (30 de setembro de 2012): Há vários trabalhos relacionados ao número de sites distintos visitados por um caminhante aleatório em uma treliça (por exemplo, ). Por exemplo, consulte: http://jmp.aip.org/resource/1/jmapaq/v4/i9/p1191_s1?isAuthorized=no$\mathbb{Z}^n$

Alguém já leu algo sobre isso?

de perguntas e respostas com você nos comentários que parece estar interessado em estudar algo definido como a distância da pilha neste conjunto de slides, Sobre a modelagem matemática de caches

defina a distância da pilha de uma referência como o número de endereços de bloco exclusivos entre a referência atual e a referência anterior ao mesmo número de bloco.

possui algumas análises empíricas via benchmarks. diz que, em geral, "não há medida conhecida da localidade" dos pedidos de cache e, em seguida, propõe a distância da pilha como tal medida. ele não o relaciona à teoria aleatória dos grafos, embora você esboce essa conexão em seus comentários. (parece que a distância da pilha pode estar relacionada à mistura de cadeias de markov ?)

parece que você está interessado em modelar o desempenho do cache ou algoritmos de otimização considerando solicitações de cache como nós de um gráfico e as arestas como transições entre solicitações adjacentes. não vi trabalhos que estudem a estrutura deste gráfico. parece não ser um gráfico puramente aleatório em aplicativos reais devido ao sucesso dos caches na prática e ao que é chamado de local espacial e temporal nos slides acima. ou seja, algum tipo de "agrupamento", como Joe esboça em sua resposta.

(talvez tenha uma pequena estrutura mundial ?, o que é bastante onipresente nos dados do mundo real)

Um comentário: recentemente participei de uma palestra de Bruce Reed com o título Catching a Drunk Miscreant , que foi um trabalho conjunto com Natasha Komorov e Peter Winkler. Se você conseguir obter os resultados deste trabalho, talvez isso possa ajudá-lo em alguma direção.

Em geral, eles provam um limite superior no número de etapas que um policial precisa em um gráfico geral para conseguir capturar um ladrão, quando sabemos que o ladrão se move aleatoriamente pelas bordas.

Esta não é realmente uma resposta adequada para sua pergunta, mas é um pouco longa para um comentário.

A quantidade que você procura varia de gráfico para gráfico e depende do local inicial do caminhante. O número esperado de nós intermediários distintos dependerá fortemente do agrupamento no gráfico, e eu esperaria que o número esperado de nós intermediários distintos fosse correlacionado com o coeficiente de agrupamento .

Um cluster é basicamente um subconjunto de vértices que compartilham um grande número de arestas, para que cada vértice seja conectado a uma grande fração dos outros vértices dentro do cluster. Quando um caminhante entra em um cluster, é provável que permaneça nessa região por um grande número de saltos, possivelmente revisitando cada nó muitas vezes. De fato, o uso de passeios aleatórios dessa maneira é uma das técnicas computacionais usadas para identificar clusters em grandes gráficos. Assim, para um caminhante iniciando em um cluster, o número esperado de vértices intermediários distintos provavelmente será escalado com o tamanho do cluster e a probabilidade média de deixar o cluster.

$N$$\frac{1}{N}$$N+1$

O grau médio de vértices no gráfico também desempenhará um papel importante, embora isso esteja vinculado ao cluster. A razão para isso é que, quando o caminhante salta para um vértice com grau 1, deve retornar ao vértice anterior no próximo salto. Mesmo quando o grau é 2, existe apenas um caminho que pode ser seguido pelo gráfico, embora possa ser percorrido em qualquer direção em cada salto. Por outro lado, para gráficos com grau maior que 2, o número de caminhos pode explodir, tornando extremamente improvável o retorno ao site inicial, mesmo que o caminho mais curto entre eles seja pequeno.

Portanto, você esperaria que o número de vértices intermediários distintos fosse alto para gráficos que possuem um grau médio substancialmente acima de 2 e também não possuem agrupamentos significativos, como árvores.

É claro que esses comentários não são mais válidos no caso de passeios aleatórios quânticos, mas acho que você se importa apenas com o caso clássico.