Let $X \subseteq \mathbb{R}^d$ be a set of points and let $r > 0$ be a parameter. The \textit{geometric graph} $G(X, r)$ is the undirected graph with the vertex set $X$ and edges between points $x$ and $y$ if and only if $||x - y|| \leq r$ (for some norm $||\cdot||$ on $\mathbb{R}^d$, for example the Euclidean norm). The \textit{random geometric graph} is the geometric graph with points generated by the Poisson point process.

\section{Introduction to probability}

We have a set $S$ and a probability function $f: \mathcal P(S) \rightarrow [0,1]$.

\textit{Random variable} is a function $X: S \rightarrow \mathbb{R}$. The \textit{expected value} $\E(X)$ of a discrete random variable $X$ with values $a_1, a_2, \dots\, a_n$ is defined by $\sum^n_{i=1} a_i \Pr(X = a_i)$. For a continuous random variable $X$ for which $\Pr(X \in (a, b)) = \int^b_a f(x) dx $ ($f$ is the density function) the expected number is $\int_{-\infty}^{+\infty} x f(x) \, \mathrm{d}x$.

The \textit{Poisson variable} is random variable $X$ (we denote it by $X \sim \operatorname{Pois} (\lambda)$), for which $\Pr(X = k) = e^{-\lambda}\frac{\lambda^k}{k!}$, where $k \geq 0$ and $\lambda > 0$ is a parameter.

\begin{thm}[Markov inequality] For all nonnegative random variables ($X \geq 0$) and $a > 0$ it holds that $\Pr(X \geq a) \leq \E(X)/a$
\end{thm}

For Poisson variables:
$\Pr(\mathrm{Pois}(\lambda) \geq k) \leq \mathrm{exp}\left({-\lambda H\left(\frac{k}{\lambda}\right)}\right)$ where $H(x) = 1 - x \log x + x$ for $x \geq 0$.

\medskip

The following is satisfied:

$$e^x = \sum^{\infty}_{k = 0} \frac{x^k}{k!}.$$

For a sequence $\left\lbrace a_n \right\rbrace \uparrow \infty$ it holds:

$$\left(1 - \frac{1}{a_n}\right)^{a_n} \uparrow \frac{1}{e} \qquad \text{and}$$

$$\left(1 + \frac{1}{a_n}\right)^{a_n} \uparrow e.$$

\section{Poisson Point Process}

A \textit{Poisson Point Process} $\mathcal{H}$ in $\mathbb{R}^d$ with intensity $\lambda$ is the process that spreads points randomly into the given space and for every disjoint sets $A_1, A_2, \dots\ A_l \subseteq \mathbb{R}^d$ holds that
\begin{align*}
\Pr(\zeta(A_1) = k_1, \zeta(A_2) = k_2, \dots\ \zeta(A_l) = k_l)
& = \prod_{i = 1}^l \Pr(\zeta(A_i) = k_i) \\
& = \prod_{i = 1}^l e^{-\lambda \mathrm{Vol}(A_i)} \frac{(\lambda \mathrm{Vol}(A_i))^{k_i}}{k_i!}
\end{align*}
where $k_i$ are nonnegative and $\zeta(A_i)$ is the number of points from the process in the set $A_i$ (for every $i = 1, \dots\ l$).

Number of nodes $N_{\lambda}$ is a random variable for which $\E(N_{\lambda}) = \lambda \cdot \mathrm{Vol}$ ($\mathrm{Vol}$ is the volume of the region of P.P.P.) and $\Pr(N_{\lambda} = k) = e^{-\lambda \mathrm{Vol}} \frac{(\lambda \mathrm{Vol})^k}{k!}$. Thus the random variable $N_{\lambda}$ follows Poisson distribution with parameter $\lambda \cdot \mathrm{Vol}$.

\begin{thm}[Superposition Theorem] Let $\mathcal{P}$ and $\mathcal{P}'$ be independent Poisson Point Processes (P.P.P.) with intensities $\lambda$ and $\lambda'$, respectively. Then $\mathcal{P} \cup \mathcal{P}'$ is also a P.P.P. with intensity $\lambda + \lambda'$.
\end{thm}

\begin{thm}[Thinning Theorem] Let $\mathcal{P}$ be a P.P.P. with intensity $\lambda$ and let $p \in [0,1]$. We accept each point $X$ in $\mathcal{P}$ with probability $p$ and reject otherwise, independently on the other points. Let $\mathcal{P}'$ be the point process of all accepted points. Then $\mathcal{P}'$ is also P.P.P. with intensity $p \lambda$.
\end{thm}
\begin{thm}[Scaling Theorem] Let $\mathcal{P}$ be a homogeneous P.P.P. (i.e. P.P.P. with the same $\lambda$ on the whole region) on a region $A \subseteq \mathbb{R}^d$ and let $a > 0$. Let $a\mathcal{P}$ be the image of $\mathcal{P}$ under mapping $x \mapsto ax$ and let $aA$ be the image of $A$ under the same mapping. Then $a\mathcal{P}$ is homogeneous P.P.P on the region $aA$ with intensity $\lambda / a^d$.
\end{thm}