Difference between Deterministic and Stochastic Algorithms

The word algorithm is often used as a vague label for the processes behind software. In precise terms, however, an algorithm is simply a defined procedure for solving a problem or performing a computation. This article demystifies the concept by providing a definition of what an algorithm is and exploring the key differences between deterministic and stochastic (or probabilistic) algorithm designs.

What is an Algorithm

An algorithm is essentially a set of instructions designed to perform a specific task or solve a particular problem. Wikipedia defines an algorithm as…

a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation.

Let’s break down this definition with a couple of examples from real life to make it more concrete.

Imagine you are playing a board game with some friends. Everyone understands the rules laid out in the manual. After each move, all players instinctively verify if it was valid based on the game’s rules. They check if the player was eligible to make that move, if the move was executed correctly, and whether the game remains in a legal state afterward. If any of these checks fail, the game halts, and the player is accused of breaking the rules. This repetitive process of rule verification can be thought of as an algorithm since it follows a fixed sequence of steps to ensure the game is played fairly.

Another everyday example is a cooking recipe. The instructions specify each step, in a particular order, that must be followed to produce the desired dish. If you deviate from the instructions, you may not end up with the intended result. Similarly, algorithms are structured sequences that must be followed to achieve a specific outcome.

Deterministic Design

Algorithm design encompasses various considerations such as complexity, efficiency, and operating principles. One of the fundamental approaches is deterministic algorithm design. In a deterministic algorithm, each step is determined by the input and the algorithm’s current state. Given the same input and the same specified conditions, a deterministic algorithm will follow the same computation and produce the same output.

For instance, let’s consider a simple example of a calculator tasked with finding the digit sum of 123. The algorithm might involve adding each digit one by one: \(1 + 2 + 3 = 6\). No matter how many times you perform this calculation, the result will always be 6. The steps are followed in the exact same order every time, so the output is consistent. This predictability is why we categorize such algorithms as deterministic.

Deterministic algorithms are particularly valuable in scenarios where reliability and accuracy are crucial. Systems like banking software or transaction processing platforms often rely on deterministic behavior so that operations are consistent and reproducible. Determinism does not itself make software error-free, faster, or easier to optimize; it only makes its behavior predictable under the same specified conditions.

Stochastic Design

Now, let’s shift our focus to stochastic algorithms, which take a different approach to problem-solving. Unlike deterministic algorithms, stochastic algorithms incorporate randomness in their decision-making process. This means that the same input may lead to different computations or outputs on different runs, although a fixed random seed can make a pseudorandom run reproducible.

Stochastic algorithms can be useful when dealing with problems that are too complex to solve exactly within a practical amount of time. For example, some problems have so many possible solutions that even the fastest supercomputers would take centuries to evaluate them all. However, computational difficulty does not imply that a stochastic method is required: deterministic approximation algorithms, heuristics, branch-and-bound methods, and exact exponential-time algorithms are also available.

Expressed in complexity notation, a polynomial running time can be written as \(T(n) = O(n^k)\), while an exponential running time might be written as \(T(n) = O(c^n)\), where \(k\) and \(c > 1\) are constants and \(n\) is the input size. The complexity class nondeterministic polynomial time (NP) contains decision problems whose proposed solutions can be verified in polynomial time by a deterministic machine, or equivalently solved in polynomial time by a theoretical nondeterministic machine.

Whether every problem in NP can also be solved in polynomial time is the unresolved P versus NP problem. One famous related problem is the Travelling Salesperson Problem (TSP). It asks for the shortest tour that visits every city once and returns to the starting city. The optimization version of TSP is NP-hard, while the decision version—which asks whether a tour no longer than a given bound exists—is NP-complete. Stochastic (or probabilistic) algorithms are one possible tool for finding a good, though not necessarily optimal, solution. The key point in these kinds of algorithms lies in the incorporation of randomness during the computation process.

The word stochastic originates from the Greek verb stokházomai which means something like «aim at a target» and «guess». Unlike a deterministic approach, a stochastic approach allows some decisions to be influenced by random values. An iterative calculation process may therefore return different outputs with the same input.

Conclusion

Algorithms serve as tools, each suited for specific types of problems. For straightforward, well-defined tasks where exact solutions are feasible, such as calculating digit sums, deterministic algorithms are a natural choice. For complex NP-hard problems where finding an exact solution is computationally impractical, stochastic algorithms can provide a practical alternative alongside deterministic methods. While these algorithms may not always find the optimal solution, generating a good enough solution is often better than having none, especially within limited time constraints.