4
$\begingroup$

Why are random numbers important to the study and application of computer science? I am new to computer science. So I am studying random numbers right now.

$\endgroup$
3
  • $\begingroup$ Randomness rules the world and our lives. It is pervasive in computer science as well. If I had to write my full-fledged answer, it would take me at least a few hours. $\endgroup$
    – John L.
    Dec 9 '18 at 6:40
  • 2
    $\begingroup$ Randomized algorithms are sometimes much more efficient than deterministic ones. The classical example is primality testing. Sometimes only randomized algorithms are known, for example many factoring algorithms. $\endgroup$ Dec 9 '18 at 8:59
  • 1
    $\begingroup$ Randomness is crucial for cryptography. $\endgroup$ Dec 9 '18 at 9:00
4
$\begingroup$

There are a lot of applications of Random numbers in Computer science, there are full books about it, check Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan, for instance. There you will find many arguments for the case of random numbers.

Here is a not exhaustive list of applications in sub-fields of CS:

  • Algorithms (As Yuval pointed, there are many problems where only randomized algorithms are known and you will find that many times randomized algorithms are simpler and more efficient than their deterministic counterpart)

  • Machine Learning ( Generative algorithms, variational autoencoders, GANS, Bayesian inference, Monte-Carlo algorithms, ...)

  • Cryptography(randomized prime number testing, ...)
  • Computer graphics and simulation (Path Tracing, Procedural stuff, games, ...)
  • Big Data (search for sketching algorithms, probabilistic counting, Bloom filters, ...)
  • Optimization (stochastic gradient descend, meta-heuristics)
  • Simulation (random processes, multi-agent, stochastic differential equations,...)

I am sure there are plenty more.

$\endgroup$
1
$\begingroup$

We may agree that statistics is important, for instance to test whether a new drug will help cure a disease, or whether a presidential candidate has sufficient support to be elected.

The cornerstone of statistics is the simple random sample whereby out of a large population of $N$ individuals we select $n$, a still large but much smaller number, in such a way that any set of $n$ individuals is equally likely.

And randomness is used to break undesirable patterns such as doing the same, or similar, things over and over, becoming predictable to our adversaries or to those we try to entertain.

Traditionally this was all done by any number of methods, I suppose, such as rolling dice or pointing a finger at a page in a book. Naturally now we want and need computers to do it, and it seems that they can. However, in theory the whole universe may be deterministic, so that any computer method of producing randomness requires careful scrutiny to see whether it might deliver biased results, especially if we're talking about delivering random bits many times a second.

Knowing that adversaries may be using randomness, there's also the question whether randomness can be used to speed up computational tasks, see e.g. the BPP=P question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.