5. Probabilistic Algorithms

A probabilistic algorithm is an algorithm that employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits. [1]

5.1. Pseudo-Random Number Generator (PRNG)

5.2. Primality Test

5.2.1. Fermat little theorem

Fermat's little theorem is a fundamental theorem in elementary number theory, which helps compute powers of integers modulo prime numbers. It is a special case of Euler's theorem, and is important in applications of elementary number theory, including primality testing and public-key cryptography. [2]

$$ a^{n-1} mod(n) = 1 \quad \forall \quad 1 \leq a \leq n - 1 \tag{1} $$

5.2.2. Miller-Rabin approach

Rabin–Miller primality test is an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test. [3]

Algorithm description:

So, Let's run the Miller-Rabin test for the first N numbers:

5.2.3. Generator of pseudo-random prime numbers

The generation of pseudorandom prime numbers has great relevance, especially for cryptographic purposes.

5.3. Monte Carlo Simulation

Monte Carlo methods are non-deterministic or stochastic algorithms, and are based on the use or generation of pseudo-random numbers to model or simulate different phenomena. The Monte Carlo algorithms occasionally make an error, but they find the correct solution with a high probability whatever the case considered.

5.3.1. Integration with Normal distribution

5.3.2. Integration with Uniform distribution

5.4. Metropolis-Hastings Algorithm

In statistics and statistical physics, the Metropolis–Hastings algorithm is a Markov chain Monte Carlo (MCMC) method for obtaining a sequence of random samples from a probability distribution from which direct sampling is difficult. This sequence can be used to approximate the distribution (e.g. to generate a histogram) or to compute an integral (e.g. an expected value). [4]

5.5. Las Vegas Algorithm

Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the input. The usual definition of a Las Vegas algorithm includes the restriction that the expected runtime be finite, where the expectation is carried out over the space of random information, or entropy, used in the algorithm. [5]

5.5.1. Quick Example

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n = 2 and n = 3. [6]

5.5.2. Law of large numbers

In probability theory, the law of large numbers (LLN) is a theorem that describes the result of performing the same experiment a large number of times. According to the law, the average of the results obtained from a large number of trials should be close to the expected value, and will tend to become closer as more trials are performed. [7]

Based on the law of large numbers calculate the probability of success of this Las Vegas algorithm.

5.5.3. Plotting the last solution

Reference

[1] Wikipedia - Randomized algorithm.
[2] Brilliant - Fermat's little theorem.
[3] Wikipedia - Miller–Rabin primality test.
[4] Wikipedia - Metropolis–Hastings algorithm.
[5] Wikipedia - Las Vegas algorithm.
[6] Wikipedia - Eight queens puzzle.
[7] Wikipedia - Law of large numbers.


« Home