## You are here

Homeprobabilistic method

## Primary tabs

# probabilistic method

The *probabilistic method* was pioneered by Erdős Pál (known to Westerners as Paul Erdős) and initially used for solving problems in graph theory, but has acquired ever wider applications. Broadly, the probabilistic method is somewhat the opposite of extremal graph theory. Instead of considering how a graph can behave in the most extreme case, we consider how a collection of graphs behave “on average”, whereby we can formulate a probability space. The fruits reaped by this method are often raw existence theorems, usually deduced from the fact that the nonexistence of whatever sort of graph would mean a zero probability. For instance, by means of the probabilistic method, Erdős proved the existence of a graph of arbitrarily high girth and chromatic number, a very counterintuitive result. Graphs tend to get enormous as the chromatic number and girth increase, thereby severely hindering necessary computations to explicitly construct them, so an existence theorem is most welcome.

In all honesty, probabilistic proofs are nothing more than counting proofs in disguise, since determining the probabilities of interest will invariably involve detailed counting arguments. In fact, we *could* remove from any probabilistic proof any mention of a probability space, although the result may be significanltly less transparent. Also, the advantage of using probability is that we can employ all the machinery of probability theory. Markov chains, martingales, expectations, probabilistic inequalities, and many other results, all become the tools of the trade in dealing with seemingly static objects of combinatorics and number theory.

# References

- 1 Noga Alon and Joel H. Spencer. The probabilistic method. John Wiley & Sons, Inc., second edition, 2000. Zbl 0996.05001.
- 2 Paul Erdős and Joel Spencer. Probabilistic methods in combinatorics. Academic Press, 1973. Zbl 0308.05001.

## Mathematics Subject Classification

05C80*no label found*11K99

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## October Ponder This

Consider a frog starting from 0 and jumping from integer to integer. With probability p he makes a jump of +1, with probability (1-p) a jump of -1. Assume .5 < p < 1. Assume each jump is independent. Let B(n,k) denote the binomial coefficient n choose k.

a. How fast will the frog move towards +infinity?

b. How many times on average will the frog visit each non-negative integer?

What is the probability the frog will be at 0 after 2*n jumps?

Combine 1b and 2 to find the sum from 0 to infinity of (x**n)*B(2*n,n). (0 < x < .25).

## Re: October Ponder This

Hi Parashar,

This is the well known asymetric random walk problem. It has been studied by physicists at stone age. I guess it came up at the IBM site after archeologic excavations?

Nowadays, it is very easily handled using the Z-transform technique (or characteristic functions for mathematicians). For example the answer to the first question is simply (2p - 1), after n steps, the average position is n(2p-1). There is no need to go into the details of the probability at each step, using the B(n,k) coefficients.

If the mean progress is 2p-1 for every step, the average number of visits at each non-negative integer is obviously 1/(2p-1). There is nothing to compute here.

The last question seems to be a direct consequence of the hard work invested by IBM in solving the first two questions. I got the result by direct summation/integration of the expression, using the gamma function. The sum is 1/sqrt(1-4x); hence the limitation x < 0.25.