Random Tools

This page regroup the tools in domain of probability of statistic.

1. Source Point distribution

To choice a random point, we use uniform distribution on cirumscribed circle.

Thus circle \(\mathcal{C}\) (we suppose th center is the origin) of ray \(R\).

We want to find a method to create a random point with thise uniform distribution.

\begin{eqnarray} P = \begin{pmatrix} R \sqrt{\xi_2} cos 2\pi \xi_1 \\ R \sqrt{\xi_2} sin 2\pi \xi_1 \end{pmatrix} \end{eqnarray}

With \(\xi_1\) ans \(\xi_2\) random point on uniform distribution on \([0,1]\).

2. Source Point Complexity

We want to know the complexity of algorithm Source Point (with triangle \(\mathcal{T}\)). This complexity is regit by a geometrical distribution.

2.1. Geometrical Distribution

Rappel of geometrical distribution :

The probability distribution of the number X of Bernoulli trials needed to get one success.

If \(p\) is the probability of success :

\[\mathbb{P} \left( X = k \right) = \left( 1-p \right)^{k-1} p\]

We have some reults :

  • esperance : \(\mathbb{E}(X) = \frac{1}{p}\)

  • variance : \(Var(X) = \frac{1-p}{p^2}\)

  • variance : \(\sigma(X) = \sqrt{\frac{1-p}{p^2}} = \frac{\sqrt{1-p}}{p}\)

2.2. Link with algorithm

The choise of random point is regit by distribuni. The complexity of algorithm Source Point is regit by geometrical distribution of parameter :

\[p = \frac{\int_{O \in \mathcal{T}}{dO}}{\int_{O \in \mathcal{C}}{dO}} = \frac{Area(\mathcal{T})}{Area(\mathcal{C})}\]

With \(\mathcal{C}\) the circumscribed circle of center \(C\) and ray \(R\).

2.3. Complexity

To calculus of complexity of Source Point (with triangle \(\mathcal{T}\)), we take :

\[\text{complexity} = \mathbb{E}(X) = \frac{1}{p}\]

With the ratio \(p = \frac{Area(\mathcal{T})}{Area(\mathcal{C})}\)

2.4. Example

2.4.1. Equilateral triangle

We take the equilateral triangle \(\mathcal{T}\) (of side \(1\)). We calculate its areas and areas of its circumcribled circle.

  • \(Area(\mathcal{T}) = \frac{\sqrt{3}}{2}\)

  • \(Area(\mathcal{C}) = \frac{2\pi}{3}\)

  • \(p = \frac{3\sqrt{3}}{4\pi} \thickapprox 0.413\)

  • Complexity \(born \thickapprox 2.41 \leq 3\)

We can suppose the number of loop of algorithm is a \(3\) for the case of equilateral triangle.

Remarks : the case of equilateral triangle maximizes \(p\) (I think).

2.4.2. Right triangle

We take the right triangle \(\mathcal{T}\) (of side \(1\)). We calculate its areas and areas of its circumcribled circle.

  • \(Area(\mathcal{T}) = 1\)

  • \(Area(\mathcal{C}) = 2\pi\)

  • \(p = \frac{1}{2\pi} \thickapprox 0.159\)

  • Complexity \(born \thickapprox 6.2\)

We can suppose the number of loop of algorithm is a \(6\) for the case of right triangle.

3. Reference