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

22

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)ijiH(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?euii

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=noZn

Alguém já leu algo sobre isso?

Fabrizio Silvestri
fonte
Qual é o problema com o seguinte argumento? Uma caminhada aleatória em um gráfico pode ser descrita por uma cadeia de Markov, onde os estados são os nós. Da mesma forma, pode-se representar a mesma caminhada por uma cadeia de Markov, onde os estados podem ser as arestas. (Cada aresta também contém as informações atuais do nó visitado.) Depois que uma cadeia de Markov é obtida, você pode usar qualquer definição / resultado de cadeias de Markov.
Abuzer Yakaryilmaz
Obrigado pelo comentário. Na verdade, eu esqueci de dizer nós distintos . Vou modificar a pergunta agora.
Fabrizio Silvestri
Talvez eu tenha perdido (desculpe), mas qual é o URL da postagem do SE?
Eu removi a postagem do SE ... É proibido postar a mesma pergunta em dois lugares diferentes.
Fabrizio Silvestri
depende do gráfico em particular, certo? você pode esboçar algo conhecido sobre problemas semelhantes?
vzn

Respostas:

4

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)

vzn
fonte
Boa pegada. De fato, possui uma pequena estrutura mundial. De fato, na aplicação que tenho em mente, a distribuição de graus segue uma lei do poder. Agora, isso pode ajudar ... Ainda assim, nós não encontrou um bom caminho a percorrer :)
Fabrizio Silvestri
THX. qual parâmetro de cache você está tentando otimizar? parece provável que se correlacione diretamente com o expoente da lei do poder de alguma forma ....? suspeitam que simples Monte Carlo abordagens poderia mostrar que a distância pilha está relacionado com a lei de potência expoente etc
vzn
αα=1,<1,>1
Parece que a distância da pilha não foi estudada diretamente na teoria dos grafos, mas é um campo vasto. note que o modelo watts / strogatz é bom para abordagens de Monte Carlo, gerando pequenos gráficos mundiais. Também passeios aleatórios em um gráfico por lovasz é uma boa pesquisa da teoria dos passeios em gráficos aleatórios.
vzn
4

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.

Pål GD
fonte
Existe a possibilidade de ter um rascunho ou uma cópia dos slides?
Fabrizio Silvestri
2
Sinto muito, não tenho mais o que dar, mas talvez esse tópico do MO seja útil: Policiais e ladrões bêbados .
GD Pål GD
Obrigado, Pål ... Estou olhando para o papel vinculado a partir da linha MO.
Fabrizio Silvestri
3

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.

N1NN+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.

Joe Fitzsimons
fonte