The terms probabilistic method and probabalistic algorithm are used for methods of approximate calculation based on probability theory, e.g., monte-carlo algorithms, simulated annealing etc.
For example, there exist probabilistic algorithmic tests for proving primality, where the probability of error can be reduced to an arbitrary degree by performing enough independent tests.
If, using such a method, the probability of error is 2-1000, the philosophical question arises: is this a proof? After all the probability of error is distinctly smaller than the probability of an error in the reader's computer, or the reader themselves making an error in reading a proof - what does it mean in real terms to consider this small a probability?
If that does not seem extreme enough to be perplexing, consider a proof with an error probability of 2-1000000: the user only has to leave the computer running the probabilistic algorithm running a little longer. At this level, the odds against error are not only astronomically, but also cosmologically vast.
The term probabilistic method refers to a method of proof that uses probability to show the existance of something with certain properties. Although the proof uses probability, the final conclusion is determined for certain, without any possible error.
One way of doing this is by considering a randomly selected thing from a finite sized universe. If the probability that the random thing satifies the properties is greater than zero, then this proves the existance of a thing that satifies the properties. It doesn't matter if the probability is astronomically small; any probability strictly greater than zero will do. (Also, showing that the probability is zero can be used to prove the non-existance of such an object).
Another way to use the probabilistic method is by calculating the expected value of some random variable. If it can be shown that the random variable can take on a value less than the expected value, this proves that the random variable can also take on some value greater than the expected value.
The probabilistic method has many applications in graph theory.