Chapter 2: Problem 10
Consider a random walk on the integers such that \(P_{i, l+1}=p, P_{1, i-1}=q\) for all integer i \((0
Over 30 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
Suppose 2 distinguishable fair coins are tossed simultaneously and repeatedly. An account of the tallies of heads and tails are recorded. Consider the event \(E_{n}\) that at the \(n\)th toss the cumulative number of heads on both tallies are equal. Relate the event \(E_{n}\) to the recurrence time of a given state for a symmetric random walk on the integers.
Let
$$
\mathbf{P}=\left\|\begin{array}{cc}
1-a & a \\
b & 1-b
\end{array}\right\|, \quad 0
If \(j\) is a transient state prove that for all \(i\) $$ \sum_{n=1}^{\infty} P_{i j}^{n}<\infty $$ uint: Use relation (5.10).
Given a finite aperiodic irreducible Markov chain, prove that for some \(n\) all torms of \(P^{3}\) are positive.
Let \(n_{1}, n_{2}, \ldots, n_{2}\) be positive integers with greatest common
divisor \(d\). Show that there exists a positive integer \(M\) such that \(m \geq
M\) implies there exist nonnegative integers \(\left\\{c_{j}\right\\}_{j=1}^{k}\)
such that
$$
m d=\sum_{j=1}^{k} c_{j} n_{j}
$$
(This result is needed for Problem 4 below.)
Hint: Let \(A=\left\\{n \mid n=c_{1} n_{1}+\cdots+c_{k}
n_{k},\left\\{c_{i}\right\\}\right.\) nonnegative integers\\}
Let \(B=\left\\{\begin{array}{l}b_{1} n_{1}+\cdots+b_{j} n_{j} \mid n_{1},
n_{2}, \ldots, n_{j} \in A, \text { and } b_{1}, \ldots, b_{j} \\ \text { are
positive or negative integers }\end{array}\right\\}\)
Let \(d^{\prime}\) be the smallest positive integer in \(B\) and prove that
\(d^{\prime}\) is a common divisor of all integers in \(A\). Then show that \(d\) '
is the greatest common divisor of all integers in \(A\). Hence \(d^{\prime}=d\).
Rearrange the terms in the representation \(d=a_{1} n_{1}+\cdots+a_{l} n_{i}\)
so that the terms with positive coefficients are written first. Thus
\(d=N_{1}-N_{2}\) with \(N_{1} \in A\) and \(N_{2} \in A\). Let \(M\) be the positive
integer, \(M=N \frac{2}{2} / d\). Every integer \(m \geq M\) can be written as
\(m=M+k=N_{2}^{2} / d+k\), \((k=0,1,2, \ldots)\), and \(k=\delta N_{2} / d+b\) where
\(0 \leq b
What do you think about this solution?
We value your feedback to improve our textbook solutions.
