Esercizi di Processi Stocastici

One hundred solved exercises for the subject: stochastic processes

Exercise 1: Harvard, Dartmouth, and Yale admissions

In the Dark Ages, Harvard, Dartmouth, and Yale admitted only male students. Assume that, at that time, 80 percent of the sons of Harvard men went to Harvard and the rest went to Yale. 40 percent of the sons of Yale men went to Yale, and the rest split evenly between Harvard and Dartmouth; and of the sons of Dartmouth men, 70 percent went to Dartmouth, 20 percent to Harvard, and 10 percent to Yale.

Questions

(i) Find the probability that the grandson of a man from Harvard went to Harvard.

(ii) Modify the above by assuming that the son of a Harvard man always went to Harvard. Again, find the probability that the grandson of a man from Harvard went to Harvard.

Solution

We first form a Markov chain with state space S = {H, D, Y} and the following transition probability matrix:

Note that the columns and rows are ordered: first H, then D, then Y. Recall: the ij entry of the matrix gives the probability that the Markov chain starting in state i will be in state j after n steps. Thus, the probability that the grandson of a man from Harvard went to Harvard is the upper-left element of the matrix:

It is equal to 0.7 = 0.8 + 0.2 * 0.3 and, of course, one does not need to calculate all elements of P to answer this question.

If all sons of men from Harvard went to Harvard, this would give the following matrix for the new Markov chain with the same set of states:

The upper-left element of P is 1, which is not surprising because the offspring of Harvard men enter this very institution only.

Exercise 2: Mating rabbits

Consider an experiment of mating rabbits. We watch the evolution of a particular gene that appears in two types, G or g. A rabbit has a pair of genes, either GG (dominant), Gg (hybrid–the order is irrelevant, so gG is the same as Gg) or gg (recessive). In mating two rabbits, the offspring inherits a gene from each of its parents with equal probability. Thus, if we mate a dominant (GG) with a hybrid (Gg), the offspring is dominant with probability 1/2 or hybrid with probability 1/2.

Questions

(i) Write down the transition probabilities of the Markov chain thus defined.

(ii) Assume that we start with a hybrid rabbit. Let μ_n be the probability distribution of the character of the rabbit of the n-th generation. In other words, μ_n(GG), μ_n(Gg), μ_n(gg) are the probabilities that the n-th generation rabbit is GG, Gg, or gg, respectively. Compute μ₁, μ₂, μ₃. Can you do the same for μ_n for general n?

Solution

(i) The set of states is S = {GG, Gg, gg} with the following transition probabilities:

We can rewrite the transition matrix in the following form:

(ii) The elements from the second row of the matrix will give us the probabilities for a hybrid to give dominant, hybrid or recessive species in the (n-1)th generation in this experiment, respectively (reading this row from left to right). We first find:

so that μ_i(GG) = 0.25, μ_i(Gg) = 0.5, μ_i(gg) = 0.25, i = 1, 2, 3.

Actually, the probabilities are the same for any i. If you obtained this result before 1858 when Gregor Mendel started to breed garden peas in his monastery garden and analysed the offspring of these matings, you would probably be very famous because it definitely looks like a law! This is what Mendel found when he crossed mono-hybrids. In a more general setting, this law is known as Hardy-Weinberg law.

Exercise 3: Calculating machine

A certain calculating machine uses only the digits 0 and 1. It is supposed to transmit one of these digits through several stages. However, at every stage, there is a probability p that the digit that enters this stage will be changed when it leaves and a probability q = 1 - p that it won’t.

Questions

Form a Markov chain to represent the process of transmission by taking as states the digits 0 and 1. What is the matrix of transition probabilities? Now draw a tree and assign probabilities assuming that the process begins in state 0 and moves through two stages of transmission. What is the probability that the machine, after two stages, produces the digit 0 (i.e., the correct digit)?

Solution

Taking as states the digits 0 and 1, we identify the following Markov chain (by specifying states and transition probabilities):

where p + q = 1. Thus, the transition matrix is as follows:

It is clear that the probability that the machine will produce 0 if it starts with 0 is p² + q².

Exercise 4: Profession inheritance

Assume that a man’s profession can be classified as professional, skilled labourer, or unskilled labourer. Assume that, of the sons of professional men, 80 percent are professional, 10 percent are skilled labourers, and 10 percent are unskilled labourers. In the case of sons of skilled labourers, 60 percent are skilled labourers, 20 percent are professional, and 20 percent are unskilled. Finally, in the case of unskilled labourers, 50 percent of the sons are unskilled labourers, and 25 percent each are in the other two categories. Assume that every man has at least one son, and form a Markov chain by following the profession of a randomly chosen son of a given family through several generations. Set up the matrix of transition probabilities. Find the probability that a randomly chosen grandson of an unskilled labourer is a professional man.

Solution

The Markov chain in this exercise has the following set states S = {Professional, Skilled, Unskilled} with the following transition probabilities:

With:

And thus the probability that a randomly chosen grandson of an unskilled labourer is a professional man is 0.375.

Exercise 5: Umbrella problem

I have 4 umbrellas, some at home, some in the office. I keep moving between home and office. I take an umbrella with me only if it rains. If it does not rain, I leave the umbrella behind (at home or in the office). It may happen that all umbrellas are in one place, I am at the other, it starts raining, and I must leave, so I get wet.

Questions

1. If the probability of rain is p, what is the probability that I get wet?

2. Current estimates show that p = 0.6 in Edinburgh. How many umbrellas should I have so that, if I follow the strategy above, the probability I get wet is less than 0.1?

Solution

To solve the problem, consider a Markov chain taking values in the set S = {i: i = 0, 1, 2, 3, 4}, where i represents the number of umbrellas in the place where I am currently at (home or office). If i = 1 and it rains, then I take the umbrella, move to the other place, where there are already 3 umbrellas, and, including the one I bring, I have next 4 umbrellas. Thus, p_1,4 = p because p is the probability of rain. If i = 1 but does not rain, then I do not take the umbrella, I go to the other place and find 3 umbrellas. Thus, p_1,3 = 1 - p ≡ q.

Continuing in the same manner, I form a Markov chain with the following diagram:

• State: 0
• Transition: 1
• State: 2
• Transition: 3
• State: 4

Let us find the stationary distribution. By equating fluxes, we have:

π(2) = π(3) = π(1) = π(4)

π(0) = π(4)q.

Also, ∑_i=0⁴ π(i) = 1.

Expressing all probabilities in terms of π(4) and inserting in this last equation, we find:

π(4)q + 4π(4) = 1, or

π(0) = q/(q + 4).

I get wet every time I happen to be in state 0 and it rains. The chance I am in state 0 is π(0). The chance it rains is p. Hence:

P(WET) = π(0) * p = pq / (q + 4)

With p = 0.6, i.e. q = 0.4, we have P(WET) ≈ 0.0545, less than 6%. That’s nice.

If I want the chance to be less than 1% then, clearly, I need more umbrellas. So, suppose I need N umbrellas. Set up the Markov chain as above. It is clear that:

π(N) = π(N-1) = ... = π(1),

π(0) = π(N)q.

Inserting in ∑_i=0^N π(i) = 1, we find:

π(N) = π(N-1) = ... = π(1), π(0) = 1/(q + N),

and so

P(WET) = pq / (q + N)

We want P(WET) = 1/100, or q + N > 100pq, or

N > 100pq/q - q,

or

N > 23.6.

So to reduce the chance of getting wet from 6% to less than 1% I need 24 umbrellas instead of 4. That’s too much. I’d rather get wet.

Exercise 6: Markov chain with random variables

Suppose that ξ₀, ξ₁, ξ₂, ... are independent random variables with common probability function f(k) = P(ξ = k) where k belongs, say, to the integers. Let S = {..., -N, ..., 0, ..., N}. Let X be another random variable, independent of the sequence (ξ_n), taking values in S and let f: S × Z → S be a certain function. Define new random variables X₁, X₂, ... by X_n+1 = f(X_n, ξ_n), n = 0, 1, 2 ...

Questions

(i) Show that the X_n form a Markov chain.

(ii) Find its transition probabilities.

Solution

(i) Fix a time n ≥ 1. Suppose that you know that X_n = x. The goal is to show that PAST=(X₀, ..., X_n-1) is independent of FUTURE=(X_n+1, X_n+2, ...).

The variables in the PAST are functions of X₀, ξ₁, ..., ξ_n-2.

The variables in the FUTURE are functions of x, ξ_n, ξ_n+1, ... Therefore, the PAST and the FUTURE are independent.

(ii) P(X_n+1 = y|X_n = x) = P(f(X_n, ξ_n) = y|X_n = x) = P(f(x, ξ_n) = y|X_n = x) = P(f(x, ξ_n) = y)

= P(f(x, ξ₀) = y) = P(ξ₀ ∈ A_x,y), where A_x,y := {ξ: f(x, ξ) = y}.

Exercise 7: Topological properties of Markov chains

Discuss the topological properties of the graphs of the following Markov chains:

Draw the transition diagram for each case.

Solution

(a) Irreducible? YES because there is a path from every state to any other state. Aperiodic? YES because the times n for which p_1,1⁽ⁿ⁾ > 0 are 1, 2, 3, 4, 5, ... and their gcd is 1.

(b) Irreducible? YES because there is a path from every state to any other state. Aperiodic? YES because the times n for which p_1,1⁽ⁿ⁾ > 0 are 1, 2, 3, 4, 5, ... and their gcd is 1.

(c) Irreducible? NO because starting from state 2 it remains at 2 forever. However, it can be checked that all states have period 1, simply because p_i,i⁽ⁿ⁾ > 0 for all i = 1, 2, 3.

(d) Irreducible? YES because there is a path from every state to any other state. Aperiodic? NO because the times n for which p_1,1⁽ⁿ⁾ > 0 are 2, 4, 6, ... and their gcd is 2.

(e) Irreducible? YES because there is a path from every state to any other state. Aperiodic? YES because the times n for which p_1,1⁽ⁿ⁾ > 0 are 1, 2, 3, 4, 5, ... and their gcd is 1.

Exercise 8: Knight's tour on a chess board

Consider the knight’s tour on a chess board: A knight selects one of the next positions at random independently of the past.

Questions

(i) Why is this process a Markov chain?

(ii) What is the state space?

(iii) Is it irreducible? Is it aperiodic?

(iv) Find the stationary distribution. Give an interpretation of it: what does it mean, physically?

(v) Which are the most likely states in steady-state? Which are the least likely ones?

Solution

(i) Part of the problem is to set it up correctly in mathematical terms. When we say that the “knight selects one of the next positions at random independently of the past” we mean that the next position X_n+1 is a function of the current X_n and a random choice ξ_n of a neighbour. Hence the problem is in the same form as the one above. Hence (X_n) is a Markov chain.

(ii) The state space is the set of the squares of the chess board. There are 8 x 8 = 64 squares. We can label them by a pair of integers. Hence the state space is S = {(i₁, i₂) : 1 ≤ i₁ ≤ 8, 1 ≤ i₂ ≤ 8}.

(iii) The best way to see if it is irreducible is to take a knight and move it on a chessboard. You will, indeed, realise that you can find a path that takes the knight from any square to any other square. Hence every state communicates with every other state, i.e. it is irreducible.

To see what the period is, find the period for a specific state, e.g. from (1, 1). You can see that, if you start the knight from (1, 1) you can return it to (1, 1) only in even number of steps. Hence the period is 2. So the answer is that the chain is not aperiodic.

(iv) You have no chance in solving a set of 64 equations with 64 unknowns, unless you make an educated guess. First, there is a lot of symmetry. So squares (states) that are symmetric with respect to the centre of the chess board must have the probability under the stationary distribution. So, for example, states (1, 1), (8, 1), (1, 8), (8, 8) have the same probability. And so on. Second, you should realise that (1, 1) must be less likely than a square closer to the centre, e.g. (4, 4). The reason is that (1, 1) has fewer next states (exactly 2) than (4, 4) (which has 8 next states). So let us make the guess that if x = (i₁, i₂), then π(x) is proportional to the number N(x) of the possible next states of the square x: π(x) = CN(x).

But we must SHOW that this choice is correct. Let us say that y is a NEIGHBOUR of x if y is a possible next state of x (if it is possible to move the knight from x to y in one step). So we must show that such a π satisfies the balance equations:

∑π(x) = ∑π(y)p_y,x

Equivalently, by cancelling C from both sides, we wonder whether:

∑N(x) = ∑N(y)p_y,x holds true.

But the sum on the right is zero unless x is a NEIGHBOUR of y:

∑N(x) = ∑N(y)p_y,x where x is a neighbour of y.

But the rule of motion is to choose one of the neighbours with equal probability:

p_y,x = 1/N(y), if x is a neighbour of y.

Which means that the previous equation becomes:

∑1/N(y)N(x) = ∑N(y) where y is a neighbour of x.

Using the obvious fact that x is a neighbour of y if and only if y is a neighbour of x (symmetry of the relation) and so the last sum equals, indeed, N(x). So our guess is correct!

Therefore, all we have to do is count the neighbours of each square x. Here we go:

Let's calculate C and the probability for each state:

• 2 corners with 2 moves each: π(1,1) = π(8,8) = 2/336
• 4 edge squares with 3 moves each: π(1,2) = π(2,1) = 3/336
• 16 other squares with 4 moves each: π(2,2) = 4/336
• 16 interior squares with 8 moves each: π(4,4) = 8/336

Meaning of π: If we start with P(X₀ = x) = π(x), for x ∈ S, then, for all times n ≥ 1, P(X_n = x) = π(x), for x ∈ S.

(v) The corner ones are the least likely: 2/336. The 16 middle ones are the most likely: 8/336.

Exercise 9: Absorbing Markov chain

Consider a Markov chain with two states 1, 2. Suppose that p_1,2 = a, p_2,1 = b. For which values of a and b do we obtain an absorbing Markov chain?

Solution

One of them (or both) should be zero. Because, if they are both positive, the chain will keep moving between 1 and 2 forever.

Exercise 10: Smith's dilemma

Smith is in jail and has 3 dollars; he can get out on bail if he has 8 dollars. A guard agrees to make a series of bets with him. If Smith bets A dollars, he wins A dollars with probability 0.4 and loses A dollars with probability 0.6. Find the probability that he wins the series of bets and gets out of jail.

(Solution not provided in the original text.)