============================================================================
CSC 263              Notes on Tutorial 1                    Winter 2019
============================================================================

1. About Indicator Random Variables (IRV)

An indicator random variable X_e of an event e indicates whether event e
happens or not, so it's defined as follows

          { 1  if e happens
    X_e = {
          { 0  if e doesn't happen


One important property of indicator random variables is the following equality

   E[X_e] = Pr(e happens)

You can easily prove this equality by trying to compute the expectation of X_e.


2. For the analysis of the FIND-MAX algorithm, we define a sequence of IRVs in
the following way:

   X_k for indicating the following event: 
       e_k: the assignment line max = L[k] is executed

where k takes value from L.length - 1 (i.e., n-1) down to 0, therefore the
expected total number of times that "max = L[k]" is executed is simply the
following sum
 
       n-1         n-1          n-1
    E[ SUM X_k ] = SUM E[X_k] = SUM P(e_k happens)
       k=0         k=0          k=0

So, now the only thing left is to figure out P(e_k happens).


3. Figure out P(e_k)

We have no idea what this probability is without defining the input
distribution. So here we choose the following distribution of the inputs: X is
the random permutation of [1,2,...,n], and each permutation is equally likely to
be chosen. The following analysis will be based on this assumption on the input
distribution.

As mentioned above the event e_k is 

   e_k: the assignment line max = L[k] is executed, which is equivalent to
        L[k] > max, which is equivalent to
        L[k] is the max among the first k+1 elements (note k starts from 0)

Since all permutations are equally likely, each one of the first k+1 elements
is *equally likely* to be the max, therefore the probability that L[k] is the
max among the first k+1 elements is:

                             1/(k+1)

So the desired average-case runtime becomes

    n-1                  n-1
    SUM P(e_k happens) = SUM 1/(k+1) = O(log n)
    k=0                  k=0

To see why the last equality is true, Google "harmonic series" if you are
interested.