Posts from the ‘Intro to Stochastic Processes’ Category

Probability Theory: Homework 2

Exercises, due Wed Sept 17.

Jacod and Protter: 4.1, 5.20 and 7.11

4.1 (Poisson Approximation to the Binomial) Let $P$ be a Binomial probability with probability of success $p$ and the number of trials $n$. Let $\lambda = pn$. Show that

$\displaystyle P(k \text{ successes}) = \frac{\lambda^k}{k!} \left(1 - \frac{\lambda}{n}\right)^n \left[\left(\frac{n}{n}\right) \left(\frac{n-1}{n} \right) \cdots \left(\frac{n - k + 1}{n}\right) \right] \left(1 - \frac{\lambda}{n}\right)^{-k}.$

Let $n \to \infty$ and let $p$ change so that $\lambda$ remains constant. Conclude that for small $p$ and large $n$,

$\displaystyle P(k \text{ successes}) \approx \frac{\lambda^k}{k!} e^{-\lambda}$, where $\lambda = pn$.

5.20 Suppose that $X$ takes its values in $\mathbb{N} = \{0, 1, 2, \ldots \}$. Show that

$\displaystyle E[X] = \sum_{n=0}^\infty P(X > n)$.

7.11 Let $\displaystyle P(A) = \int_{-\infty}^\infty 1_A(x) f(x) dx$ for a nonnegative function $f$ with $\displaystyle \int_{-\infty}^\infty f(x) dx = 1$. Let $A = \{x_0\}$, a singleton. Show that $A$ is a Borel set and also a null set (that is, $P(A) = 0$).

Stochastics: Code for Martingales

Code for branching processes: branching_proc.R

Code for the Polya urn scheme: polya.R

Stochastics: HW 7, due Wed Apr 23

1. The Autocovariance problem posted last week..

2. Consider the random variable

$\displaystyle X := \left\{ \begin{matrix} 5 & \text{wp } 1/2 \\ 2 & \text{wp } 1/3 \\ 1 & \text{wp } 1/6 \end{matrix} \right.$

and let $A$ be the event that $X = 2$ or $X = 5$.

• Compute $\mathbb{E}[X \, | \, A]$.
• Compute $\mathbb{E}[X 1_{A}]$.
• Let $Y$ be distributed like $X$ and let $Z := X + Y$.  Compute $\mathbb{E}[Z \, | \, A]$.
• Compute $\mathbb{E}[Z \, | \, X]$.

3. Let $\{X_1, \, X_2, \, \ldots\}$ be a sequence of iid random variables and let $\mathcal{F}_n = \sigma(X_1, X_2, \ldots, X_n)$.  Let $m(s) = \mathbb{E}[e^{sX_1}]$ be the moment generating function of $X_1$ (and hence of each $X_i$).  Fix $s$ and assume $m(s) < \infty$.  Let $S_0 = 0$ and for $n > 0$,

$S_n = X_1 + X_2 + \ldots + X_n$.

Define $M_n = m(s)^{-n} e^{s S_n}$. Show that $M_n$ is a martingale with respect to $\mathcal{F}_n$.

Stochastics: HW 6, due Wed April 16

Durrett 3.8 Counter processes. Suppose that arrivals at a counter come at times of a Poisson process with rate $\lambda$.  An arriving particle that finds the counter free gets registered and then locks the counter for an amount of time $\tau$. Particles that arrive while the counter is locked are not counted and have no effect. (a) Find the limiting probability that the counter is locked at time $t$.  (b) Compute the limiting fraction of particles that get registered.

Durrett 3.21 The city of Ithaca, NY, allows for two-hour parking in all downtown spaces.  Methodical parking officials patrol the downtown area, passing the same point every 2h.  When an official encounters a car, he marks it with chalk.  If the car is still there 2h later, a ticket is written.  Suppose that you park your car for a random amount of time that is distributed uniformly over $(0,4)$ hours.  What is the probability you will get a ticket?

Durrett 4.2 A small computer store has room to display up to three computers for sale. Customers come at times of a Poisson arrival process at a rate of 2 per week. If a customer arrives and a computer is available, the customer will buy it. When the store has only one computer left they place an order for two more computers.  The order takes an exponentially distributed amount of time to be completed, with a rate of 1 per week. Of course, while the store is waiting for delivery, sales may reduce inventory from 1 to 0.  (a) Write a matrix for the transition rates $Q_{ij}$ and solve $\pi Q = 0$ to find the stationary distribution. (b) At what rate does the store makes sales?

Durrett 4.9 A hemoglobin molecule can carry one oxygen or one carbon monoxide molecule.  Suppose that the two types of gases arrive at rates 1 and 2 and attach for an exponential amount of time with rates 3 and 4, respectively.  Formulate a Markov chain model with state space $\{+ 0 -\}$ where $+$ denotes an attached oxygen molecule, $-$ denotes an attached carbon monoxide molecule, and 0 a free hemoglobin molecule.  Find the long-run fraction of time the hemoglobin molecule is in each of its three states.

Autocorrelation of a Stochastic Process (DUE WED APR 23)

Consider a sequence of random variables $\{X_n\}_{n \geq 0}$ that take the values 5 and 1 with asymptotic frequencies $\frac{2}{3}$ and $\frac{1}{3}$ respectively.  We will consider some stochastic processes that produce such sequences and compute the one-step autocorrelation of these sequences.

The autocovariance function of a sequence is defined to be

$\displaystyle \rho(i,j) = Cov(X_i, X_j)$

where

$\displaystyle Cov(X,Y) = E(XY) - E(X) E(Y)$

1. iid model. Suppose that the sequence is iid with $P(X_n = 1) = 1/3$ and $P(X_n = 5) = 2/3$.  Compute $\rho(n, n + 1)$ for $n \geq 0$.
2. Deterministic switching. Consider the sequence $\{X_n\} = (1,5,5,1,5,5,1,5,5,1 \ldots)$.  Compute the “empirical” autocovariance function
$\displaystyle \hat \rho(1) = \lim_{N \to \infty} \frac{1}{N} \sum_{n=0}^{N-1} X_n X_{n+1} - \left(\frac{1}{N} \sum_{n=0}^{N-1} X_n\right) \left(\frac{1}{N} \sum_{n=1}^N X_n \right)$
3. Markov chain model. Suppose that $\{X_n\}_{n \geq 0}$ is a Markov chain that takes the values 1 and 5 whose transition probabilities are given by the transition matrix
$\displaystyle P = \begin{pmatrix} 0.1 & 0.9 \\ p & (1 - p) \end{pmatrix}$.

• For what value of $p$ will $\{X_n\}$ satisfy the asymptotic frequencies given above?
• Compute the one-step autocovariance function for this process assuming that the initial condition is drawn from the stationary distribution.

Stochastics: HW 5, due Wed April 2

This week’s problems are all directly from Durrett:

Chapter 2, #32, 33, 52, 58

Hint:  For the chicken crossing the road problem, you may find Theorem 2.10 useful.

UPDATE: It has been brought to my attention that the version of the textbook online has different numbers and one problem is missing altogether.  If you are working from the web version, the problem numbers are:

Chapter 2, #33, 34 (chicken crossing the road), 48 (preventative maintenance) and the following,

#58 For a Poisson process $N(t)$ with arrival rate 2, compute: (a) $\mathbb{P}(N(2) = 5)$, (b) $\mathbb{P}(N(5) = 8 \, | \, N(2) = 3$, and (c) $\mathbb{P}(N(2) = 3 \, | \, N(5) = 8)$.

UPDATE:

HW 5 Solutions (pdf)

Stochastics: Some suggested theoretical exercises

These exercises are not required, but they are recommended for graduate students and others enrolled in the 5000-level of this class.

Theoretical Exercises (pdf)

Stochastics: Suggested Problems for Chapter 2

Practice with exponential random variables
2.1 – 2.3, 2.32

Comparison of multiple exponentially distributed random events
2.7, 2.8

Queueing Theory
2.9, 2.10

The Poisson Process
2.22, 2.23, 2.25, 2.27, 2.33

Stochastics: Take home test problem, due Thursday at 5pm in LIT 460

We shuffle a deck by the following method:

Take the top card off the top of the deck and place back into the deck in a position chosen uniformly at random.

It is allowable that the top card will be put directly on top again.

Let $Z_n$ denote the position of the Queen of Hearts at time $n$.  We assume that the Queen of Hearts starts on top, i.e. $Z_0 = 1$, and wish to compute the expected time for it to return to the top.

The probability transition matrix when there are a total of FIVE cards is:

$\displaystyle P = \begin{pmatrix} \frac15 & \frac15 & \frac15 & \frac 15 & \frac15 \\ \frac45 & \frac15 & 0 & 0 & 0 \\ 0& \frac35 & \frac25 & 0 & 0 \\ 0 & 0 & \frac25 & \frac35 & 0 \\ & 0 & 0 & \frac15 & \frac45 \end{pmatrix}$

What is the expected time until the shuffler sees the Queen of Hearts on top of the deck when there are 52 cards?

You may use the book, but you may not communicate with other students on this problem.  Work smart!  The solution does not require solving a 52-dimensional system of equations. (Hint: It may help to solve the 5-card case first and then attack the larger problem.)

Stochastics: HW 4 Solutions

HW 4 (pdf)

HW4 Solutions (pdf)

In these solutions I reference the use of Wolfram Alpha, (special section on matrix functions here).