1

Problem sheet 7, 2005, Nov. 18  MT441 Channels

If you haven’t done homework so far: Work through the homework and solutions of the previous weeks. If you want you can hand it in and get feedback. Please catch up with the material!

Ex. 1 A memoryless source emits only vowels, each with the following probabilities:

P (A) = 0.2, P (E) = 0.3, P (I) = P (O) = 0.2, P (U) = 0.1.

Estimate the number of typical outputs of length n. (Describe what you are doing: define what you mean by typical.)

Ex. 2 A memoryless source over the 26-letter alphabet has a vocabulary of about 10^{n} sequences of length n, for suifficiently large n. Estimate the entropy of the source. (Hint: The answer is simple and short.)

Ex. 3 Consider the infinite square lattice consisting of all integer-coordinated points of the plane and with nearest neighbours in the direction of the coordinate axes joined by an edge. A self avoiding walk of length n is a sequence of n edges starting from the origin, each pair of consecutive edges having a common point, and at no stage revisiting a point already visited. If f(n) denotes the number of self-avoiding walks of length n, then f(1) = 4, f(2) = 12 and so on. Prove that

f(m + n) ≤ f(m)f(n),

and hence deduce that

lim_{n→∞}(f(n))^{\frac{1}{n}} = inf_{n≥1}(f(n))^{\frac{1}{n}} = θ

exists. Determine f(3). Draw the situation for n = 1, 2, 3. Prove that 2 ≤ θ ≤ 3.

Ex. 4 With probability \frac{1}{3}, a source S emits a random string of zeros and ones; with probability \frac{2}{3}, it emits a random string of ones and twos. Show that the source is not ergodic.

Ex. 5 Find the entropy of the Markov source whose transition matrix is given by

(\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & \frac{1}{2} & \frac{1}{2} \end{matrix} )

Ex. 6 Which of the Markov sources having transition matrices as shown are irreducible?

M_{1} = (\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \end{matrix} ) , M_{2} = (\begin{matrix}1 & 0 & 0 \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 0 & \frac{1}{2} & \frac{1}{2} \end{matrix})

M_{3} = (\begin{matrix}\frac{1}{2} & \frac{1}{2} & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & \frac{1}{4} & \frac{3}{4} \end{matrix}) , M_{4} = (\begin{matrix}0 & \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 \end{matrix})

To be returned in one week, before the lecture. My web page contains a collection of related material. http://www.ma.rhul.ac.uk/∼elsholtz/WWW/lectures/0506mt441/lecture.html