Fork me on GitHub
Math for the people, by the people.

User login

probabilistic method

Type of Math Object: 
Major Section: 

Mathematics Subject Classification

05C80 no label found11K99 no label found


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).

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.

Subscribe to Comments for "probabilistic method"