# 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).

## 2 Answers

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))`.

ADDENDUM:

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

You will need to add these definitions to your Named Functions.

(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)
)
)
``````