Number of possible ways for a group of ratings to give a specified average

Question

This is a combinatorial counting problem I'm trying to solve just for my own curiosity, but the obvious approach (in my mind) balloons into a multi-dimensional nightmare very quickly.

Say you work for a service, and customers can give you a rating. The rating scale is 1..5, with 5 as best. They have 24 hours to rate you, and after that they can't. You don't get to see the individual ratings, but you can see the average rating over the past 24 hours. You only know you got somewhere between 1 and 'n' ratings that resulted in the current average, where 'n' is the number of customers you've had in the past 24 hours. (Some people rate immediately, some wait a bit, and some never get around to it.)

Here's the problem: given an average rating and the maximum number of possible ratings (ie., customers) over the past 24 hours, what are the different combinations of ratings that could have been given that will produce that exact average rating value? Also, historically speaking, it's very rare for 100% of customers to give ratings; the average is around 60%-70%.

If it helps, assume there won't be more than 20 possible ratings in any 24 hour period. Also, assume the average never drops below 4.0 -- that is, most ratings are 5's. The question is, what's the possible distribution of non-5 ratings for any given average?

Example: you had 10 customers in the past 24 hours, and you have an average rating of 4.67. What are the possible ratings that could have produced that average? (I got that average with three ratings of: 5, 5, and 4.) The question is, how can one discover all possible rating combinations that produce a 4.67 average with a max of 10 possible ratings?

Perhaps I should add that the norm is 5. So 5s pull the average up, while everything else pulls it down.

The rating is always given as a floating point number with at most two decimals: 4.xx

Answer 1

(Borrowing the setup from Cristian's answer:) Denote by $x_k\in{\mathbb N}_{\geq0}$ $\>(1\leq k\leq5)$ the number of times grade $k$ has been given, by $\lambda^*$ the true average grade and $\lambda$ the rounded average grade, and by $n$ the number of customers in the last 24 hours, and let $\lambda^+=\lambda+.005$, $\lambda^-=\lambda-.005$ (these are the bounds on the true average grade). Also, let $s=\sum_{k=1}^5x_k\le n$ be the number of voters. Then: $$\lambda^-s\le\sum_{k=1}^5 k\>x_k\le\lambda^+s.$$

This constraint on $\lambda$ severely limits the number of possibilities for $s$, because $s\lambda^*$ is an integer and $s\lambda$ is close to an integer, and since $s$ is fairly small we can correct for this inexactitude. So our first step is to find integers $s,T=s\lambda^*$ that satisfy $\operatorname{round}(T/s)=\lambda$. If you are programming this you can just check that $\lfloor s\lambda^-\rfloor \ne\lfloor s\lambda^+\rfloor$ for each candidate $s$ - any number which does not satisfy this cannot be a possibility. For example, for $\lambda=4.67$ we see that for $s=1$ this gives $[4.665,4.675]$ which does not contain an integer, $s=2$ gives $[9.33,9.35]$ which does not contain an integer, and $s=3$ gives $[13.995,14.025]$ which contains $T=14$. This reflects the fact that $4.67$ is probably rounded from $4+2/3=14/3$.

After fixing integers $s,T$ by this search, we can list the lattice points that satisfy this total value. First we need to find one point on the lattice; if $4\le\lambda^*\le 5$ we can use $b=(0,0,0,5s-T,T-4s)$, which you can check satisfies $\sum_ix_i=s$ and $\sum_iix_i=T$ (this says that everyone votes $4$ or $5$, with the proportions calibrated to give the right average).

From this basepoint, we can use the three lattice generators:

$$v^1=(3,-4,0,0,1)\qquad v^2=(2,-3,0,1,0)\qquad v^3=(1,-2,1,0,0)$$

Note that for each $v^k$, $\sum_iv^k_i=0$ and $\sum_iiv^k_i=0$. Thus adding $v^k$ to a lattice point yields another lattice point, and since this is a $5$-dimensional system reduced by two equations, and these vectors are clearly independent, this gives all the lattice points.

The only issue is how far to go. We've just seen that $b+n_1v^1+n_2v^2+n_3v^3$ is a solution for any $n_k\in\Bbb Z$, but this doesn't take into account the nonnegativity constraints on the $x_i$'s. I won't go into details, but it's not hard to verify that a solution is nonnegative iff it satisfies $$4s-T\le n_1\le\frac34(5s-T),\qquad T-5s\le n_2\le-\frac43n_1,\\\max(0,-3n_1-2n_2)\le n_3\le-\frac12(4n_1+3n_2),$$ and it's not difficult to simply enumerate all integer triples satisfying these inequalities. This yields a complete enumeration of the solutions in roughly $O(n^4)$ steps, where $n$ is the upper bound on $T$ here, which is proportional to our original $n$ for the number of customers that could have voted.

Answer 2

(This is not an answer in the proper sense. It just introduces the relevant variables, given the data.)

Denote by $x_k\in{\mathbb N}_{\geq0}$ $\>(1\leq k\leq5)$ the number of times grade $k$ has been given, by $\lambda$ the average grade, and by $n$ the number of customers in the last 24 hours. Then $$\lambda={\sum_{k=1}^5 k\>x_k \over\sum_{k=1}^5 x_k}\ .$$ It follows that the $x_k$ satisfy the conditions $$\sum_{k=1}^5(k-\lambda) x_k=0, \qquad\sum_{k=1}^5 x_k\leq n\ .$$ Note that $\lambda$ may be not known exactly. Given that $n\leq20$ and $\geq60\%$ of the customers respond there are about $${1\over5!}\bigl(20^5-14^5)\doteq22\,000\tag{1}$$ lattice points to check. The expression $(1)$ represents the volume of the set $$\{(x_1,\ldots, x_5)\in{\mathbb R}^5\>|\>x_k\geq0, \ 14\leq x_1+\ldots+ x_5\leq 20\}\ .$$

Answer 3

This is the answe explaining one posible aproach you can use to solve your problem that I tried to post on Stack Owerflow before your question has been put on hold.

If you asume that all votes are either 4 or 5 then the answer is pretty simple. All you have to do is reverse the process that you use in calculation of average value.

You calculate average by using next approach.

AverageOfVotes = SumOfAllVotes / NumberOfVotes

So you should reverse this in order to get SumOfAllVotes value out

SumOfAllVotes = AverageOfVotes * NumberOfVotes

Now when you have SumOfAllVotes available you calculate its difference between maximum possilbe sum of votes which would be

MaximumSumOfVotes = NumberOfVotes * MaximumVoteValue //In your case 5

So if you asume that all votes are only 4 or 5 you can also asume that number of 4 votes is the same as the difference between maximum sum of votes and your current sum of votes. The rest of votes are 5.

So if we check your example of three votes (5,5 and 4)

Average = SumOfVotes / NumberOfVotes
Average = (5+5+4) / 3
Average = 14 / 3
Average = 4,666666666666667

Reversing the process

SumOfVotes = Average * NumberOfVotes

SumOfVotes = 4,666666666666667 * 3
SumOfVotes = 14

NumberOf4Votes = MaximumSomofVotes - SumOfVotes
NumberOf4Votes = (NumberOfVotes * maximumVoteValue) - SumOfVotes
NumberOf4Votes = (3 * 5) - 14
NumberOf4Votes = 15 - 14
numberOf4Votes = 1

But as soon as the posible votes are 3, 4 and 5 or even 1 and 2 this becomes much more complex. Why? Becouse there are multiple vote combinations that would result in same SumOfVotes. But the overal process would be still the same.

I hope my answer makes any sense to you.

Answer 4

Let $A(i,r,k)$ denote the set of possible rate sets (each rate is encoded as $(x_1,...,x_i)$, $x_j$ being the number of rates $j$) that yield a sum of rates equal to $r$, with possible rates from $1$ to $i$ and $k$ voters.

You can write the following recursive relation : $$ A(i,r,k)=\cup_{i.l \le r,l\le k} \left( A(i-1,r-l.i,k-l) \times \{x_i=l\} \right) $$ $$ A(0,0,0)=\emptyset $$

where $\times$ is the cartesian product. You can use this relation to compute the set for all $(i,r,k)$ such that $R.k=r, i=5, 0 \le k \le n$, $R$ being the given average rate.

To be efficient, do not use a recursive algorithm, but rather a dynamic-programming like algorithm (start with $i=k=r=0$, and compute $A(i,k,r)$ using the values of $A$ for smaller parameters already computed and stored).

Edit: depending on the number of possible voters, computing $A$ for all smaller values of $(i,r,k)$ may not be the most efficient. One can consider a recursive approach storing all values of $A$ already computed in a hash map for example.

Edit 2: As explained by @MarioCarneiro, the number of solutions is polynomial in the number of possible voters (since the number of possible individual rates being a fixed constant). It follows that a simple 5-nested loops procedure would do the job.