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.

  • 1
    $\begingroup$ Please use MathJax to properly format math expressions. $\endgroup$ – Lee David Chung Lin Apr 9 at 1:41
  • $\begingroup$ perhaps trying solving it "by hand" and then after that, translate what you did into linear algebra operations $\endgroup$ – phdmba7of12 Apr 9 at 1:44
  • $\begingroup$ I solved by hand but I couldn't come up with a concise linear algebraic operation. I have a feeling that its grounded in markov chain and transitions but I couldn't do it. $\endgroup$ – toing Apr 9 at 1:50

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.


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?)

  • $\begingroup$ Thanks for taking effort to expand on your answer. I wish there was an easy linear transformation. But this is helpful. $\endgroup$ – toing Apr 10 at 13:42
  • 1
    $\begingroup$ if you want a precise notation, then there is already a precise notation for convolution, $a * b$. In the context of sequences (more generally, signals) the $*$ operator is understood to mean convolution. $\endgroup$ – antkam Apr 10 at 13:44

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.

  • 1
    $\begingroup$ not sure this is right... first of all, the OP wants a length-$7$ vector as final output, not a matrix. second, if your $x_i$ and $y_j$ are the original vector entries, then adding them isn't really the right thing. E.g. the prob that the two jobs together would take $2$ hours is $0.25 \times 0.33$. perhaps i'm missing something? $\endgroup$ – antkam Apr 9 at 21:38
  • $\begingroup$ Thanks @Cye Waldman. I however resonate concerns with antkam. How can I really use what you are suggesting? $\endgroup$ – toing Apr 9 at 22:48
  • $\begingroup$ @Cye Waldman - I think I understand it now. Once I have the Gazale sum matrix, I could process it further to get it in terms of frequency. Would you mind sharing implementation of Gazale sum if handy? $\endgroup$ – toing Apr 9 at 23:06
  • $\begingroup$ @toing The Gazale sum routine that I use is the exactly the Matlab kron function (Kronecker product) with one character changed. Therefore, I don't feel its appropriate for me to give it away. As for what the OP wants, it looks to me as though there are 21 ways of adding the two vectors. But since one of the vectors all have same values, I suppose it will reduce to a 7-vector. My attempt here was only to show one would create all the possible additive combinations of two data sets. I've used it for such problems as finding the closest pair of two curves (or random points). $\endgroup$ – Cye Waldman Apr 9 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.