Review Session
Updated 2017-12-06
Problems
Problem 1
Suppose we have \(Z_n=\frac{3}{4}Z_{n-1}+X_n\) with \(Z_0=0\) where \(X_n\sim \text{Bernoulli}\)
We can start by finding the Fourier transform of \(Z\):
\[Z(f)=\frac{3}{4}Z(f)e^{-j2\pi f}+X(f)\]Now factor out \(Z(f)\) and find the \(H(f)\):
\[H(f)=\frac{1}{1-\frac{3}{4}e^{-j2\pi f}}\]We recognize that the signal in time domain is
\[h(n)=(\frac{3}{4})^n u(n)\]Thus we know that the output has \(h(n)\) convolved with the input (product in frequency domain)
\[Z_n=h_n*X_n=\sum_{m=-\infty}^\infty X_m h_{n-m}=\sum_{m=1}^n X_m (\frac{3}{4})^{n-m}\\ =X_1(\frac34)^{n-1}+X_2(\frac34)^{n-2}+\dots+X_n\]What is the expected value of \(Z_n\)?
\[\mathbb E(Z_n)=\mathbb E(X_1(\frac34)^{n-1})+\mathbb E(\dots)+\dots\\ =\mathbb E(X_1)(\frac34)^{n-1}+\mathbb E(X_2)(\frac34)^{n-2}+\dots\\\]Since \(\mathbb E(X_1)=\mathbb E(X_2)=\dots\), then
\[=\mathbb E(X)[1+\frac34+(\frac34)^2+\dots]\\ =\mathbb E(X)\frac{1-(\frac34)^n}{1-\frac34}\]Since the second term is a geometric series.
We see that as time \(n\) increases, the mean of \(Z\) is changing, thus \(Z\) is not a stationary process.
Problem 2
Packets arrive at probability \(a\); packets depart at probability \(b\). The buffer can hold up to \(N\) packets. Let \(X_n\) be the number of packets in the buffer at time \(n\).
Show that the system can be modelled by Markov Chain:
Since at any time \(n\) we don’t care about the number of packets in the buffer at time \(n-2\) (history) if we already have all the information \(n-1\). In particular,
\[\mathbb P(X_{n+1}=x_{n+1}\vert X_n=x_n, X_{n-1}=x_{n-1\dots})\]The conditional stuff (after that \(\vert\) symbol) in the probability is useless information as far as the buffer is concerned.
There are total of \(N+1\) states in the Markov chain: state \(\in\{0,1,\dots,n-1,n,n+1,\dots,N-1, N\}\)
For state 0: there are two possible states to go to:
- There is a \(1-a\) probability that we will stay in state 0
- probability \(a\) to go to state 1
For state \(N\): there are also only two possible states to go
- \(1-b\) probability that we stay in state \(N\)
- \(a\) is the probability that we go to state \(N-1\)
For any state in between (state 1 to state \(N-1\)) there are three possible outcomes:
- probability of \(b(1-a)\) of going to a lower state; since we need one packet to be transmitted and no packets arrive. The probabilities are \(b\) and \(1-a\) respectively. Since packet being received by the buffer and transmitted by the buffer is independent, the probability that \(X_n\) goes from some number \(k\) to \(k-1\) is \(b(1-a)\).
- probability of \(a(1-b)\) of going to a higher state (same argument from above applies)
- probability of \(ab+(1-a)(1-b)\) of staying in the same state. This occurs when (no packets are received \(\wedge\) no packets are transmitted) \(\vee\) (packet arrives \(\wedge\) packet transmitted).
Therefore, the transition matrix is:
\[P=\begin{bmatrix} 1-a & a & 0 & 0 & \cdots &0&0\\ b(1-a) & ab+(1-a)(1-b) & a(1-b) & 0 & \cdots &0&0\\ \vdots & \ddots && &&& \vdots\\ 0 &0&0&0&\cdots&b&1-b \end{bmatrix}\]To find the stationary distribution, we use the fact that
\[\pi=\pi P\]Do the matrix multiplication and we obtain \(N\) equations for \(N\) variables: \(\pi_1,\pi_2\dots, \pi_N\).
The equations are:
\[\begin{align} \pi_0&=\pi_0(1-a)+\pi_1b(1-a)\\ \pi_1&=\pi_0(a)+\pi_1(ab+(1-a)(1-b))\dots\\ \vdots\\ \pi_N&=\dots \end{align}\]Then we substitute every equation in terms of \(\pi_0\), and for general \(n\), we find the pattern:
\[\pi_n=\frac{a^n(1-b)}{b^n(1-a)^n}\pi_0\]Then find \(\pi_0\) by setting an initial condition.
Office Hour
The variance for two normal random variables added together is the sum of two variances. (Proof later)