The subject of probability gives rise to some very interesting questions, which we believe everyone should be exposed to, even if to a minor extent. In this section, we’ll do precisely that. The examples will clearly show you the depth of this subject.
A drunk mathematician called is performing a random walk along the number line as follows. His original position is . He takes a step forward or a step backward with equal probability. Thus, for example, if he is at , he can go to or with equal probability.
His home is at , while there is a pit at . What is the probability that he’ll reach home before falling into the pit?
Assume the required probability to be . Thus, denotes the probability where
: reaches home before the pit
Now, let us draw the probability tree that will make happen:
What should the events and be and what should be their probabilities? Once has reached , the situation is as follows:
should therefore be the event that reaches before . Now comes the crucial insight. Compare Fig- with Fig-. The situations have been symmetrically reversed. In Fig -, was the probability that reaches before, that is, travels units in one direction before travelling in the other. In Fig-, is the probability that travels units in one direction before travelling in the other, so we simply have
Make sure you understand this argument carefully.
Coming to , has reached , he must return to , because he must not reach . Once he is at , he comes back to the starting configuration, which means that now his probability of reaching before is again .
So let us complete the probability tree of Fig- now:
Thus (pay attention to how we write this!),
This relation is a form of recursion. In the definition (or expression) of , we are using again. Thus, recursion is, in plain words, the process a ‘procedure’ goes through when one of the steps of the ‘procedure’ involves rerunning the procedure. In this example, the ‘procedure’ of calculating involved the step at which point we have to rerun the ‘procedure’ of calculating .
Thus, there is a chance that will return home safely!
Recursions can also take the following form: suppose we have to calculate , the term of some sequence, and suppose we are able to express as some function of , the previous term:
This is also a recursion relation, for now we can use this relation repeatedly to descend, that is, to reach some that is calculable:
For example, could be the first term of the sequence. Thus, here we are rerunning the ‘procedure’ .