Mathematics

Reading characters with Markov chains

It seems strange that mathematics can say anything about chance events. Before one flips a coin, the result -- heads or tails -- is not predictable. Predicting the result of a horse race is somewhat easier: even though the strongest/ fastest horse is usually not guaranteed to win, it can be expected to win more frequently than the others.

The word probability is used for an idea which can be described as that the probability of an event -- such as getting heads on a coin toss -- is related to the ratio, of the number of times that the event happened, and the number of times that the experiment -- throwing the coin -- was performed. These probabilities do satisfy certain mathematical formulas.

We are going to look at experiments, called Markov chains, which can be roughly described in the following way. We observe one number, some number between 1 and N where N is some integer, on every day. The days are numbered 1,2,3 and so on. We assume that to calculate the probabilities of events that talk about day n+1, we only need the information about what happened on day n. That is, we do not need to know what happened on days one, two, and so on, up to n-1. In short, the "history" of the process does not give more information when we calculate probabilities.

These kind of processes play an important role in certain methods which enable a computer to recognize the characters which appear in a digital image. This is because as the image is scanned with a vertical strip moving from left to right, the character "a", for example, would give certain features with different probabilities than the character "b" would. There is uncertainty, and probabilities, because scanning in a typed page into a digital image do not always give the same result, due to measurement errors, different typefaces, and so on.

Our goals will be:

1. To learn more about these processes and the mathematics behind it.
2. To understand the relevance of Markov chains in this situation.
3. To write a computer program that can distinguish between two characters read
   from an image scanned from a typed document.
   

Participants

• Dr. Gusti van Zyl