ECS 252     Local & Metropolitan Area Networks   Assigned: Feb.  3, 1998
Winter 98               Assignment 2             Due:      Feb. 10, 1998
                                                              (In class)


Note:
+  If you make any assumptions, please write them down clearly.
+  Do not assume that the person grading your work will correctly "guess"
   your assumptions.
+  When multiple solutions to a problem exist, the best solution will fetch
   the maximum credit.


1. Text (Hammond), pp. 108, Problem 3-3

2. Text (Hammond), pp. 109, Problem 3-17

3. Consider a "packet" which has to be processed in a number of "nodes"
   (say n). Assume that all "nodes" are identical, and the time spent in
   a "node" is an integer-valued random variable X uniformly distributed
   between 2 and 11.
   Denote by T(n) the time measured from the instant the "packet" enters
   the first "node" until its processing is completed at the nth "node".

   (a) Obtain the distribution of T(n) for n=1, n=2, and n=3.

   (b) Given that a "packet" has to meet a deadline D(n) (or else it is
       "lost"), what fraction of "jobs" are "lost" if D(n) = 10*n for
       n=1, n=2, and n=3?

   *Hint*: Consider two independent integer-valued random variable Y1
   and Y2 whose distributions P[Yi(j) = yi(j), j = 0,1,2, ... ; i = 1,2]
   are known.  Their sum Z = Y1 + Y2 is also a random variable, and
   the distribution of Z is given by the "convolution"
                   k
     P[Z = zk] = SIGMA  y1(m) . y2(k-m)
                  m=0

6. Consider the "shifted" geometric distribution:

             {   p(1-p)^(i-T)    i = T, T+1, T+2, ...
      P(i) = {
             {   0               otherwise

   Find the first moment, second moment, second central moment,
   standard deviation, and coefficient of variation of P(i).

7. For the following discrete-time Markov chain,

   (a) what are $pi_1^{(2)}$ and $pi_2^{(3)}$ if $PI^{(0)}$ = [0  1  0  0]?

   (b) what is   lim    $pi_0{(n)}$ if $PI^{(0)}$ = [0.5  0.5  0  0]?
                n->inf

   assuming (la)tex notation for the mathematical expressions, e.g.,
   $pi_1^{(2)}$ = probability that system is in state 1 at time 2, while
   $PI^{(0)}$ = probability vector (of all system states) at time 0.

            ---------------------------------------
           /  0.1                                  |
          /                                        V
        ----  0.2     ----   0.4    ----   0.3    ----
       / 0 /-------->/ 1 /-------->/ 2 /-------->/ 3 /
       ----          ----          ----          ----
         ^            /              ^            /
         |___________/               |___________/
              0.6                        0.5