Transition Probabilities

A coin is tossed, and the probability of heads equals $p$. Define $\xi_n$ as the difference between the number of heads and the number of tails after $n$ tosses of the coin. In Problems 27.1--27.6, find the matrices of transition probabilities for the Markov chains describing the given process.

A die is thrown. Let $\xi_n$ be the largest of the numbers obtained in the first $n$ throws. Find the matrix of transition probabilities for the Markov chain describing this process.

Two urns together contain $N$ black and $N$ white balls, arranged so that each urn contains exactly $N$ balls. At each moment of time $n$, one ball is drawn at random from each urn, and the two balls are exchanged. Let $\xi_n$ denote the number of white balls in the first urn at time $n$. Find the matrix of transition probabilities for the Markov chain describing this process.

A particle located on a line moves along that line under the influence of random impulses occurring at integer moments of time. The particle can be at points with integer coordinates $0, 1, \ldots , N$; at the points $0$ and $N$ there are reflecting walls. Each impulse moves the particle to the right with probability $p$ and to the left with probability $1-p$, unless the particle is at a wall. If the particle is at a wall, any impulse moves it one unit inward, into the interval between the walls. Let $\xi_n$ denote the particle's coordinate after the $n$-th impulse. Find the matrix of transition probabilities for the Markov chain describing this process.

A particle located on a line moves along that line under the influence of random impulses occurring at integer moments of time. The particle can be at points with integer coordinates $0, 1, \ldots , N$; at the points $0$ and $N$ there are absorbing walls. Each impulse moves the particle to the right with probability $p$ and to the left with probability $1-p$, unless the particle is at a wall. If the particle is at a wall, it remains there forever. Let $\xi_n$ denote the particle's coordinate after the $n$-th impulse. Find the matrix of transition probabilities for the Markov chain describing this process.

A white rat is placed in the maze shown in the figure. [Figure omitted -- see source PDF page 153: a diagram of a 9-cell maze, cells numbered 1 through 9, with corridors connecting adjacent cells.] The rat moves from cell to cell at random, i.e., if a cell has $k$ exits, the rat chooses each of them with probability $1/k$. At each moment of time the rat necessarily moves to one of the neighboring cells. Let $\xi_n$ denote the number of the cell the rat is in after the $n$-th move. Find the matrix of transition probabilities for the Markov chain describing this process.

Items arrive at a rate of one per minute to a worker stationed at an inspection post, and each item, independently of the others, may turn out to be defective with probability $p$. The worker inspects the arriving items one after another, spending one minute inspecting each item. If an item turns out to be defective, the worker stops inspecting other items and repairs the defective one, which takes an additional 5 minutes. Is the quantity $\xi_n$ --- the number of items that have accumulated at the worker's station $n$ minutes after the start of work --- a Markov chain?

Let $\xi_n$ be as defined in the previous problem, and let $\nu_n$ be the time already spent by the worker inspecting and repairing the item currently being handled. Is the vector $(\xi_n, \nu_n)$ a Markov chain?

Let the points $A_1, \ldots , A_n$ be the vertices of a regular $n$-gon. A particle performs a random walk on the points $A_1, \ldots , A_n$. Is the sequence of positions of the particle a Markov chain if the particle:

A particle performs a random walk in the plane on the integer points $(i, j)$ such that $0 \leqslant i, j \leqslant N$. From any interior point of the given square, the particle moves, with equal probabilities and independently of its previous motion, to one of the neighboring points. Is the sequence of positions of the particle a Markov chain if, upon reaching the boundary, the further motion of the particle follows the rule:

At the initial moment of time, an urn contains $n_0$ white and $m_0$ black balls. At each subsequent unit of time, one ball is drawn from the urn without replacement. Let $n_k$ be the number of white balls and $m_k$ the number of black balls in the urn at time $k$. Which of the following sequences form a Markov chain and which do not:

Let $\{ \xi_n\}$ be a simple random walk on $\mathbb {Z}$, i.e., a Markov chain with transition probabilities $p_{i,i+1} = p$ and $p_{i,i-1} = 1-p$. Find the $n$-step transition probabilities.

Let $\{ \xi_n\}_{n=-\infty }^{\infty }$ be a stationary sequence whose terms take only the values $0$ and $1$. Set

Prove that $\{ \eta_n\}$ is a Markov chain. Find its transition probabilities if the random variables $\{ \xi_n\}$ are independent.

Let $\xi_0, \xi_1, \ldots$ be independent random variables taking the values $1$ and $-1$ with probability $1/2$ each. Prove that the random variables $\eta_n = \dfrac {\xi_n + \xi_{n+1}}{2}$ do not form a Markov chain.

Let the independent random variables $\xi_0, \xi_1, \ldots$ take the values $1$ and $-1$ with probabilities $p$ and $1-p$, respectively. Do the following sequences of random variables form Markov chains:

Consider a sequence of Bernoulli trials. Let $\xi_n = 1$ if trials number $n-1$ and $n$ both resulted in success, and $\xi_n = 0$ otherwise. Prove that the random variables $\xi_n$ do not form a Markov chain.

Let $\{ \xi_n\}$ be a stationary Markov chain taking only the values $0$ and $1$, with transition probability matrix

Set $\eta_n = 1$ if $(\xi_n, \xi_{n-1}) = (1,1)$ or $(0,0)$, and $\eta_n = 0$ otherwise. Prove that the random variables $\{ \eta_n\}$ are independent and identically distributed.

Can every stochastic matrix be the matrix of two-step transition probabilities of some Markov chain?