Automatic Control (AC)
Question 3: Optimization
August 2016 Problem 1
Solution
The problem equal to:
Minimize $ 2x_1+x_2 $
Subject to $ \begin{align*} &x_1+3x_2-x_3=6\\ &2x_1+x_2-x_4=4\\ &x_1+x_2+x_5=3\\ &x_1, x_2, x_3, x_4,x_5 >=0 \end{align*} $
such that $ A= \begin{bmatrix} 1 & 3 & -1 & 0 & 0 \\ 2 & 1 & 0 & -1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{bmatrix} $
we take $ B= \begin{bmatrix} 1 & 3 & 0 \\ 2 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix} \Rightarrow B\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} $
Solution 2
Let $ Z=X+Y $,
$ P_Z(k)=P_Z(z=k)=P_Z(x+y=k)\\ =\sum_{i=0}^{k}P(x=i)(y=k-i)=\sum_{i=0}^{k}\frac{\lambda_1^i e^{\lambda_1}}{i!}\cdot\frac{\lambda_2^{k-i}e^{-\lambda_2}}{(k-i)!} =e^{-\lambda_1-\lambda_2}\cdot \frac{(\lambda_1+\lambda_2)^k}{k!} $
Using $ (a+b)^k=\sum_{i=0}^{k}a^ib^{(k-i)}\cdot \frac{k!}{i!(k-i)!} $
Therefore,
$ P_{X|Z}(x=k|z=n)=\frac{P(x=k,z=n)}{P(z=n)}=\frac{P(x=k,x+y=n)}{P(z=n)}=\frac{P(x=k,y=n-k)}{P(z=n)}\\ =\frac{\lambda_1^k e^{-\lambda_1}}{k!}\frac{\lambda_2^{n-k} e^{-\lambda_2}}{(n-k)!}\frac{n!}{e^{-\lambda_1}e^{-\lambda_2}(\lambda_1+\lambda_2)^n} = \frac{\lambda_1^k \lambda_2^{n-k} }{(\lambda_1+\lambda_2)^n}\frac{n!}{k!(n-k)!} $
Solution 3
We will view this problem through the lens of Bayes' Theorem. As such, we can write the conditional distribution as
$ P(X = x | X+Y = n) = \frac{P(X = x, X+Y = n)}{P(X+Y = n)} = \frac{P(X = x, Y = n - X)}{\sum^n_{k = 0}P(X = k, Y = n - k)} $.
Since $ X $ and $ Y $ are independent, we can further write
$ P(X = x | X+Y = n) = \frac{P(X = x)P(Y = n - X)}{\sum^n_{k = 0}(P(X=k)P(Y = n-k))} $.
Now let us separate the above expression into numerator and denominator. Recalling that $ X $ and $ Y $ are independent Poisson r.v.s, the numerator is given by
$ P(X = x)P(Y = n - X) = \frac{e^{-\lambda_1}\lambda_1^x}{x!}\cdot\frac{e^{-\lambda_2}\lambda_2^{n-x}}{(n-x)!} $.
Multiplying the above by $ \frac{n!}{n!} $ gives
$ P(X = x)P(Y = n - X) = \frac{e^{-\lambda_1 + \lambda_2}}{n!}{n\choose x}\lambda_1^x\lambda_2^{n-x} $.
Now let us examine the denominator. Again, we make use of the fact that $ X $ and $ Y $ are independent Poisson r.v.s to write
$ \sum^n_{k = 0}(P(X=k)P(Y = n-k)) = \sum^n_{k = 0}\left(\frac{e^{-\lambda_1}\lambda_1^k}{k!}\frac{e^{-\lambda_2}\lambda_2^{n-k}}{(n-k)!}\right) $.
Again, we multiply by $ \frac{n!}{n!} $ to obtain
$ \sum^n_{k = 0}(P(X=k)P(Y = n-k)) = \frac{e^{-\lambda_1 + \lambda_2}}{n!}\sum^n_{k = 0}{n\choose k}\lambda_1^k\lambda_2^{n-k} $.
We can make use of the binomial formula to simplify this expression. Recall that the binomial formula is given by
$ (a+b)^n = \sum^n_{k = 0}{n\choose k}a^k b^{n - k} $.
We use this to write
$ . \sum^n_{k = 0}(P(X=k)P(Y = n-k)) = \frac{e^{-\lambda_1 + \lambda_2}}{n!}\cdot(\lambda_1 + \lambda_2)^n $
Putting this all together, we can finally write
$ P(X = x | X+Y = n) = \frac{\frac{e^{-\lambda_1 + \lambda_2}}{n!}{n\choose x}\lambda_1^x\lambda_2^{n-x}}{\frac{e^{-\lambda_1 + \lambda_2}}{n!}\cdot(\lambda_1 + \lambda_2)^n} = {n\choose x}\frac{\lambda_1^x\lambda_2^{n-x}}{(\lambda_1 + \lambda_2)^n} $
and we are done.
Similar Problem
If $ X $ and $ Y $ are independent binomial random variables with success probabilities $ p $ and $ q $ respectively, find the probability mass function of $ X $ when $ X + Y = k $. In addition, investigate what happens to this p.m.f. when $ p = q $.
