Lesson 1

Probability theory is an important branch of mathematics, with applications in various areas of our lives: finance, insurance, healthcare, risk management, traffic flows, weather conditions. Probability theory is also used in various fields of computer science. Let us provide some examples.

• Algorithms.  For some problems, probabilistic algorithms are simpler and more efficient than deterministic ones. A well-known example is the quicksort algorithm. There are also problems for which we still do not know an efficient deterministic algorithm, but we know a simple and efficient probabilistic algorithm. Perhaps the most striking example of such a problem is polynomial identity testing.


• Protocols.  Using random numbers, it is possible to construct more efficient protocols. For example, a deterministic comparison of two files of size \(n\) over a network would require transmitting \(n\) bits, while probabilistically this can be done exponentially better, sending only \(O(\log n)\) bits.


• Cryptography.  When encrypting messages, it is customary to add random noise to the original message to ensure that the same message is always encoded differently; otherwise, an adversary intercepting the encoded message can determine that the same message is being transmitted without even decoding it.


• Game Theory.  In many games, strategies that do not use randomness are almost meaningless. For example, in the rock-paper-scissors game, there is no sense in using a deterministic strategy.


• Probabilistic Method.  The probabilistic method is a way to prove the existence of an object non-constructively: instead of presenting an explicit object with the required properties, we prove that a randomly chosen object has the desired properties with nonzero probability.


• Learning from data.  When a program classifies emails, ranks recommendations, or predicts the next word in a sentence, it often does not know the answer with certainty. Instead, it estimates probabilities from observed examples. This makes probability theory a language for training data, uncertainty, and evaluation.


• Data Analysis.  Probabilistic methods are often used in data analysis to handle noisy or incomplete data. For example, the maximum likelihood method helps find the most likely model parameters, and the bootstrap method allows us to assess the statistical reliability of results.


• Network Technologies.  In computer networks, probabilistic algorithms are used for traffic management, load balancing, and routing. For example, in data transmission protocols such as TCP, random delays help avoid congestion and collisions.