
Let $X \subseteq \mathbb{R}^d$ be a set o points and let $r > 0$ be a parameter. We denote \textit{geometric graph} $G(X, r)$ the undirected graph with 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 Euclidean norm). The \textit{random geometric graph} is the geometric graph with points generated by a random 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 number} $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 = x) = f(x)$ ($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 \frac{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

We will use these equations:

$$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}$$

$$\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 $\Pr(\zeta(A_1) = k_1, \zeta(A_2) = k_2, \dots\ \zeta(A_l) = k_l) = \prod_{i = 0}^l \Pr(\zeta(A_i) = k_i) = \prod_{i = 0}^l e^{-\lambda \mathrm{Vol}(A_i)} \frac{(\lambda \mathrm{Vol}(A_i))^{k_i}}{k_i!}$ 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 Vol$ ($Vol$ is volume of the region of P.P.P.) and $\Pr(N_{\lambda} = k) = e^{-\lambda \cdot Vol \frac{(\lambda Vol)^k}{k!}}$. Thus the random variable $N_{\lambda}$ follows Poisson distribution with parameter $\lambda \cdot Vol$.

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

\begin{thm}[Thinning Theorem] Let $\mathcal{P}$ is 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}$ is a homogeneous P.P.P. (i.e. P.P.P. with the same $\lambda$ on 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 a region $aA$ with intensity $\frac{\lambda}{a^d}$.
\end{thm}