Network modeling program (all classes)

[lobisquit]

• Probability recap: see First lectures #4

• Markov chains see Asymptotic MC behaviour #1

  • markov property
  • homogeneus MC
  • Probability matrix (1 and n-step)

• Poisson's processes

  • definition -> law of rare events (no demonstration here, see KT p. 23) NOT MANDATORY
  • exponential inter-arrival time (<- cit recap)

• Particular poisson processes

  • M/G/1 as MC: tn as departure times
  • G/M/1 as MC: tn as arrival times

• First step analysis (<- Markov property) 582d24e

• Random walks (as particular MC) NOT MANDATORY 04eaa22

• Synchronization model 762a7d2

• First passage time theta_ij, f_ij(n) definitions 582d24e

• Asymptotic behaviour, see Asymptotic MC behaviour #1

  • regular MC

  • limiting distribution: proof of existence and uniqueness for regular finite MC

  • accessibility and communication between states: classes of states

  • period d(j) is a class property

  • sufficient and necessary condition for recurrent states (sum_n p_ii^(n) = + inf)

  • recurrence as a class property

  • basic limit theorem for MCs -> proof of existence and uniqueness of limiting distribution for aperiodic, irreducible, recurrent classes

  • Lemma 4.1: yet another sufficient and necessary condition for recurrent states

    ---

    see Completing MC asymptotic behaviour #6

  • guess on G/M/1 limiting distribution (c beta^k)

  • periodic MC definition -> limiting distribution of falling into a recurrent class from a transient state

  • Th. 3.1 (KT page 91)

  • Th. finite MC has at least one positive recurrent state and (Th.) no null recurrent states

  • Lemma 4.13 (Ross, 2nd edition, pages 78-82), irreducible MC has f_i0 = 1 for i!=0

  • Th. 4.14 (Ross, 2nd edition, pages 78-82), transient MC has non-zero bounded solution for Zj system

  • Th 4.2 (KT page 95): necessary condition on MC irreducible and aperiodic

    • recap table of all conditions above

  • M/G/1 is transient/recurrent conditions for rho > 1 1806861

• Poisson process reloaded

  • Lemma: sum of indipendent Poisson is Poisson
  • Law of rare events (demonstration) NOT MANDATORY
  • Poisson arrivals in [0, t] | number of arrivals in [0, t] are uniformly distributed in [0, t]
  • Th. Poisson arrivals in [0, u] | number of arrival in [0, t] are binomial distributed ~ bin(n, u/t) ~~> nice diagram intensity-time
  • M/G/inf

• BG 275: slotted multi-access

  • assumptions
  • drift analysis
  • aloha & slotted aloha: correct analysis for m finite and m -> inf
  • Pake's lemma: sufficient condition on drift for stable (positive recurrent) MCs
  • Kaplan's lemma: sufficient condition on drift for not stable (not positive recurrent) MCs
  • enhanced aloha: CSMA & CSMA/CD

• Renewal processes: see pull Renewal processes #9

  • Introduction. c5eae12
  • Renewal equation
  • Wald equation
  • Elementary renewal theorem
  • Key renewal theorem
  • Limiting distribution of the excess life
  • Delayed renewal processes
  • Theorem 3.6
  • Semi-Markov process

• Go-Back-N

  • Lecture 03-05-2017 3f5fd0e
  • Lecture 04-05-2017 9c1d200
  • Lecture 09-05-2017 b1cd48d
  • Lecture 10-05-2017 90b942f
  • Lecture 16-05-2017 3f5fd0e
  • Lecture 18-05-2017 2540f6c
  • Lecture 19-05-2017 2540f6c
  • Lecture 25-05-2017 NOT MANDATORY 60fe751
  • Lecture 26-05-2017 NOT MANDATORY 0dcce03

• sensor networks NOT MANDATORY 777fffd