Given probability vectors $x$ and $y$, how can I compute probability vector of $z = x + y$ using linear algebra operations

Question

I have probability vector $t_1$ (hours to get '$A$' done), $p({t^{a}_{1})} = [0.25, 0.25, 0.25, 0.25]$ (here: $0.25$ probability for $A$ done in $1, 2, 3$ or $4$ hours).

Another probability vector $t_2$ (hours to get '$B$' done), $p({t^{b}_{2})} = [0.33, 0.33, 0.33]$.

How can I get to probability vector $p({t^{a}_{1}+t^{b}_{2}))}$ (hours to get both $A$ and $B$ done assuming they can only be done one after the other and distributions are independent) using linear algebra operations?

p.s.: I am looking for linear algebraic solution and suspect that there may be a solution via markov chain etc.

Answer 1

You don't need Markov chains. What you need is (discrete) convolution.

While convolution is linear (in both arguments), it is not among the "usual" linear algebra operations. E.g. you have a length-$4$ vector and a length-$3$ vector as the two inputs, and yet the result must be a length-$7$ vector. None of the "usual" linear algebra operations would do that... I'm sure you can write it in terms the usual linear algebra operations, including using block matrices, but it will be specific to the sizes involved, and very tedious, and frankly kinda pointless.

It is possible to map a convolution into a multiplication after a proper transform (e.g. Z-transform), but that does not seem like what you want either.

---

ADDENDUM

Let the two vectors be $a = [a_1, a_2, a_3, a_4]$ and $b = [b_1, b_2, b_3]$ where $a_j =$ prob that job $A$ takes $j$ hours, etc. Form this outer-product (ignore the color for now):

$$ C =a^T b = \begin{pmatrix} a_1 b_1 & a_1 b_2 & \color{red}{a_1 b_3} \\ a_2 b_1 & \color{red}{a_2 b_2} & a_2 b_3 \\ \color{red}{a_3 b_1} & a_3 b_2 & a_3 b_3 \\ a_4 b_1 & a_4 b_2 & a_4 b_3 \end{pmatrix} $$

Then, if I understand you correctly, you want a vector $f = [...f_k...]$ where $f_k =$ prob that both jobs (done sequentially) will take $k$ hours total. This means $f_k = \sum_{i+j = k} a_i b_j$ and e.g. $f_4 = a_3 b_1 + a_2 b_2 + a_1 b_3$, which as you can see is the sum of the entries in the $\color{red}{red}$ diagonal. Every different $k$ (from $2$ to $7$) is the sum of a different diagonal. Unfortunately for you, there is no standard linear-algebra operation that takes a $4 \times 3$ matrix and returns a length-$6$ vector of the sums of its $+45^\circ$ diagonals. What you're asking for is exactly convolution.

(BTW I suspect you might want to add a $0$ at the front to represent the impossibility of doing the two jobs in $1$ hour?)

Answer 2

What you want is a matrix sum that is not well known but is a perfectly valid solution to your problem. You will not find this, for example, in the Wikipedia article on Matrix addition. It would look like this

$$ z=\begin{pmatrix} x_1+y_1 & x_1+y_2 & \cdots & x_1+y_n \\ x_2+y_1 & x_2+y_2 & \cdots & x_2+y_n \\ \vdots & \vdots & \ddots & \vdots \\ x_m+y_1 & x_m+y_2 & \cdots & x_m+y_n \end{pmatrix} $$

A close examination of this will reveal that it's very much like the Kronecker product, albeit with addition instead of multiplication. Assuming that $x$ and $y$ are given as column vectors, I would write this as

$$z=x\oplus y^T$$

I'll probably get trampled for using the $\oplus$ symbol, but it's already used for two different matrix additions.

I call this the Gazal$\acute{e}$ sum after the author from whom I got the idea originally. (See Gazal$\acute{e}$, Gnomon: From Pharaohs to Fractals, Princeton University Press, 1999.) He refers to this as the Kronceker product with respect to addition. I have used this matrix extensively in problems where I have two data sets, such as finding the closest pair of points. I have programmed it by taking a Kronecker product algorithm and changing a single '$\times$' to '$+$'. This will also work if $x$ and/or $y$ are given as matrices, rather than vectors.