Recursive Probability Problems
Recursions and their solutions have interesting applications, namely in random walk problems. The random walk problems are applicable to problems in many fields. One approach to the random walk problem is a gambling situation and another line of approach involves Markov chains.
Recursion relation:
1.A simple counting problem
In how many n distinct objects can be arranged?
The obvious solution is n!. Let P(n)denote the number of arrangements(permutations) of n distinct objects. P(n) is a function of n. If we were permute n-1 distinct objects, then for a given permutation of n-1 objects, each one of the n choices for the n th object gives a distinct permutation. This reasoning leads to
The abovementioned form of an equation is called a recursion or recurrence relation or difference relation.
A discrete probability distribution can be represented by a recurrence relation. For example, the binomial probability distribution
The primary value of a recursion is that, given a starting value or a seed value, any value of the function can be determined. Many interesting problems can be represented by recursions. Let us now turn our attention to recursions that arise in connection to probability. The next example does two things : 1) The problem is represented by a recursion and 2) the number of entries in the sample space is a Fibonacci sequence.
2. Consider observing single births in a hospital until two girls are born consecutively. Let us construct the sample space, G denoting a girl is born and B, the birth of a boy.
The number of sample points in as shown in the table follows the sequence 1, 1, 2, 3, 5, 8… which we recognize is a Fibonacci sequence.
What is the general pattern in the entries?
Why does the Fibonacci sequence occur?
Let us try to understand how GG occurs for the first time say, in the third birth. In this case, there is only one possibility, that is the sequence begins with a B.
In the fourth birth the occurrence of GG for the first time , there are two possibilities for the beginning of the sequence. These two possibilities are mutually exclusive; that they cannot occur simultaneously. The first possibility is that the sequence begins with B and is followed for the first time by the occurrence of GG in three births. The other possibility is that the sequence would begin with a G and would be followed by the occurrence of GG in three births.
Let us generalize this to n births. Consider a sequence of B’s and G’s in which GG occurs for the first time say, in the nth birth. Let t(n) denote the number of ways in which this can occur. Reasoning as before, we have two mutually exclusive possibilities for beginning the sequence. The first possibility is that the sequence begins with B and is followed for the first time by the occurrence of GG in n-1births. This can occur in t(n-1) ways. The other possibility is that the sequence would begin with a G, followed by a B, and then the pattern GG occurs in n-2 births. This occurs in t(n-2) ways. Therefore,
The recursion relation above describes a Fibonacci sequence.
The recursions are easily programmed. Computer algebra systems are used to compute t (n) for large values of n.If n=25, then there are 46,368 ways for the sequence GG to occur for the first time.
In the next part, we will discuss the applications of recursion to the problem of random walk by illustrating a gambling situation.
