Probabilidade de que pontos aleatoriamente uniformes em um retângulo tenham distância euclidiana menor que um determinado limite

8

Suponha que temos pontos em um retangular com limite , e esses pontos são distribuídos uniformemente neste plano. (Não conheço bem as estatísticas, portanto não sei a diferença entre escolher uniformemente um nó na área ou escolher uniformemente o eixo- de e eixo de independentemente).n[0,a]×[0,b][0,a]×[0,b]x[0,a]y[0,b]

Dado um limite de distância , talvez eu queira saber a probabilidade de que a distância euclidiana de dois pontos seja menor que ou, mais precisamente, a distância de quantos pares de nós será menor que ?ddd


Talvez a descrição a seguir seja inequívoca.

Deixe-me especificar este problema. Dados nós e limite . Esses pontos são distribuídos uniformemente em um retângulo . Denote uma variável aleatória como o número de pares de pontos dentro da distância . Encontre .ndn[0,a]×[0,b]ξdE[ξ]

zhouzhuojie
fonte
Você deve navegar pelas perguntas em math.SE também, já que eu lembro de várias questões relacionadas lá. Eles provavelmente estão marcados probability.
cardeal
1
Aqui estão algumas das perguntas que eu lembrei de ver no math.SE, mas nenhuma delas é exatamente o que você pergunta: ( 1 ) math.stackexchange.com/questions/64028 ( 2 ) math.stackexchange.com/questions/66777 ( 3 ) math.stackexchange.com/questions/101692 ( 4 ) math.stackexchange.com/questions/50775
cardinal

Respostas:

15

Podemos resolver esse problema analiticamente usando alguma intuição e argumentos geométricos . Infelizmente, a resposta é bastante longa e um pouco confusa.

Configuração básica

Primeiro, vamos definir uma notação. Suponha que desenhamos pontos uniformemente aleatoriamente a partir do retângulo . Assumimos sem perda de generalidade que . Seja as coordenadas do primeiro ponto e sejam as coordenadas do segundo ponto. Então, , ,[0,a]×[0,b]0<b<a(X1,Y1)(X2,Y2)X1X2Y1e Y2 são mutuamente independentes com Xi distribuído uniformemente em [0,a] e Yi distribuído uniformemente em [0,b].

Considere a distância euclidiana entre os dois pontos. Isto é

D=(X1X2)2+(Y1Y2)2=:Z12+Z22,
Onde Z1=|X1X2| e Z2=|Y1Y2|.

Distribuições triangulares

Desde a X1 e X2 são uniformes independentes, então X1X2 tem uma distribuição triangular, de onde Z1=|X1X2| tem uma distribuição com função de densidade

fa(z1)=2a2(az1),0<z1<a.
A função de distribuição correspondente é Fa(z1)=1(1z1/a)2 para 0z1a. Similarmente,Z2=|Y1Y2| tem densidade fb(z2) e função de distribuição Fb(z2).

Note que desde Z1 é uma função apenas dos dois Xi e Z2 é uma função apenas do Yi, então Z1 e Z2são independentes. Portanto, a distância entre os pontos é a norma euclidiana de duas variáveis ​​aleatórias independentes (com distribuições diferentes).

O painel esquerdo da figura mostra a distribuição de X1X2 e o painel direito mostra Z1=|X1X2| Onde a=5 neste exemplo.

Densidades triangulares

Alguma probabilidade geométrica

assim Z1 e Z2 são independentes e são suportados em [0,a] e [0,b]respectivamente. Para fixod, a função de distribuição da distância euclidiana é

P(Dd)={z12+z22d2}fa(z1)fb(z2)dz1dz2.

Podemos pensar nisso geometricamente como tendo uma distribuição no retângulo e considerando um quarto de círculo de raio . Gostaríamos de saber a probabilidade que existe dentro da interseção dessas duas regiões. Há três possibilidades diferentes a serem consideradas:[0,a]×[0,b]d

Região 1 (laranja): . Aqui o quarto de círculo fica completamente dentro do retângulo.0d<b

Região 2 (vermelha): . Aqui o quarto de círculo cruza o retângulo ao longo das bordas superior e inferior.bda

Região 3 (azul): . O quarto de círculo cruza o retângulo ao longo das bordas superior e direita.a<da2+b2

Aqui está uma figura, onde desenhamos um raio de exemplo de cada um dos três tipos. O retângulo é definido por , . O mapa de calor em escala de cinza no retângulo mostra a densidade que as áreas escuras têm maior densidade e as áreas mais claras, com menor densidade. Clicar na figura abrirá uma versão maior dela.a=5b=4fa(z1)fb(z2)dz1dz2

Distribuição induzida: interseções

Algum cálculo feio

Para calcular as probabilidades, precisamos fazer algum cálculo. Vamos considerar cada uma das regiões, por sua vez, e veremos que uma integral comum surgirá. Essa integral tem uma forma fechada, embora não seja muito bonita.

Região 1 : .0d<b

P(Dd)=0d0d2y2fb(y)fa(x)dxdy=0dfb(y)0d2y2fa(x)dxdy.

Agora, a integral interna produz . Portanto, resta calcular uma integral da forma onde neste caso de interesse . A antiderivada do integrando é 1a2d2y2(2ad2y2)

G(c)G(0)=0c(by)d2y2(2ad2y2)dy,
c=d
G(y)=(by)d2y2(2ad2y2)dy=a3d2y2(y(3b2y)+2d2)+abd2tan1(yd2y2)bd2y+by33+(dy)22y44.

A partir disso, obtemos que .P(Dd)=2a2b2(G(d)G(0))

Região 2 : .bda

P(Dd)=2a2b2(G(b)G(0)),
pelo mesmo raciocínio que para a Região 1, mas agora precisamos integrar ao longo do eixo até vez de apenas .ybd

Região 3 : . a<da2+b2

P(Dd)=0d2a2fb(y)dy+d2a2bfb(y)0d2y2fa(x)dxdy=Fb(d2a2)+2a2b2(G(b)G(d2a2))

Abaixo está uma simulação de 20000 pontos onde plotamos a distribuição empírica como pontos cinzas e a distribuição teórica como uma linha, colorida de acordo com a região específica que se aplica.

PDF empírico e teórico

A partir da mesma simulação, abaixo, plotamos os 100 primeiros pares de pontos e desenhamos linhas entre eles. Cada um é colorido de acordo com a distância entre o par de pontos e em qual região essa distância se encaixa.

Amostra aleatória de pontos

O número esperado de pares de pontos dentro da distância é simplesmente pela linearidade da expectativa.d

E[ξ]=(n2)P(Dd),
cardeal
fonte
3
+1. Bom trabalho! Seria maravilhoso ver a resposta expressa em termos de propriedades geométricas intrínsecas do retângulo: deveria depender de coisas como sua área, perímetro e configuração dos quatro ângulos. (A literatura - à qual eu já vi referências, mas ainda não tive acesso - parece focar em domínios com limites suaves.)
whuber
Obrigado. Essa é uma excelente sugestão. Vou tentar fazer essas simplificações e reformulações.
cardeal
@ cardinal Muito bom trabalho! Fiquei surpreso que você tenha respondido completamente ao problema, mesmo com o cdf detalhado. Obrigado.
Zhouzhuojie 12/02/12
0

Se os pontos são realmente uniformemente distribuídos, ou seja, em um padrão conhecido fixo, para qualquer distância d, você pode simplesmente fazer um loop sobre todos os pares e contar os que estão à distância. Sua probabilidade é (esse número / n).

Se você tem a liberdade adicional de escolher como os n pontos são distribuídos / escolhidos, essa é a versão retangular do paradoxo de Bertrand . Essa página mostra várias maneiras de responder a essa pergunta com base em como você distribui seus pontos.

cape1232
fonte
A pergunta pergunta sobre a distribuição de pontos uniformemente distribuídos: são variáveis ​​aleatórias, não qualquer "padrão conhecido fixo", e não se pode simplesmente fazer um loop sobre pares deles!
whuber
Eu acho que você pode ter entendido mal a pergunta do OP. Além disso, a distribuição desejada é definida sem ambiguidade na pergunta. Meu comentário ao OP sugere que já existe uma solução na rede SE para essa pergunta, portanto, é provável que esta seja fechada. :)
cardeal
Você tem certeza de que existe uma solução em math.SE, cardeal? Este é um problema difícil devido aos efeitos das bordas. Talvez haja uma solução no toro plano.
whuber
@whuber: Uma solução? Não. Mas tenho quase certeza de que essa pergunta aparece. :) Vou ver se consigo encontrá-lo. De qualquer forma, não tenho certeza se esse problema é tão difícil, mesmo neste caso. Eu acredito que você pode usar a invariância da tradução para simplificá-la um pouco. Mas ainda não resolvi os detalhes.
cardeal
1
@ cardinal Obrigado. Na verdade, eu passei por todas as perguntas sobre Math.SE, mas ainda não consegui encontrar algumas próximas a esse problema.
Zhouzhuojie