Topics in The Theory of Computation

Probability - A very short course:

A Probabalistic Computer:

  1. Take two urns, each containing $\QTR{Large}{1000}$ balls of identical size, labled$\QTR{Large}{.000}$ to $\QTR{Large}{.999}$. Perform the following computation:

  2. Without looking, select one ball from each urn. We denote them by their lables "$\QTR{Large}{x}$" and "$\QTR{Large}{y}$".

  3. Compute MATH , record the result, and put the balls back into their urns.

  4. Repeat 1. 2. 3. a few hundred times.

  5. Count the number of times that MATH MATH .Multiply this number by $\QTR{Large}{4}$. The result is an approximation to $\QTR{Large}{\pi .}$

Why?

Terminology :

Suppose we have an experiment with a finite number of possible outcomes, all of which depends on chance.

  1. The sample space of the experiment is the set of all possible outcomes.In general we will use the letter $\QTR{Large}{S}$ to denote such a set and MATH to denote members of $\QTR{Large}{S}$ .

  2. A probability distribution (or just distribution ) on $\QTR{Large}{S}$ is a real valued function MATH such that

Examples:

Expected Value:

Suppose we are given a a distribution $\QTR{Large}{p\ }$on $\QTR{Large}{S}$ and a function MATH . The expected value $\QTR{Large}{E(f)}$ is defined by the formula

MATH

Example:

In the second example above, suppose MATHand MATH

then MATH

______________________________________________________

Metric Spaces - A very short course.

Definition:

We can abstract the notion of Euclidian Distance as follows

A Metric Space is a set $\QTR{Large}{M}$ and a function MATH. We write MATH

such that for all MATHin $\QTR{Large}{M}$:

  1. Positivity: MATH0 unless MATH in which case MATH0$\QTR{Large}{.}$

  2. Symmetry: For all MATH

  3. Triangle Inequality: For all MATH

Lemma:

The the Triangle Inequality has a second, equivalent form:

For all MATH

Proof:

Assume for the moment that

MATH . The Triangle Inequality as written implies

$\qquad \qquad $0 MATH

If MATH

then, since the Triangle Inequality is symetric in MATH and MATH rewrite it as:

MATH

_____________________________

Hamming Distance for Bytes - An Example from Computer Science:

Definition:

The Hamming distance between two bytes is defined to be the count of the number of positions in which the corresponding bits differ.

For example:

MATH

Error Detecting Codes:

Suppose we transmitting a byte code with an acceptably low probability of more than a single bit being in error.

A code is said to be error detecting if MATH for MATH

It is called error correcting if MATH

Analysis:

Our assumption that we can assume that the transmission has at most one bit in error translates to the assumption that if we see a byte

$\QTR{Large}{x\ }$then MATH for some MATH If MATH then we can assume that that is the correct character. If MATHfor all MATH then we can assume that there is an error.

Note that since MATH if MATHthen we cannot have MATH and MATH

simultaneously. So if, say MATH we can assume that MATH is the actual byte that was transmitted.

ascii

_________________________________________________