Densidade de robôs fazendo caminhada aleatória em um gráfico geométrico aleatório infinito

Considere um gráfico geométrico aleatório infinito no qual as localizações dos nós seguem um processo de ponto de Poisson com densidade e as arestas são colocadas entre os nós que estão mais próximos que . Portanto, o comprimento das arestas segue o seguinte PDF: $\rho$ $d$

f (l) = {\begin{cases} \frac{2 l}{d^{2}} l \leq d \\ 0 l > d \end{cases}

$f(l)= \begin{cases} \frac{2 l}{d^2} \;\quad l \le d \\ 0 \qquad\; l > d \end{cases}$

No gráfico acima, considere os nós dentro do círculo do raio centralizados na origem. Suponha que, no tempo , coloque um pequeno robô dentro de cada um dos nós mencionados. Ou seja, a densidade dos robôs no avião é dada por: $r$ $t=0$

g (l) = {\begin{cases} ρ l \leq r \\ 0 l > d \end{cases}

$g(l)= \begin{cases} \rho \quad l \le r \\ 0 \quad\; l > d \end{cases}$ que é a distância da origem. A figura a seguir mostra um exemplo do posicionamento inicial dos robôs.

l

$l$

exemplo

A cada passo, os robôs vão para um dos vizinhos aleatoriamente.

Agora, minha pergunta é: qual é a função de densidade dos robôs em ? É possível calcular a função de densidade quando ? $t>0$ $t \rightarrow \infty$

Desculpe pessoal, não sou de forma alguma um matemático. Informe-me se algo não estiver claro.

probability stochastic-processes pdf asymptotics graph-theory Hélio
fonte

Procure livros de Wolfgang Woess como editor ou autor. Uma coleção recente: Passeios aleatórios, limites e espectros. Birkhauser, 2011. Desde 2000 (Cambridge Univ.Press): Passeios aleatórios em gráficos e grupos infinitos.

Deer Hunter

Obrigado Hunter. Dei uma olhada rápida no livro de 2011, mas não encontrei nada relacionado. Eu não tenho acesso ao 2000 no momento, mas procurarei assim que o encontrar. Entre em contato se você se lembrar de algo mais específico dos livros.

Helium

Aqui está um começo.

Seja o raio da bola que você está considerando. $r = d/2$

Primeiro, leia sobre passeios aleatórios: http://en.wikipedia.org/wiki/Random_walk . Suponha que você tenha apenas um robô e assuma que seu passeio aleatório está em uma estrutura bidimensional. Para pequeno , é fácil calcular com a multiplicação de matrizes. Você sabe que existem apenas pontos possíveis na rede na qual você pode pisar ou pousar após etapas. Seja a matriz de adjacência desses vértices. Deixe ser o vector de todas as s excepto para um na th local. Suponha que a primeira linha (e coluna) de $t$ $n = 1 + 4t + 2t(t-1)$ $t$ $A_t$ $n \times n$ $n$ $e_{i,t} \in \{0,1\}^n$ $0$ $1$ $i$ $A_t$ corresponde à origem. Então, a probabilidade de você estar no vértice após etapas é (onde o primo significa transpor e é elevada para o th potência). Tenho certeza que você deve ser capaz de resolver isso explicitamente. Você pode usar o fato de que tudo a mesma distância da origem na norma deve ter a mesma densidade. $i$ $t$ $e_{1,t}' A_t^t e_{i,t}$ $A^t = A \times A \cdots \times A$ $A$ $t$ $\cal L_1$

Após esse aquecimento, passemos à sua pergunta original. Após etapas, você só precisa considerar o gráfico finito que está dentro do raio torno da origem (em qualquer outro lugar a probabilidade de ser alcançável após apenas $t$ $r(t+1)$ $0$ $t$ passos). Tente criar a matriz de adjacência desse gráfico e trabalhe com ela da mesma maneira que o caso da treliça - não sei como fazer isso, mas acho que há alguma teoria de Markov por aí para ajudá-lo. Uma coisa que você pode tirar vantagem de nós é o fato de saber que essa distribuição deve ser simétrica em torno da origem, em particular a densidade é apenas uma função da distância da origem. Isso deve facilitar as coisas, então tudo o que você precisa considerar é a probabilidade de estar a uma distância da origem após etapas. Depois de resolver este problema, ligue para o densidade no local depois de passos . Observe que será uma função de $q$ $t$ $(x,y)$ $t$ $f_t(x,y)$ $f_t$ $r$ . Seja uma variável aleatória amostrada nesta distribuição. $X$

Agora você também precisa considerar começar com vários robôs. Supondo que vários robôs possam estar no mesmo vértice, isso não torna muito mais difícil do que o caso de um robô. Os robots podem iniciar de modo uniforme sobre o círculo, chamada a variável aleatória que é amostrado de modo uniforme nesta círculo . Você começará com um número de robôs Poisson, seja uma variável aleatória amostrada nessa distribuição de Poisson. Assim, a densidade que você começa a partir de múltiplos robôs é apenas . $U$ $M$ $MU + X$

Eu acho que este é um começo razoável para a solução, exceto que eu não definir completamente a distribuição de . Boa sorte e boa pergunta. $X$

user1448319
fonte

Você poderia esclarecer como obteve o número total de possíveis locais ocupados após etapas em uma rede regular? Por exemplo, inserir , e não fornece respostas razoáveis. Sua resposta não deve ser ?

t

$t$

t = 0

$t = 0$

t = 1

$t = 1$

t = 2

$t = 2$

t^{2}

$t^2$

cardeal

Oh, boa captura. não deveria ser , deveria ser . é a origem, é os eixos, são as 4 matrizes triangulares. por exemplo, para , e e as outras três direções, e e os outros quatro quadrantes.

n = 1 + 4 t + 2 (t - 1)^{2}

$n = 1 + 4t + 2(t-1)^2$

n = 1 + 4 t + 2 t (t - 1) = 1 + 2 t + 2 t^{2}

$n= 1 + 4t + 2t(t-1) = 1 + 2t + 2t^2$

1

$1$

+ 4 t

$+4t$

+ 2 t (t - 1)

$+2t(t-1)$

t = 2

$t=2$

(0, 0)

$(0,0)$

(1, 0), (2, 0)

$(1,0), (2, 0)$

(1, 1)

$(1,1)$

user1448319

Como você estará em após duas etapas? (Talvez eu não esteja entendendo a caminhada que você está descrevendo. Se eu pensar na caminhada aleatória "usual" em , ou seja, uniforme nas quatro direções cardinais, então, a menos que eu esteja enganado, a resposta no meu primeiro comentário deve estar correto).

(1, 0)

$(1,0)$

Z^{2}

$\mathbb Z^2$

cardeal

Você não pode terminar após duas etapas começando em . Mas você PODE atravessar depois de dar dois passos. Você DEVE considerar todos os pontos alcançáveis em 2 etapas para construir como descrito acima.

(1, 0)

$(1,0)$

(0, 0)

$(0,0)$

(1, 0)

$(1,0)$

A_{t}

$A_t$

user1448319

Isso é verdade, mas entendi a frase como o que dizia: Você sabe que existem apenas lugares possíveis que você pode pousar na treliça após etapas. $n=1+4t+2(t−1)^2$ $t$ :-) Talvez uma edição ajude a esclarecer. Felicidades.

cardeal

Densidade de robôs fazendo caminhada aleatória em um gráfico geométrico aleatório infinito

Respostas: