Example 1: Three cards: one red on both sides, one black on both sides, one black on one side, red on the other. Shuffle, pick card at random. Side up is Black. What is the probability the side down is Black?
Solution: To do this carefully, enumerate sample space, , of all possible outcomes. Six sides to the three cards. Label three red sides 1, 2, 3 with sides 1, 2 on the all red card (card # 1). Label three black sides 4, 5, 6 with 3, 4 on opposite sides of mixed card (card #2). Define some events:
|side shows face up|
|side showing is black|
|card is chosen|
One representation . Then , , and so on.
Modelling: assumptions about some probabilities; deduce probabilities of other events. In example simplest model is
Apply two rules:
Definition of conditional probability:
Example 2: Monte Hall, Let's Make a Deal. Monte shows you 3 doors. Prize hidden behind one. You pick a door. Monte opens a door you didn't pick; shows you no prize; offers to let you switch to the third door. Do you switch?
Sample space: typical element is where is number of door with prize, is number of your first pick and is door Monte opens with no prize.
Model? Traditionally we define events like
|Prize behind door|
|You choose door|
The event , that you lose if you switch is
So the event you win by switching has probability 2/3 and you should switch.
Usual phrasing of problem. You pick 1, Monte shows 3. Should you take 2? Let be rv door Monte shows you. Question:
Modelling assumptions do not determine this; it depends on Monte's method for choosing door to show when he has a choice. Two simple cases:
Use Bayes' rule:
For case 1 we get
Notice that in case 2 if we pick door 1 and Monte shows us door 2 we should definitely switch. Notice also that it would be normal to assume that Monte used the case 1 algorithm to pick the door to show when he has a choice; otherwise he is giving the contestant information. If the contestant knows Monte is using algorithm 2 then by switching if door 2 is shown and not if door 3 is shown he wins 2/3 of the time which is as good as the always switch strategy.
Example 3: Survival of family names. Traditionally: family name follows sons. Given man at end of 20th century. Probability descendant (male) with same last name alive at end of 21st century? or end of 30th century?
Simplified model: count generations not years. Compute probability, of survival of name for generations.
Technically easier to compute , probability of extinction by generation .
|child s line extinct|
Geometric Distribution: Assume
Example 3: Mean values
= total number of sons in generation .
Recall definition of expected value:
If is discrete then
If is absolutely continuous then
Theorem: If , has density then
Key properties of :
1: If then . Equals iff .
3: If then
If , , two discrete random variables then
Extension to absolutely continuous case:
Joint pmf of and is defined as
The marginal density of is, for .
For not in the integral is 0 so
If and have joint density then we define the conditional density of given by analogy with our interpretation of densities. We take limits:
Going back to our interpretation of joint densities and ordinary densities we see that our definition is just
Example: For of previous example conditional density of given defined only for :
WARNING: in sum is required and , integers so sum really runs from to
If and are continuous random variables with joint density we define:
Key properties of conditional expectation
1: If then . Equals iff .
3: If and are independent then
Computing expectations by conditioning:
Notation: is the function of you get by working out , getting a formula in and replacing by . This makes a random variable.
2: If and are independent then
4: (compute average holding fixed first, then average over ).
For expect exponential decay. For exponential growth (if not extinction).
We have reviewed the following definitions:
Tactics for expected values:
Last names example has following structure: if, at generation there are individuals then number of sons in next generation has distribution of sum of independent copies of the random variable which is number of sons I have. This distribution does not depend on , only on value of . Call a Markov Chain.
Ingredients of a Markov Chain:
The stochastic process is called a Markov chain if
The matrix is called a transition matrix.
Example: If in the last names example has a Poisson distribution then given , is like sum of independent Poisson rvs which has a Poisson() distribution. So
Example: Weather: each day is dry (D) or wet (W).
is weather on day n.
Suppose dry days tend to be followed by dry days, say 3 times in 5 and wet days by wet 4 times in 5.
Markov assumption: yesterday's weather irrelevant to prediction of tomorrow's given today's.
Now suppose it's wet today. P(wet in 2 days)?
General case. Define
Proof of these assertions by induction on .
Example for . Two bits to do:
First suppose are discrete variables. Assume
Proof of claim:
Second step: consider
More general version
Summary: A Markov Chain has stationary step transition probabilities which are the th power of the 1 step transition probabilities.
Here is Maple output for the 1,2,4,8 and 16 step transition matrices for our rainfall example:
> p:= matrix(2,2,[[3/5,2/5],[1/5,4/5]]); [3/5 2/5] p := [ ] [1/5 4/5] > p2:=evalm(p*p): > p4:=evalm(p2*p2): > p8:=evalm(p4*p4): > p16:=evalm(p8*p8):This computes the powers ( evalm understands matrix algebra).
> evalf(evalm(p)); [.6000000000 .4000000000] [ ] [.2000000000 .8000000000] > evalf(evalm(p2)); [.4400000000 .5600000000] [ ] [.2800000000 .7200000000] > evalf(evalm(p4)); [.3504000000 .6496000000] [ ] [.3248000000 .6752000000] > evalf(evalm(p8)); [.3337702400 .6662297600] [ ] [.3331148800 .6668851200] > evalf(evalm(p16)); [.3333336197 .6666663803] [ ] [.3333331902 .6666668098]Where did and come from?
Suppose we toss a coin and start the chain with Dry if we get heads and Wet if we get tails.
A probability vector is called an initial distribution for the chain if
A Markov Chain is stationary if
An initial distribution is called stationary if the chain is stationary. We find that is a stationary initial distribution if
Suppose converges to some matrix . Notice that
This proves that each row of satisfies
Def'n: A row vector is a left eigenvector of with eigenvalue if
So each row of is a left eigenvector of with eigenvalue .
Finding stationary initial distributions. Consider the for the weather example. The equation
p:=matrix([[0,1/3,0,2/3],[1/3,0,2/3,0], [0,2/3,0,1/3],[2/3,0,1/3,0]]); [ 0 1/3 0 2/3] [ ] [1/3 0 2/3 0 ] p := [ ] [ 0 2/3 0 1/3] [ ] [2/3 0 1/3 0 ] > p2:=evalm(p*p); [5/9 0 4/9 0 ] [ ] [ 0 5/9 0 4/9] p2:= [ ] [4/9 0 5/9 0 ] [ ] [ 0 4/9 0 5/9] > p4:=evalm(p2*p2): > p8:=evalm(p4*p4): > p16:=evalm(p8*p8): > p17:=evalm(p8*p8*p):
> evalf(evalm(p16)); [.5000000116 , 0 , .4999999884 , 0] [ ] [0 , .5000000116 , 0 , .4999999884] [ ] [.4999999884 , 0 , .5000000116 , 0] [ ] [0 , .4999999884 , 0 , .5000000116] > evalf(evalm(p17)); [0 , .4999999961 , 0 , .5000000039] [ ] [.4999999961 , 0 , .5000000039 , 0] [ ] [0 , .5000000039 , 0 , .4999999961] [ ] [.5000000039 , 0 , .4999999961 , 0] > evalf(evalm((p16+p17)/2)); [.2500, .2500, .2500, .2500] [ ] [.2500, .2500, .2500, .2500] [ ] [.2500, .2500, .2500, .2500] [ ] [.2500, .2500, .2500, .2500]doesn't converges but does. Next example:
Pick in ; put .
> p:=matrix([[2/5,3/5,0,0],[1/5,4/5,0,0], [0,0,2/5,3/5],[0,0,1/5,4/5]]); [2/5 3/5 0 0 ] [ ] [1/5 4/5 0 0 ] p := [ ] [ 0 0 2/5 3/5] [ ] [ 0 0 1/5 4/5] > p2:=evalm(p*p): > p4:=evalm(p2*p2): > p8:=evalm(p4*p4):
> evalf(evalm(p8*p8)); [.2500000000 , .7500000000 , 0 , 0] [ ] [.2500000000 , .7500000000 , 0 , 0] [ ] [0 , 0 , .2500000000 , .7500000000] [ ] [0 , 0 , .2500000000 , .7500000000]Notice that rows converge but to two different vectors:
> p:=matrix([[2/5,3/5,0],[1/5,4/5,0], [1/2,0,1/2]]); [2/5 3/5 0 ] [ ] p := [1/5 4/5 0 ] [ ] [1/2 0 1/2] > p2:=evalm(p*p): > p4:=evalm(p2*p2): > p8:=evalm(p4*p4): > evalf(evalm(p8*p8)); [.2500000000 .7500000000 0 ] [ ] [.2500000000 .7500000000 0 ] [ ] [.2500152588 .7499694824 .00001525878906]
Basic distinguishing features: pattern of 0s in matrix .
State leads to state if for some . It is convenient to agree that the identity matrix; thus leads to .
Note leads to and leads to implies leads to (Chapman-Kolmogorov).
States and communicate if leads to and leads to .
The relation of communication is an equivalence relation; it is reflexive, symmetric and transitive: if and communicate and and communicate then and communicate.
Example ( signs indicate non-zero entries):
For this example:
, , so are all in the same communicating class.
but not vice versa.
but not vice versa.
So the communicating classes are
A Markov Chain is irreducible if there is only one communicating class.
State is recurrent if , otherwise transient.
If then Markov property (chain starts over when it gets back to ) means prob return infinitely many times (given started in or given ever get to ) is 1.
Consider chain started from transient . Let be number of visits to state (including visit at time 0). To return times must return once then starting over return times, then never return. So:
has a Geometric distribution and .
For last example: and are transient. Claim: states 1, 2 and 3 are recurrent.
Proof: argument above shows each transient state is visited only finitely many times. So: there is a recurrent state. (Note use of finite number of states.) It must be one of 1, 2 and 3. Proposition: If one state in a communicating class is recurrent then all states in the communicating class are recurrent.
Proof: Let be the known recurrent state so
Proposition also means that if 1 state in a class is transient so are all.
State has period if is greatest common divisor of
A chain is aperiodic if all its states are aperiodic.
Example: consider a sequence of independent coin tosses with probability of Heads on a single toss. Let be number of heads minus number of tails after tosses. Put .
is a Markov Chain. State space is , the integers and
This chain has one communicating class (for ) and all states have period 2. According to the strong law of large numbers converges to . If this guarantees that for all large enough , that is, the number of returns to 0 is not infinite. The state 0 is then transient and so all states must be transient.
For the situation is different. It is a fact that
Local Central Limit Theorem (normal approximation to ) (or Stirling's approximation) shows
Start irreducible recurrent chain in state . Let be first such that . Define
Notice stationary initial distribution is
Heuristic: start chain in . Expect to return to every time units. So are in state about once every time units; i.e. limiting fraction of time in state is .
Conclusion: for an irreducible recurrent finite state space Markov chain
Previous conclusion is still right if there is a stationary initial distribution.
Example: HeadsTails after tosses of fair coin. Equations are
You have to go through 1 to get to 0 from 2 so
Symmetry (switching H and T):
The transition probabilities are homogeneous:
Summary of the situation:
Every state is recurrent.
All the expected hitting times are infinite.
All entries converge to 0.
Jargon: The states in this chain are null recurrent.
Page 229, question 21: runner goes from front or back door, prob 1/2 each. Returns front or back, prob 1/2 each. Has pairs of shoes, wears pair if any at departure door, leaves at return door. No shoes? Barefoot. Long run fraction of time barefoot?
Solution: Let be number of shoes at front door on day . Then is a Markov Chain.
pairs at front door on day . is if goes out back door (prob is 1/2) or out front door and back in front door (prob is 1/4). Otherwise is .
pairs at front door on day . is if out back, in front (prob is 1/4). is if out front, in back. Otherwise is .
0 pairs at front door on day . is 0 if out front door (prob 1/2) or out back door and in back door (prob 1/4) otherwise is .
Transition matrix :
Doubly stochastic: row sums and column sums are 1.
So for all is stationary initial distribution.
Solution to problem: 1 day in no shoes at front door. Half of those go barefoot. Also 1 day in all shoes at front door; go barefoot half of these days. Overall go barefoot of the time.
Insurance company's reserves fluctuate: sometimes up, sometimes down. Ruin is event they hit 0 (company goes bankrupt). General problem. For given model of fluctuation compute probability of ruin either eventually or in next time units.
Simplest model: gambling on Red at Casino. Bet $1 at a time. Win $1 with probability , lose $1 with probability . Start with dollars. Quit playing when down to $0 or up to . Compute
= fortune after plays. .
Middle equation is
For we get
Notice that if our formulas for the sum of the geometric series are wrong. But for we get
For or and or 4:
For first step analysis:
In matrix form
Translate to matrix notation:
Particles arriving over time at a particle detector. Several ways to describe most common model.
Approach 1: numbers of particles arriving in an interval has Poisson distribution, mean proportional to length of interval, numbers in several non-overlapping intervals independent.
For , denote number of arrivals in by . Model is
Let be the times at which the particles arrive.
Let with by convention.
Then are independent Exponential random variables with mean .
Note is called survival function of .
Approaches are equivalent. Both are deductions of a model based on local behaviour of process.
Approach 3: Assume:
All 3 approaches are equivalent. I show: 3 implies 1, 1 implies 2 and 2 implies 3. First explain , .
Notation: given functions and we write
[Aside: if there is a constant such that
Model 3 implies 1: Fix , define to be conditional probability of 0 points in given value of process on .
Derive differential equation for . Given process on and 0 points in probability of no points in is
Notice: survival function of exponential rv..
General case. Notation: .
is a non-decreasing function of . Let
Given probability that is conditional probability of points in .
So, for :
is increasing so only consider .
With we get
Similar ideas permit proof of
If is a Poisson Process we define to be the times between 0 and the first point, the first point and the second and so on.
Fact: are iid exponential rvs with mean .
We already did rigorously. The event is exactly the event . So
I do case of . Let be two positive numbers and , . Consider event
This is almost the same as the intersection of the four events:
First step: Compute
Second step: write this in terms of joint cdf of . I do :
Differentiate twice, that is, take
That completes the first part.
Now compute the joint cdf of by
Summary so far:
Instantaneous rates model implies independent Poisson increments model implies independent exponential interarrivals.
Next: show independent exponential interarrivals implies the instantaneous rates model.
Suppose iid exponential rvs with means . Define by if and only if
Let be the event . We are to show
If is a possible trajectory consistent with then has jumps at points
So given with we are essentially being given
The computation of
Convolution: If and independent rvs with densities and respectively and then
If iid Exponential then has a Gamma distribution. Density of is
Extreme Values: If are independent exponential rvs with means then has an exponential distribution with mean
Memoryless Property: conditional distribution of given is exponential if has an exponential distribution.
The hazard rate, or instantaneous failure rate for a positive random variable with density and cdf is
Weibull random variables have density
Indications of some proofs:
1) independent Poisson processes rates , . Let be the event of 2 or more points in in the time interval , , the event of exactly one point in in the time interval .
Let and be the corresponding events for .
Let denote the history of the processes up to time ; we condition on .
We are given:
Next let be the event of no points in in the time interval and the same for . Then
2) The infinitesimal approach used for 1 can do part of this. See text for rest. Events defined as in 1): The event that there is one point in in is the event, that there is exactly one point in any of the processes together with a subset of where there are two or more points in in but exactly one is labeled . Since
Similarly, is a subset of so
3) Fix . Let be the number of points in . Given the conditional distribution of is Binomial with . So
4): Fix for such that
Divide by and let all go to 0 to get joint density of is
5) Replace the event with . With as before we want
We are left to compute the limit of
The idea of hazard rate can be used to extend the notion of Poisson Process. Suppose is a function of . Suppose is a counting process such that
Jargon: is the intensity or instaneous intensity and the cumulative intensity.
Can use the model with any non-decreasing right continuous function, possibly without a derivative. This allows ties.
Imagine insurance claims arise at times of a Poisson process, , (more likely for an inhomogeneous process).
Let be the value of the th claim associated with the point whose time is .
Assume that the 's are independent of each other and of .
Consider a population of single celled organisms in a stable environment.
Fix short time interval, length .
Each organism has some probability of dividing to produce two organisms and some other probability of dying.
We might suppose:
Constants of proportionality do not depend on time: ``stable environment''.
Constants do not depend on organism: organisms are all similar and live in similar environments.
: total population at time .
: history of process up to time .
Condition on event .
Probability of two or more divisions (more than one division by a single organism or two or more organisms dividing) is .
Probability of both a division and a death or of two or more deaths is .
So probability of exactly 1 division by any one of the organisms is .
Similarly probability of 1 death is .
These equations lead to:
This is the Markov Property.
Definition:A process taking values in , a finite or countable state space is a Markov Chain if
Definition:A Markov chain has stationary transitions if
From now on: our chains have stationary transitions.
Suppose a Markov Chain with stationary transitions. Then
Now consider the chain starting from and let be the first for which . Then is a stopping time.
Conclusion: given , has memoryless property so has an exponential distribution. Let be the rate parameter.
Let be the stopping times at which transitions occur. Then . The sequence is a Markov chain by the Markov property. That reflects the fact that by design.
As before we say if for some . It is fairly clear that for the if and only if for the embedded chain .
We say ( and communicate) if and .
The Chapman-Kolmogorov equations are
The Chapman-Kolmogorov equations can also be written
Look at these equations in component form:
Let be the matrix with entries
is the infinitesimal generator of the chain.
On the other hand
Remark: When the state space is infinite the forward equations may not be justified. In deriving them we interchanged a limit with an infinite sum; the interchange is always justified for the backward equations but not for forward.
Example: . Then
Add first plus third backward equations to get
Notice: rows of are a stationary initial distribution. If rows are then
Fact: is long run fraction of time in state 0.
Consider a population of individuals. Suppose in next time interval probability of population increase of 1 (called a birth) is and probability of decrease of 1 (death) is .
Jargon: is a birth and death process.
All ; called a pure birth process.
All (0 is absorbing): pure death process.
and is a linear birth and death process.
, : Poisson Process.
and is a linear birth and death process with immigration.
Ingredients of Queuing Problem:
1: Queue input process.
2: Number of servers
3: Queue discipline: first come first serve? last in first out? pre-emptive priorities?
4: Service time distribution.
Example: Imagine customers arriving at a facility at times of a Poisson Process with rate . This is the input process, denoted (for Markov) in queuing literature.
Single server case:
Service distribution: exponential service times, rate .
Queue discipline: first come first serve.
= number of customers in line at time .
is a Markov process called queue:
Customers arrive according to PP rate . Each customer begins service immediately. is number being served at time . is a birth and death process with
We have seen that a stationary initial distribution is a probability vector solving
So equation says:
Rate of departure from balances rate of arrival to . This is called balance.
Application to birth and death processes:
Apply to get
For fair random walk = number of heads minus number of tails,
We now turn these pictures into a stochastic process:
For we define
Another observation: is independent of because the two rvs involve sums of different .
As the processes converge to a process with the properties:
Definition:Any process satisfying 1-4 above is a Brownian motion.
Suppose . Then is a sum of two independent normal variables. Do following calculation:
, and independent. .
Compute conditional distribution of given :
Coefficient of :
Coefficient of :
Finally you should check that
Conclusion: given the conditional distribution of is with and as above.
Application to Brownian motion:
Tossing a fair coin:
|HTHHHTHTHHTHHHTTHTH||5 more heads than tails|
|THTTTHTHTTHTTTHHTHT||5 more tails than heads|
Both sequences have the same probability.
So: for random walk starting at stopping time:
Any sequence with more heads than tails in next tosses is matched to sequence with more tails than heads. Both sequences have same prob.
Suppose is a fair () random walk. Define
Compute ? Trick: Compute
First: if then
Second: if then
Fix . Consider a sequence of H's and T's which leads to say and .
Switch the results of tosses to to get a sequence of H's and T's which has and . This proves
This is true for each so
Finally, sum over all to get
Make the substitution in the second sum to get
Brownian motion version:
Any path with and is matched to an equally likely path with and .
Let to get
On the other hand in view of
NOTE: the preceding is a density when viewed as a function of the variable .
A stochastic process indexed by either a discrete or continuous time parameter is a martingale if:
Note: Brownian motion with drift is a process of the form
Some evidence for some of the above:
Random walk: iid with
treated as constant given .
Knowing is equivalent to knowing .
For we have independent of so conditional expectation is unconditional expectation.
Since Standard Brownian Motion is limit of such random walks we get martingale property for standard Brownian motion.
Poisson Process: . Fix .
Things to notice:
I used independent increments.
is shorthand for the conditioning event.
Similar to random walk calculation.
We model the price of a stock as
If annual interest rates are we call the instantaneous interest rate; if we invest $1 at time 0 then at time we would have . In this sense an amount of money to be paid at time is worth only at time 0 (because that much money at time 0 will grow to by time ).
Present Value: If the stock price at time is per share then the present value of 1 share to be delivered at time is
Now we compute
Note: is ; the expected value needed is the moment generating function of this variable at .
Suppose . The Moment Generating Function of is
If this identity is satisfied then the present value of the stock price is a martingale.
Suppose you can pay $ today for the right to pay for a share of this stock at time (regardless of the actual price at time ).
If, at time , you will exercise your option and buy the share making dollars.
If you will not exercise your option; it becomes worthless.
The present value of this option is
In a fair market:
The other integral needed is
Introduce the notation
This is the Black-Scholes option pricing formula.
Monte Carlo computation of expected value:
To compute : do experiment times to generate independent observations all with same distribution as .
To estimate : use same and compute
In practice: random quantities are not used.
Use: pseudo-random uniform random numbers.
They ``behave like'' iid Uniform(0,1) variables.
Many, many generators. One standard kind: linear congruential generators.
Start with an integer in range . Compute
Integers and are chosen so that
We now pretend we can generate which are iid Uniform(0,1).
Monte Carlo methods for generating a sample:
Fact: continuous CDF and satisfy
Proof: For simplicity: assume strictly increasing on inverval with and .
If Uniform(0,1) then
Conversely: if and then there is a unique such that
Application: generate and solve for to get which has cdf .
Example:For the exponential distribution
Observation: so also has an Exponential() distribution.
Example:: for the standard normal cdf solving
Special purpose transformations:
Example:: If and are iid define and by
NOTE: Book says
Compute joint cdf of at .
Moreover has cdf
So: generate iid Uniform(0,1).
You have generated two independent variables.
If difficult to solve (eg hard to compute) sometimes use acceptance rejection.
Goal: generate where .
Tactic: find density and constant such that
Most important fact: :
Proof: this is like the old craps example:
Condition on to get
Example:Half normal distribution: has density
Use . To find maximize
Choose to minimize (or ); get so
Algorithm is then: generate and then compute
To generate : use a third to pick a sign at random: negative if otherwise positive.
The inverse transformation method works for discrete distributions.
has possible values with probabilities compute cumulative probabilities
Find such that