Introduction to Stochastic Processes - Lecture Notes

1 Introduction to Stochastic Processes - Lecture Notes (with 33 illustrations)Gordan itkovi Department of MathematicsThe University of Texas at AustinContents1 Probability Random variables .. Countable sets .. Discrete random variables .. Expectation .. Events and probability .. Dependence and independence .. Conditional probability .. Examples .. 122 Mathematica in 15 Basic Syntax .. Numerical Approximation .. Expression Manipulation .. Lists and Functions .. Linear Algebra .. Predefined Constants .. Calculus .. Solving Equations .. Graphics .. Probability Distributions and Simulation.

2 Help Commands .. Common Mistakes .. 253 Stochastic The canonical probability space .. Constructing the Random Walk .. Simulation .. Random number generation .. Simulation of Random Variables .. Monte Carlo Integration .. 334 The Simple Random Construction .. The maximum .. 361 CONTENTS5 Generating Definition and first properties .. Convolution and moments .. Random sums and Wald s identity .. 446 Random walks - advanced Stopping times .. Wald s identity II .. The distribution of the first hitting timeT1.. A recursive formula .. Generating-function approach.

3 Do we actually hit1sooner or later? .. Expected time until we hit1? .. 557 Branching A bit of history .. A mathematical model .. Construction and simulation of branching Processes .. A generating-function approach .. Extinction probability .. 618 Markov The Markov property .. Examples .. Chapman-Kolmogorov relations .. 709 The Stochastics Installation .. Building Chains .. Getting information about a chain .. Simulation .. Plots .. Examples .. 7710 Classification of The Communication Relation .. Classes .. Transience and recurrence .. Examples .. 8411 More on Transience and A criterion for recurrence.

4 Class properties .. A canonical decomposition .. 89 Last Updated: December 24, 20102 Intro to Stochastic Processes : Lecture NotesCONTENTS12 Absorption and Absorption .. Expected reward .. 9513 Stationary and Limiting Stationary and limiting distributions .. Limiting distributions .. 10414 Solved Probability review .. Random Walks .. Generating functions .. Random walks - advanced methods .. Branching Processes .. Markov chains - classification of states .. Markov chains - absorption and reward .. Markov chains - stationary and limiting distributions .. Markov chains - various multiple-choice problems.

5 156 Last Updated: December 24, 20103 Intro to Stochastic Processes : Lecture NotesChapter 1 Probability reviewThe probable is what usually happens. AristotleIt is a truth very certain that when it is not in our power to determine. what istrue we ought to follow what is most probable Descartes - Discourse on Method It is remarkable that a science which began with the consideration of games ofchance should have become the most important object of human knowledge. Pierre Simon Laplace - Th orie Analytique des Probabilit s, 1812 Anyone who considers arithmetic methods of producing random digits is, ofcourse, in a state of sin. John von Neumann - quote in Conic Sections by D.

6 MacHaleI say unto you: a man must have chaos yet within him to be able to give birth toa dancing star: I say unto you: ye have chaos yet within you .. Friedrich Nietzsche - Thus Spake Zarathustra Random variablesProbability is about random variables. Instead of giving a precise definition, let us just metion thatarandom variablecan be thought of as an uncertain, numerical ( , with values inR) it is true that we do not know with certainty what value a random variableXwill take, weusually know how to compute the probability that its value will be in some some subset ofR. Forexample, we might be interested inP[X 7],P[X [2, ]]orP[X {1,2,3}].

7 The collection ofall such probabilities is called thedistributionofX. One has to be very careful not to confusethe random variable itself and its distribution. This point is particularly important when severalrandom variables appear at the same time. When two random variablesXandYhave the samedistribution, , whenP[X A] =P[Y A]for any setA, we say thatXandYareequallydistributedand writeX(d)= 1. PROBABILITY Countable setsAlmost all random variables in this course will take only countably many values, so it is probablya good idea to review breifly what the wordcountablemeans. As you might know, the countableinfinity is one of many different infinities we encounter in mathematics.

8 Simply, a set is countableif it has the same number of elements as the setN={1,2,..}of natural numbers. Moreprecisely, we say that a setAiscountableif there exists a functionf:N Awhich is bijective(one-to-one and onto). You can thinkfas the correspondence that proves that there exactly asmany elements ofAas there are elements ofN. Alternatively, you can viewfas anorderingofA; it arrangesAinto a particular orderA={a1,a2,..}, wherea1=f(1),a2=f(2), are funny, however, as the following example showsExample is countable; just usef(n) = {0,1,2,3,..}is countable; usef(n) =n 1. You can see here why I think thatinfinities are funny; the setN0and the setN- which is its proper subset - have the {.}

9 , 2, 1,0,1,2,3,..}is countable; now the functionfis a bit more complicated;f(k) ={2k+ 1, k 0 2k, k < could think thatZis more than twice-as-large asN, but it is not. It is the same It gets even weirder. The setN N={(m,n) :m N,n N}of all pairs of naturalnumbers is also countable. I leave it to you to construct the A similar argument shows that the setQof all rational numbers (fractions) is also The set[0,1]of all real numbers between0and1isnotcountable; this fact was first provenby Georg Cantor who used a neat trick called thediagonal Discrete random variablesA random variable is said to be discrete if it takes at most countably many values.

10 More precisely,Xis said to bediscreteif there exists afiniteorcountablesetS Rsuch thatP[X S] = 1, , if we know with certainty that the only valuesXcan take are those inS. The smallest setSwith that property is called thesupportofX. If we want to stress that the support correspondsto the random variableX, we supports appear more often then the others:1. IfXtakes only the values1,2,3,.., we say If we allow0(in addition toN), so thatP[X N0] = 1, we say thatXisN0-valuedLast Updated: December 24, 20105 Intro to Stochastic Processes : Lecture NotesCHAPTER 1. PROBABILITY REVIEW3. Sometimes, it is convenient to allow discrete random variables to take the value+.