Difference between Deterministic and Stochastic Algorithms

The term algorithm is often used when IT people don’t want to explain how something works in detail. It is commonly used as a wrapper term for all the enigmatic things going on in software applications. 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…

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, the outcome is entirely predictable. Given the same input, a deterministic algorithm will always produce the same output, making it highly reliable and consistent.

For instance, let’s consider a simple example of a calculator tasked with finding the cross total 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 rely on deterministic algorithms to ensure that outputs are consistent and error-free. Since these algorithms always yield the same result for the same input, they can be optimized for speed and performance, which is essential in high-stakes environments.

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 can lead to different outputs on different runs, making them less predictable but often more flexible in handling complex problems.

The need for stochastic algorithms becomes evident when dealing with problems that are too complex for deterministic methods to handle efficiently. For example, some problems have so many possible solutions that even the fastest supercomputers would take centuries to evaluate them all. In such cases, we talk about problems with a nondeterministic polynomial (NP) time hardness. In other words, there are no algorithms which could solve these kinds of problems in a polynomial time.

Expressed in complexity notation, algorithms that follow polynomial time complexity are \(O(n^k)\), while NP is \(O(k^n)\), where \(k\) is a constant and \(n\) is the variable input size of the problem.

The classification, which problems can be solved in polynomial time and which cannot (nondeterministic polynomial time) is, by the way, a big issue for itself, named «P vs. NP». In case you want to learn more about this problem, I recommend this article. One of the most famous ones is called the Travelling Salesman Problem (TSP). It is about finding the shortest closed path (circuit) in a set of cities (vertices). Stochastic (or probabilistic) algorithms serve as a suitable tool to still come up with a decent solution, however not optimal one. The key point in these kinds of algorithms lies in the incorporation of randomness during the computation process.

The word stochastic originates from the Latin expression stokházomai which means something like «aim at a target» and «guess». So instead of a deterministic approach, where the algorithm’s steps remain the same, the stochastic approach always involves some unforeseeable decisions due to the influence of randomness. An iterative calculation process will 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 cross totals, deterministic algorithms are the optimal choice. However, for complex problems with NP-hard characteristics, where finding an exact solution is computationally impractical, stochastic algorithms provide a practical alternative. 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.