How to compute the average in modular arithmetic?

Question

Let's say I'm working in modulo 10 and I have some numbers: 0,0,1,1,9.

How can I calculate the average?

I'm expecting 0,2 in my example (0+0+1+1-1 over 5).

Answer 1

We can attempt to define your intuitive "modular average" in the following way.

Let our set of data points be $\{a_1,a_2,\dots,a_n\}$

We define a modular average of the data points to be a point $\bar{a}$ such that $\sum\limits_{i=1}^n d(a_i,\bar{a})$ is minimized where the summation here is not done using modular arithmetic, but rather normal arithmetic and $d$ here is a distance function where $d(a,b) = \min\limits_{x\in[a],~y\in[b]}(|x-y|)$ where $[a]$ is the equivalence class of $a$.

We have as an example then, the "modular average" of $\{1,9\}$ in base 10 to be $0$ since this minimizes the sum, giving a sum of $2$ since $d(1,0)+d(9,0)=1+1=2$. On the other hand, $4$ would not be since you would have $d(1,4)+d(9,4)=3+5=8$.

This is not perfect however as in this play example we would also have every other value "between" $9$ and $1$ also minimizing the sum, for example, $1$ also minimizes the sum as $d(1,1)+d(9,1)=0+2=2$ as well. This does have the benefit however that an actual average will be a modular average.

To account for this, perhaps we might want to look instead at the values of $\bar{a}$ such that instead $\sum\limits_{i=1}^nd(a_i,\bar{a})^2$ is minimized. In doing so, perhaps we reduce the number of available modular averages, but we lose the property that our usual average will agree with the modular average under several circumstances.

Answer 2

The residues of modular arithmetic do not have an order, so there isn't a notion of median available. The arithmetic mean (the usual "average") can be calculated when the number to divide by (count of observations) is coprime to the modular base (but here you have $5$ observations, which is not coprime to $10$), but it doesn't convey the statistical sense of a typical value.

The most useful "average" here is the mode, the most frequent value appearing in the observations. You can sensibly claim that if $1$ appears three times in your sample of five, then $1$ is the mode of your observations. But here zero appears twice and one appears twice, so there is no unique mode.

Answer 3

Let me try to answer this is as principled a way as I can.

Your question suggests that you want to take a list of $k$ numbers, modulo some number $n$, and compute an "average" that's a real number. By "numbers mod $n$", it appear that you mean the numbers $0, 1, 2, \ldots, n-1$, i.e., you're not willing to say that $15$ is a number mod $7$. (Most mathematicians are quite happy to say something like this, and informally say "it's the same as the number $1$, mod $7$.")

What property should an "average" have?

Well...

A. if your $k$ numbers are all the same -- say they're all "3"s -- then the average should be that number.

B. What if you add $1$ to all the numbers in your set? Then the average should also increase by $1$, right?

Now right away that presents a problem, because if we're working $\bmod 10$, and we have the list $[9,9,9]$, whose average (by rule A) should be $9$, then we add $1$ to all of them to get $[0,0,0]$, but when we add one to the average, we get $10$. That's kind of a problem. Maybe we should modify rule B to say that the average is always a number between 0 and 9, and if it goes outside that range, we'll just apply the "mod" operation. That makes rule B work OK.

What if we have two sets of $k$ numbers, with averages $a$ and $b$. If we combine them to get a set of $2k$ numbers, we'd expect the average to be $\frac{a+b}{2}$, right? Maybe that should be rule C.

If you keep writing down "reasonable" things, you pretty rapidly find that they're not internally consistent, although you may have to be a bit clever about it, and try to think of examples where computing an average would be difficult, as a guide to showing that your rules are contradictory. Of course, when you find a contradiction, you might say "Wait...rule F wasn't really all that important, and it was the one that caused trouble, so I'll just delete it." You can go that route, but at some point you'll find that you're just defining a function, not an average in any reasonable sense.

But let me briefly go with the idea you mention: you can compute it geometrically. That's correct (almost). You can treat the number $k$, $\bmod n$, as being the same as the point $$ P_k = (\cos \frac{2 \pi k}{n}, \sin \frac{2 \pi k}{n}) $$ that's a fraction $k/n$ of the way around the unit circle from the point $P_0 = (1,0)$ on the $x$-axis. To compute the average of a bunch of mod-$n$ numbers, you average the corresponding points in $\Bbb R^2$. The problem is that you end up with...a point in $\Bbb R^2$ rather than a number. But you could imagine taking a ray from the origin through your point and seeing where it hits the unit circle. So if the average came out to be $(0.534, 0)$, then your answer would be the point $(1, 0)$ on the unit circle, which corresponds to $k = 0$. You could do that in general...except for cases like mod 12 arithmetic, where the average of 11, 1, 5, and 6 turns out to be at the origin. Now you can't project out to the circle.

So while this approach is sort of OK, you have to live with the idea that it may sometimes generate a "no answer" kind of result.

There's a bunch of work on topics like this; I think von Mises may be the name associated with early work on circular averages and statistics on the circle in general. Sam Bass wrote an article for the ACM Transactions on Graphics sometime in the 1990s, I think, about taking averages on higher-dimensional spheres. It would have back-pointers to earlier works.

Finally, your "average time I woke up" idea is also a good one, but if you woke up at 11, 1, 5, and 6, you'd be hard-pressed to find an "average time." What makes that work is that all the times you woke up were reasonably close to 8 AM, so a kind of local averaging works. What's going on, in more sophisticated terms, is that the exponential map from the tangent space at 8 AM to the circle (or in simpler words, the "wrapping function" based at "8" on the clock) lets you pull all the wake-up times into a line. [practically speaking: you take the signed distance from the wake up time to 8:00, so that 8:05 gets sent to 5, and 7:52 gets sent to -8, etc.] You can then take an average in this line, and it turns out (perhaps) that the average is actually 0...so you say your average wake-up time was 8:00. If the average came out to $+3$, you might try the whole exercise again, based at 8:03, and then the average would be zero, and you'd be happy. (This "repeat until average is zero" isn't essential on the circle, because its intrinsic curvature is zero, but if you want to generalize to things like a sphere, it's essential, so I included it.)

But let me note that if we took the times 1:45, 2:01, 2:15, 1:59 (whose average is obviously 2:00) and performed the exercise in the previous paragraph using, as our starting point, the time 8:00, we'd get offsets of 5:45, 6:59, -5:45, and -5:59, which average to 0, so I could claim that 8:00 was your average wake-up time.

Typical responses are "well, you should choose something reasonable as your starting point!" or "Oh, that's just a stupid bit of bad luck...we can ignore that." The first answer really is the better one...but what would be a "reasonable" choice? One of the points in the set? That doesn't (generally) work, as you can see by having wake-up times of 2,2,2,2,2,2,2,2,2,2,2,8,2,2,2,2,2. Perhaps the right starting point is the average! Oh...that's no good. That's what we're trying to FIND. Maybe choose multiple starting points at random, and see what we converge to, and take a vote. (In my example, almost all will result in "2" as the wake up time, and at most one will give the answer "8") But what if the vote is a tie? What if every starting point for the wake up times results in the answer that IT is the average? (You can see this happen by having wake up times of 1, 5, and 9.)

As I said, there's basically no good answer...unless you're willing to put some constraint on your points. If, for instance, you're willing to ask for the average only for lists of points that all lie in some half-circle, then you can do just fine. (In that case the "exponential" approach works great.) And that's the case with your wake-up times -- they're all within in a few hours, plus or minus, of 8 AM. If if they're all over the clock and the app gives some stupid answer, the app developers don't care --- they lose one user whose behavior is weird enough that they can't send him "buy a latte at Starbucks near you" ads just when he wakes up, i.e., he was a losing customer anyhow. (Call me cynical...)

The discussion I've given here also applies to higher-dimensional spheres, only moreso -- it's not even obvious at first that the exponential method converges, even when all the starting points lie in some hemisphere.

That's a long answer to a short question, and I hope it's of some use to you.