3

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 2

2

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

1
  • 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
1

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

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.