Module 7: Probability and Simulation

• \(lim_{n\to\infty} y_n\)
• \(lim_{n\to\infty} z_n\)
• \(lim_{n\to\infty} F(y_n)\)
• \(lim_{n\to\infty} F(z_n)\)

• Argue that \(\prob{X\gt k} = (1-p)^k\).
• Then write down the CDF.
• Write down an expression for \(\prob{3.11 \lt X \leq 5.43}\) in terms of the CDF.

Exercise 23: What is an example of a continuous rv associated with the QueueControl.java application?

The difficulty with continuous rv's:

• First, \(\prob{X=x} = 0\) for most continuous rv's \(X\).
       \(\Rightarrow\) This means we can't specify the distribution using a list.

• Second, it's not clear how we can get probabilities to sum to 1.
       e.g., for a rv that takes any real value in \([0,1]\), how do we sum probabilities?

• Fortunately, the CDF offers a way out.

Let's write some code to estimate a CDF:

• First, identify the range \([a,b]\) of interest.

• Then, break this up into \(M\) small intervals:
       \([a,a+\delta ], [a+\delta ,a+2\delta ], \ldots, [a+(M-1)\delta ,a+M\delta ]\)

• Maintain a counter intervalCount[i] for each interval.

• For any random value \(x\), identify the interval
       \(j = \lfloor \frac{x-a}{\delta} \rfloor \)
  and increment the count of every interval \(i \geq j\).

  

• Pseudocode:

      Algorithm: cdfEstimation (M, a, b)
      Input: number of intervals M, range [a,b]
      1.   δ = (b-a) / M
      2.   for n=1 to numTrials 
      3.       x = generateRV ()
      4.       j = floor ( (x-a) / δ )
      5.       for i=j to M-1
      6.           intervalCount[i] = intervalCount[i] + 1
      7.       endfor
      8.   endfor
           // Now build and print the CDF
      9.   for i=0 to M-1
      10.      midPoint = a + iδ + δ/2                           // Interval: [a+iδ,a+(i+1)δ]
      11.      print (midPoint, intervalCount[i] / numTrials)
      12.  endfor
      

• Sample code: (source file)

      static Function makeUniformCDF ()
      {
  	double a = 0, b = 1;
  	int M = 50;                   // Number of intervals.
  	double delta = (b-a) / M;     // Interval size.
  
  	double[] intervalCounts = new double [M];
  	double numTrials = 1000000;
  
  	for (int t=0; t<numTrials; t++) {
              // Random sample:
  	    double y = RandTool.uniform ();
              // Find the right interval:
              int k = (int) Math.floor ((y-a) / delta);
              // Increment the count for every interval above and including k.
              for (int i=k; i<M; i++) {
                  intervalCounts[i] ++;
              }
  	}
  
  	// Now compute probabilities for each interval.
  	double[] cdf = new double [M];
  	for (int k=0; k<M; k++) {
  	    cdf[k] = intervalCounts[k] / numTrials;
  	}
  
          // Build the CDF. Use mid-point of each interval.
          Function F = new Function ("Uniform cdf");
  	for (int k=0; k<M; k++) {
  	    double midPoint = a + k * delta + delta/2;
              F.add (midPoint, cdf[k]);
  	}
  
          return F;
      }
       

Getting probabilities out of a CDF:

• Recall that for any rv \(X\) with CDF \(F\):
       \(\prob{y_1 \lt X \leq y_2} = F(y_2) - F(y_1)\)

• Thus, for example, if \(X\) has the uniform CDF
       \(\prob{0.75 \lt X \leq 1.0} = F(1) - F(0.75)\)

• Important: the CDF gets you the probability that \(X\)'s outcome lands in any particular interval of interest:
       \(\probm{X falls in any interval (a,b]} = F(b) - F(a)\)

A small technicality that goes to the heart of a continuous rv:

• Notice something peculiar about the statement
       \(\probm{X falls in any interval (a,b]} = F(b) - F(a)\)

• The interval is NOT written as \([a,b]\) or \((a,b)\) or \([a,b]\).

• Instead, it's written as: \((a,b]\)

• Recall from earlier: $$\eqb{ F(y_2) & \eql & \prob{X \leq y_2} \\ & \eql & \prob{X \leq y_1} + \prob{y_1 \lt X \leq y_2}\\ & \eql & F(y_1) + \prob{y_1 \lt X \leq y_2} }$$ and so $$ \prob{X \in (y_1,y_2]} \eql \prob{y_1 \lt X \leq y_2} \eql F(y_2) - F(y_1) $$

• What does this mean?

  

  The interval \((a,b]\) includes \(b\) but does NOT include \(a\).

• Why is this relevant?

  

  • Because a discrete rv's CDF has jumps
         \(\Rightarrow\) We need to account for the jump points carefully.
  • We say that the CDF for a discrete rv is discontinuous.
  • A continous rv's CDF, on the other hand, is continuous (smooth, no jumps).
         \(\Rightarrow\) Inclusion or exclusion of an end point makes no difference.

• Another related point: consider \(\lim_{a\to b} F(b) - F(a)\)

  

  • For a continuous rv
         \(\lim_{a\to b} F(b) - F(a) = 0\)
  • This is why \(\prob{X=a} = 0\)
         \(\prob{X=a} = \lim_{b\to a} F(b)-F(a) = 0\)

• A few more observations:
  • A discrete rv's CDF is continuous in places
         In fact, it's discontinous only at the points where the jumps occurs
  • So, is this useful?

    

    
         No, because the non-jump points never actually occur
         \(\Rightarrow\) We are never interested in probabilities of intervals between jump points.
         \(\Rightarrow\) Those probabilities are always zero.

• Finally, since \(F\) is continuous for a continuous distribution, we might ask: is the derivative \(F'\) of any value?
       We'll explore this next.

About CDFs and derivatives:

• The concept of CDF applies to both discrete and continuous rv's.

• The CDF of a discrete rv is not differentiable.

• For continuous rv's, the derivative is called a probability density function (pdf).

• The pdf has two uses:
  • It's useful in some calculations as we'll see below.
  • Most books use the pdf
         \(\Rightarrow\) You need to be comfortable with the pdf to read them.

• For completeness, note that the list of probabilities for a discrete rv is called a probability mass function (pmf), e.g.
       \(\prob{X=0} = 0.064\)
       \(\prob{X=1} = 0.288\)
       \(\prob{X=2} = 0.432\)
       \(\prob{X=3} = 0.216\)

• Customarily, a discrete rv's distribution is specified by giving its pmf.
       \(\Rightarrow\) The CDF is not really useful for discrete rv's

• Customarily, a continuous rv's distribution is specified by giving its pdf.
       \(\Rightarrow\) The CDF is equivalent (because you can take its derivative to get the pdf)

• To summarize:
  • Discrete rv's use a pmf.
  • Continuous rv's use a pdf.
  • Both use a CDF.

7.6   Expectation - the discrete case

The expected value of a rv is a calculation performed on its distribution:

• If \(X\) is a discrete rv with range \(A\), then $$ \mbox{Expected value of }X \eql \sum_{k\in A} k \; \prob{X=k} $$

• We write this as $$ E[X] \eql \sum_{k\in A} k \; \prob{X=k} $$

• Note: this is merely a calculation, and (so far) has nothing to do with the English word "expect".

• \(E[X]\) is a number (not a function).

• Example: recall the 3-coin-flip example where \(X\) = number-of-heads (we'll use \(\prob{H}=0.6\)).
  • The range: \(A = \{0,1,2,3\}\).
  • The pmf:
         \(\prob{X=0} = 0.064\)
         \(\prob{X=1} = 0.288\)
         \(\prob{X=2} = 0.432\)
         \(\prob{X=3} = 0.216\)
  • Thus, $$\eqb{ E[X] & \eql & \sum_{k\in \{0,1,2,3\}} k \; \prob{X=k} \\ & \eql & 0 \; \prob{X=0} + 1 \; \prob{X=1} + 2 \; \prob{X=2} + 3\; \prob{X=3} \\ & \eql & 0*0.064 + 1*0.288 + 2*0.432 + 3*0.216 }$$