공간 속에 있는 점들 사이이 거리에 대한 성질

공간 속에 있는 점들 사이이 거리에 대한 성질

엄청 애매한 말이지만, 이런 것이 수학의 진수가 아닐까 싶다. 

내가 찾고자 하는 것은 다음과 같다. 

'$S \subseteq R^d$'의 공간에서 반지름 '$r$'인 ball들이 '$N$'개가 뿌려져있다고 가정하자. 

이 때, 전체 영역에서 ball로 채워지지 않은 영역은 얼마나 될 것인가? 

모 대충 이런 상황이다. 

1. Distance Distribution in Finite Uniformly Random Networks: Theory and Applications 

 Spatial point process는 임의의 random countable subset of space '$S$'라고 볼 수 있다. 일반적으로 '$S$'는 '$d$' 차원의 box인 경우가 많다. 예를 들어서 1km^2 공간을 생각해보자. 이 때 '$S = [0, 1]^2 \subset R^2$' 일 것이다. 이 공간 속에 있는 잡초의 분포 등이 spatial point process가 될 것이다. 

Definition (Locally Finite) 

 '$n(x)$'를 subset '$x \subseteq S$'의 cardinality라 하자. 만약 '$s$'가 finite하지 않다면, '$n(x) = \infty $'이다. '$x_B = x \cap B$' for '$B \subseteq S$'라 하자. 즉 '$x_B$'는 '$x$'라는 set과 '$B$'라는 set의 교집합이다. 이 때 '$x$'가 locally finite이라는 정의는 '$n(x_B) < \infty $' whenever '$B$' is bounded. 

Definition (Point process) 

 '$S$'에서 정의된 point process '$X$'의 정의는 probability space '$(\Omega, F, P)$'에서의 measurable mapping이다. (값의 범위는 skip!) 직관적으로 설명하자면 이러한 point process '$X$'는 어떤 set '$F$'에 대한 확률을 정의할 수 있고, 이는 다음과 같다. '$P_X(F) = P(\{ w \in \Omega : X(w) \in F \})$'

 아래 두 개념(BPP, PPP)은 spatial point process의 기본 중에 기본이다. 

Definition (Binomial Point Process) 

 '$f$'를 어떤 set '$B \subseteq S$'에서 정의된 density function이라 하고, '$n \in N$', 즉 어떤 자연수라 하자. 이 때 어떤 point process '$X$'가 '$f$'의 density를 따르며 모두 i.i.d. 관계를 갖고 있으면 이러한 '$X$'를 '$B$'에서 '$f$'의 분포로 '$n$'개의 점으로 이뤄진 binomial point process라 한다. 

$$X \sim binomial(B, n, f)$$

Definition (Poisson Point Process) 

  이는 기본적으로 점들 사이에 그 어떤 interaction도 없음을 의미한다. 다시 말해서 점들 사이에 어떤 연관 관계가 있는 경우에 PPP는 의미없는 결과를 도출하게 된다. 물론 간단해서 좋다. 

 어떤 point process '$X$' on '$S \subseteq R^d$'는 다음의 조건을 만족할 때 Poisson point process라 한다. 

1. 어떤 '$B \subseteq S$'에 대해 '$\mu(B) < \infty$', '$N(B) ~ Pois(\mu(B))$' (평균이 '$\mu(B)$'인 Poisson distribution)를 만족한다. 쉽게 생각해서 어떤 영역을 잡았을 때 해당 영역에 뿌려져 있는 원소의 수는 해당 넓이를 평균으로 하는 Poisson distribution을 따르는 것을 의미한다. 

 - 사실 구현은 쉽다. 영역이 주어지면, 영역의 넓이 (혹은 넓이의 함수)를 평균으로 하는 Poisson 분포에서 값을 뽑은 후에 해당 영역에 뽑은 값 만큼의 원소를 뿌리면 된다. (http://stats.stackexchange.com/questions/16282/how-to-generate-nd-point-process)

2. 어떤 '$n \in N$'과 '$B \subseteq S$'이고, '$0 < \mu(B) < \infty$'에 대해서 

$$[X_B | N(B) = n] \sim binomial(B, n, \frac{\sigma(\zeta)}{\mu(B)})  $$

를 만족한다! 

만약 '$S$'가 bounded라면 PPP를 그리는 가장 간단한 방법은 1) '$N(B) ~ Pois(\mu(B))$' 2) '$N(B)$' 개의 independent한 점을 '$B$'에서 뽑는 것이다. 논문엔 '$S$' 라고 나오는데 내 생각엔 '$B$' 인 것 같다. 

먼저 위와 같은 상황이 있다고 하자. 이 공간 속에 N개의 점이 있다고 할 때, 각 점까지의 거리를 크기 순으로 나열했다고 하자. 그리고 이 거리에 대한 분포에 대해서 생각해보자. 

 결론만 쓰자면, 공간 속 (임의의 '$d$' 차원의 공 속에 '$N$'개의 점이 임의로 뿌려져 있다면 원점에서 '$m$' 번째로 가까운 점 까지의 거리는 다음의 분포를 갖는다. 

 이를 유도하는 과정을 직관적으로 설명하자면 먼저 해당 random variable의 1-CDF를 구한다. 임의의 점에서 n번째로 가까운 점까지의 거리에 대한 1-CDF는 '$r_n$' (해당 확률 변수)가 주어졌을 때, '$r_n$' ball 안에 점이 n개보다 적게 들어있을 확률을 의미한다. 전체 영역이 주어졌고, '$r_n$' ball에 해당하는 넓이가 가 주어졌으므로 임의의 점이 해당 ball 속에 있을 확률 '$p$'가 있다. 이 때 1부터 n까지 '$p$'의 확률을 갖는 multinomial 확률 변수의 확률을 다 더하면 된다. 이 값을 미분하면 pdf가 나온다. 

위의 식을 매트랩을 이용해서 여러 다른 조건에서 그려보면 다음과 같다. 

     

 이 때 원점에서 가장 가까운 점 까지의 거리와 두 번째로 가까운 점 까지의 거리는 다음과 같이 나타난다. 

 사용된 매트랩 코드

%% 서로 다른 N에 따른 pdf를 그려보자. 

% 기본 함수들

beta_density = @(x, a, b)(1/beta(a, b)*x^(a-1)*(1-x)^(b-1));

f_Rn = @(r, N, R, d, n)(d/R*beta(n-1/d+1, N-n+1)/beta(N-n+1, n)*beta_density((r/R)^d, n-1/d+1, N-n+1));

Nlist = [10 20 30];

flist = cell(length(Nlist), 1);

for Ni = 1:length(Nlist)

    % 파라미터

    N = Nlist(Ni); 

    R = 10;

    d = 1;

    n = 1;

    r_list = linspace(0, 10, 1E2);

    % pdf

    f = @(r)(f_Rn(r, N, R, d, n));

    fs = zeros(length(r_list), 1);

    for fi = 1:length(r_list)

        fs(fi) = f(r_list(fi));

    end 

    flist{Ni} = fs;

end

figure(1); hold on;

colors = 'rgbckymrgbckym';

hlist = zeros(length(Nlist), 1);

legend_str = cell(length(Nlist), 1);

for hi = 1:length(Nlist)

    hlist(hi) = plot(r_list, flist{hi}, 'LineWidth', 3, 'Color', colors(hi));

    legend_str{hi} = sprintf('N: %d', Nlist(hi));

end

hleg = legend(hlist, legend_str); set(hleg, 'FontSize', 15);

title(sprintf('Radius (R): %d / Dimension (d): %d / n: %d', R, d, n), 'FontSize', 15);

xlabel('r', 'FontSize', 15); ylabel('f_R_n(r)', 'FontSize', 15);

2. On the Lengths of the Pieces of a Stick Broken at Random 

3. The Probability Distribution of the Distance between Two Random Points in a Box

4. Random Points Associated with Rectangles 

.