# Convolve two arrays on Google Sheets?

How can I take the convolution of two distributions on a spreadsheet such as Google Sheets?

Example 1: You want to multiply two arbitrary polynomials together on a spreadsheet symbolically (e.g. `2*x^4 + x` times `3*x^2 - 5`).

Example 2: Like in a board game or tabletop game, you have two 6-sided dice🎲🎲, with probabilities given by the following arrays/tables as a histogram. I'd like to figure what the probabilities are when you roll them together and add them up 🎲+🎲 "2d6".

x P(x) y P(y)
1 =1/6 = 16.6% 1 =1/6
2 =1/6 = 16.6% 2 =1/6
3 =1/6 = ... 3 =1/6
4 =1/6 4 =1/6
5 =1/6 5 =1/6
6 =1/6 6 =1/6

How do I get an array like below, in the general case with arrays of arbitrary size and values (not just a 6-sided die)?

sum P(X+Y=sum)
2 =1/36
3 =2/36
4 =3/36
5 =4/36
6 =5/36
7 =6/36
8 =5/36
9 =4/36
10 =3/36
11 =2/36
12 =1/36

(I would like to do this without using Google Apps Script, since I have found that sometimes excessive computation on Apps Script will hard-freeze the spreadsheet and cause it to become corrupted beyond repair for days or forever, with the "Loading..." error message.)

(disclosure: I am posting this question to answer it, which is explicitly allowed per the site rules, since the answer is nowhere on the internet.)

To convolve two or more distributions e.g. a * b * c, do the above operation one-at-a-time (e.g. conv(a, conv(b, c))) (ideally from the smallest domain to the largest domain will minimize computation; such an ordering will depend on your data, and is irrelevant if you don't have much data you're crunching).

This may be done as follows by using lambdas or Named Functions.

It is as simple as doing something like this:

``````=CONV(dice1, dice2)
``````

This works as follows. The below code may be copy-pasted into a single cell, or the inner code (between 'begin function body' and 'end function body') may be copy-pasted into a named function's body. However, note that you will need the definition for `MYMAP1` (see addendum at end of this answer far below) to workaround an existing bug in Google Sheets.

``````=LAMBDA(x_px, y_py,
``````

named function: `CONV` (or whatever you want*)

description: given two Nx2 arrays {x,Px} and {y,Px} where x,y are values and Px,Py are probabilities, returns the convolution

parameter #1: `x_px` parameter #2: `y_py`

▼ ▼ ▼ begin named function body... ▼ ▼ ▼

``````LAMBDA(xs,pxs,ys,pys, flatouter2d, filterRows,

filterRows(
QUERY(
{
flatouter2d(xs,ys, LAMBDA(a,b, a+b)),
flatouter2d(pxs,pys, LAMBDA(a,b, a*b))
},
"select Col1,sum(Col2) group by Col1"
),
LAMBDA(i,negI,len,
i>1
)
)

)(
INDEX(x_px,,1),
INDEX(x_px,,2),
INDEX(y_py,,1),
INDEX(y_py,,2),
``````

...continue named function body... (the two functions below are the definitions of `flatouter2d` and `filterRows` used above)

``````  LAMBDA(as,bs,f,
FLATTEN(MYMAP1(as, LAMBDA(a,
TRANSPOSE(MYMAP1(bs, LAMBDA(b,
f(a,b)
)))
)))
),

LAMBDA(arr,f,
LAMBDA(len,

FILTER(
arr,
MAKEARRAY(len,1, LAMBDA(i,_,
f(i, len-i, len)
))
)

)(
ROWS(arr)
)
)
``````
``````)
``````

▲ ▲ ▲ ...end named function body; ▲ ▲ ▲

below we apply it to the probability distribution of two 6-sided dice:

``````)(
{1,1/6; 2,1/6; 3,1/6; 4,1/6; 5,1/6; 6,1/6},
{1,1/6; 2,1/6; 3,1/6; 4,1/6; 5,1/6; 6,1/6}
)
``````

How it works:

• The `flatouter2d` function creates a 2d table; for each row it considers the `as` (a's), and for that particular `a`, creates a row (transposes a column) by considering the `bs` (b's), and in considering the two writes the value `f(a,b)` into the cell (for some arbitrary function `f`; i.e. the dice values are summed f(a,b)=a+b, while the probabilities are multiplied f(a,b)=a*b. The flattening turns this X x Y array back into a single column.
• We do this twice (once for the domain i.e. dice values, and once for the range i.e. probabilities), and paste them back side-by-side `{..., ...}` like a zipper to get back our original "{z,Pz}" (Nx2 array) format.
• The duplicate entries are then summed together by using `QUERY`, combining the events with their associated probabilities.

(The query should probably have a `sort by` clause if one cares about sorting.)

The `FILTERROWS` function defined above is one of many possible versions and generically useful (equivalent to a more powerful "slice operator"); it is merely used to get rid of the first informational header row returned by `QUERY` i.e. `i>0` filters out the header.

The function body for `CONV` could be less verbose (half the size) if `FILTERROWS` and even maybe `FLAPMAP2D` were moved into their own named functions.

*IMPORTANT NOTE: You may want to call this `CONV_V1` or something, if you plan to have a name in Apps Script that is called `conv`, otherwise there will be a namespace collision and one or the other won't work.

If you are taking multiple convolutions, you can use the `REDUCE` function. For example, to take the power of a distribution `DIST_POW(dist,n)` e.g. sum of 4 six-sided dice:

``````=IF(n=1,dist,
REDUCE(
dist,
SEQUENCE(n-1),
LAMBDA(acc,x,
CONVOLVE(acc,dist)
)
)
)
``````

bonus: To apply a function to the dice values `DIST_MAP(dist, f)`:

``````=MYMAP2(
INDEX(dist,,1),
INDEX(dist,,2),
f
)
``````

e.g. like if 'snakeeyes' (1+1) is worth 12 then `f`=DIST_MAP(dist, LAMBDA(x, IF(x=2,12))`.

Bug in Google Sheets implementation of `MAP`:

It is currently the case that if you pass a 1x1 array to `MAP`, you will not be allowed to return a row or column. This can cause very frustrating and hard-to-track-down bugs. To avoid this problem, if the array you pass in might ever be of size 1, use one of the following workarounds:

definition of `MYMAP1(xs, f)`:

``````=IF( (ROWS(xs)<>1)+(COLUMNS(xs)<>1),
MAP(xs, f),
f(xs)
)
``````

definition of `MYMAP2(xs,ys, f)`:

``````=IF( (ROWS(xs)<>1)+(COLUMNS(xs)<>1) + (ROWS(ys)<>1)+(COLUMNS(ys)<>1)
,
MAP(xs,ys, f),
f(xs,ys)
)
``````

(Also note that technically `map({}, ...)` should return the empty array `{}`, but I'm not sure that's even possible in Google Sheets to have an empty array.)

• Thank you for contributing that. Regarding `map()`: I agree that the "no zero-length array allowed" issue is a problem. My understanding is that `map()` will always return an array of the same size as its arguments, including an array of just one value, as in `=map( { 1 }, lambda(value, value + 1) )`. You can resize an array of one value, one row or one column to match the dimensions of a range with `arrayformula(iferror(range/0, value))`. Dec 3, 2022 at 11:51

Not attempting to solve convolutions in the general case — just pointing out that you can get the probability distribution of the sum of two simple independent integer variables with this pattern:

``````=arrayformula(
lambda(
dice1, dice2,
lambda(
numCombos,
query(
flatten(dice1 + transpose(dice2)),
"select Col1, count(Col1) / " & numCombos & "
group by Col1
label
Col1 'sum',
count(Col1) / " & numCombos & " 'P(X+Y=sum)'
",
0
)
)(
counta(dice1) * counta(dice2)
)
)(
sequence(6), sequence(6)
)
)
``````