next up previous contents
Next: Methods to estimate the Up: NEAREST NEIGHBOUR METHODS Previous: Introduction   Contents

The expected value of nearest neighbour distances

For $N$ uncorrelated points in phase space, we expect the probability to find exactly $k$ points in a given ball, centered at a reference point $x$,with volume $V$ and radius $r$ to be binomial:
\begin{displaymath}
P\{ M_x(r) = k \} = {N \choose k} {[p(x)V]}^k {[1 - p(x)V]}^{N-k}
\end{displaymath} (3.1)

where $M_x(r)$ is the random variable denoting the number of points in the ball; it is assumed that the density $p(.)$ is constant within each ball. The (possibly non-integer) $D$-dimensional volume $V$ equals $r^D V_D$ where the (fractal) hypersphere $V_D$ has radius 1. The probability density function of the distance $r_{k,x}$ to the $k$-th nearest neighbour can be obtained by [Pettis et al., 1979]:
$\displaystyle f_{k,x}(r)$ $\textstyle =$ $\displaystyle \lim_{\Delta r \rightarrow 0} \frac{1}{\Delta r}
P\{ r \leq r_{k,x} \leq r + \Delta r\} =$  
    $\displaystyle \lim_{\Delta r \rightarrow 0} \frac{1}{\Delta r}
P\{ M_x(r + \Delta r) = k \mid M_x(r) = k-1 \} \cdot
P\{ M_x(r) = k-1\} =$  
    $\displaystyle N p(x) \Delta V \cdot P\{ M_x(r) = k-1 \}$  
    $\displaystyle N p(x) V_D D r^{D-1} \cdot P\{ M_x(r) = k-1 \}$ (3.2)

For large $N$ and small $r$ (so that $p(x)V$ will also be small), the binomial distribution can be approximated by the Poisson distribution:
\begin{displaymath}
P\{ M_x(r) = k \} = \frac{{[ Np(x)V ]}^k}{\Gamma(k+1)} \exp(-Np(x)V)
\end{displaymath} (3.3)

Hence we obtain
\begin{displaymath}
f_{k,x}(r) = \frac{cDr^{D-1}{(cr^{D})}^{k-1}}{\Gamma(k)}\exp(-cr^{D})
\end{displaymath} (3.4)

where $c = Np(x)V_D$. For the expectation of $r_{k}^{\gamma}$ we write
$\displaystyle \mbox{E}\left\{ r_{k}^{\gamma} \right\}$ $\textstyle =$ $\displaystyle \int_{r=0}^{\infty}
r^{\gamma} f_{k,x}(r)dr =$  
    $\displaystyle \int_{r=0}^{\infty} r^{\gamma} \frac{cDr^{D-1}
{(cr^{D})}^{k-1}}{\Gamma(k)}
\exp(-cr^{D})dr = \quad \mbox{(using the substitution $y=cr^d$)}$  
    $\displaystyle \frac{c^{-\gamma/D}}{\Gamma(k)}
\int_{r=0}^{\infty} y^{k+\gamma/D-1} \exp(-y) dy =$  
    $\displaystyle c^{-\gamma/D} \frac{\Gamma(k+\gamma/D)} {\Gamma(k)}$ (3.5)

since the gamma function is defined as [Abramowitz and Stegun, 1970]:
\begin{displaymath}
\Gamma(x) = \int_{0}^{\infty} t^{x-1} \exp(-t) dt \quad (x > 0)
\end{displaymath} (3.6)

Nearest neighbour distances will be averaged over a set of reference points. The expectation of the averaged distance to the $k$-th nearest neighbour is:
\begin{displaymath}
\mbox{E}\left\{ <r_{k}^{\gamma}> \right\} =
\mbox{E}\left\{ ...
...a \right\} =
C_N \frac{\Gamma(k+\gamma/D(\gamma))} {\Gamma(k)}
\end{displaymath} (3.7)

where
\begin{displaymath}
C_N = \frac{1}{N_{ref}} \sum_{i=1}^{N_{ref}}
{\left[ N p(x_i) V_{D(\gamma)} \right]}^{-\gamma/D(\gamma)}
\end{displaymath} (3.8)

and $N_{ref}$ is the number of reference points. In general an attractor is inhomogeneous, i.e. the dimension depends on the reference point, so that $D$ will depend on $\gamma$. We will estimate $D(\gamma)$ with
\begin{displaymath}
\ln {<r_{k}^{\gamma}>}^{1/\gamma} = C +
\frac{1}{D(\gamma)} \ln \left( \frac{k}{N} \right) +
\ln G(k,\gamma,D(\gamma))
\end{displaymath} (3.9)

where
\begin{displaymath}
G(k,\gamma,D(\gamma)) = {\left[
\frac{ \Gamma(k+\gamma/D(\gamma)) } { \Gamma(k) k^{\gamma/D(\gamma)} }
\right]}^{1/\gamma}
\end{displaymath} (3.10)

since $C_N \approx N^{-\gamma/D(\gamma)}$ and $ \frac{\Gamma(k+\gamma/D(\gamma))} {\Gamma(k)}
\rightarrow k^{\gamma/D(\gamma)}$ for large $k$. Here $G$ is called the ``correction function'' and it is close to unity for large $k$; $C$ is independent of $k$ and $N$. $D(\gamma)$ is called the ``dimension function'' [Badii and Politi, 1985] and it is non-decreasing. In this derivation we followed references [Pettis et al., 1979,Somorjai, 1986,Grassberger, 1985]. A firm basis using the formalism of local scaling indices is given in [van de Water and Schram, 1988].


next up previous contents
Next: Methods to estimate the Up: NEAREST NEIGHBOUR METHODS Previous: Introduction   Contents
webmaster@rullf2.xs4all.nl