2
$\begingroup$

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

$\endgroup$
10
  • 2
    $\begingroup$ Hi David. Welcome to MSE! the convention to get help from other people is to also write down your thoughts besides the question. So please do so. The question has a familiar format. Has it taken from any kind of coding competitions out there? if so, you should mention that as well. $\endgroup$ Feb 13, 2015 at 8:50
  • $\begingroup$ Without any help concerning the main question, I just can say that rating distribution tends to normal (Bell curve). $\endgroup$ Feb 13, 2015 at 9:08
  • $\begingroup$ I'm a programmer, and this is how I write. It's simply a problem I'm dealing with that I'm curious how to solve. I have a degree in Math and Computer Science, but I was never very good with combinatorics. $\endgroup$ Feb 13, 2015 at 9:18
  • $\begingroup$ The rating distribution is not a bell curve. It can drop below 4 periodically, but the long-term average is between 4 and 5. $\endgroup$ Feb 13, 2015 at 9:21
  • $\begingroup$ David, please make the title of the question more informative. Regards, $\endgroup$
    – Pedro
    Feb 13, 2015 at 9:23

4 Answers 4

1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Is there a typo in the text: vector $b$ and vectors $v$ are not read in the same directions (in $b$, first component is for rate $1$, and in $v^1$ for $5$)? Independently, I have a doubt concerning the generators. The signs of $v_5^1$ and $v_1^1$ are the same; and $v_1^1$ has a non-null value only in $v^1$. Does that mean that, in any vector $w$ generated from $b$, either both $w_1$ and $w_5$ are not larger than $b_1$ and $b_5$, or both not smaller? Suppose that $T=91$ and $b=(0,0,0,4,15)$. How can we generate $w=(0,1,1,4,14)$ which is another possible rating set? Thank you, $\endgroup$
    – borisd
    Feb 13, 2015 at 13:28
  • $\begingroup$ @borisd Regarding order of $v^k$, I don't believe it is reversed; for example I calculate $3-2\cdot 4+5\cdot 1=0$ for the net rating change from $v^1$. However, since each $v^k$ satisfies $\sum_i(6-i)x_i=6\sum_ix_i-\sum_iix_i=0$, it is no coincidence that the vectors are still solutions if the components are reversed. $\endgroup$ Feb 13, 2015 at 20:04
  • $\begingroup$ @borisd As for accessing different solutions via the generators, note that the $v^k$ vectors only give you more solutions with the same $s,T$ values - these are fixed in advanced since the rounding presents some nonlinearity. You can get to these by iterating over $s$ and then iterating over all integer values of $T$ between $\lambda^-s$ and $\lambda^+s$ (which for $s<100$ will always be either none or one integer). Your examples have different $s$ values, $19$ in $b$ and $20$ in $w$. $\endgroup$ Feb 13, 2015 at 20:07
1
$\begingroup$

(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\}\ .$$

$\endgroup$
8
  • $\begingroup$ That's n <= 20 and <= 60% of customers respond. But often n < 10. This is a mushy problem. And it's a real problem. I see the current average rating and I wonder what individual ratings went into it. Given an exact decimal and the fact that all ratings are integers, and the total counts are always fairly small, it seems fairly reasonable to guess at the ratings. $\endgroup$ Feb 13, 2015 at 9:55
  • $\begingroup$ What would this solution look like if you take into account the fact that you need a range $[\lambda-0.005,\lambda+0.005]$ instead of $\lambda$ given the rounding? $\endgroup$ Feb 13, 2015 at 10:02
  • $\begingroup$ @ChristianBlatter: Can you please explain why $20^5$? I would have said $5^{20}$ (5 possibilities for each voter). Thanks, $\endgroup$
    – borisd
    Feb 13, 2015 at 10:14
  • $\begingroup$ @borisd There are only $5$ vectors, each of which contains a number less than $n$ (this is counting how many people voted $5$, how many gave $4$, etc.), so the number of possibilities is bounded by $n^5$. $\endgroup$ Feb 13, 2015 at 10:18
  • $\begingroup$ @MarioCarneiro Thank you. I now see where the $14^5$ come from, but not $\frac{1}{5!}$? $\endgroup$
    – borisd
    Feb 13, 2015 at 10:23
0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Yes, it's that last bit you mention that messes things up and creates a multi-dimensional nightmare. Overall, 70% or more of the ratings are 5s. The rest are usually 4s. Sometimes there will be a lower rating, although they are rare. If you think about all possible combinations, the vast majority are never seen. It's impossible to distinguish any number of 5s, but if there's just one 4, you can actually determine how many ratings there were if it's fairly small (eg. < 20). The more non-5 ratings you get, the more possible solutions there are. But again, for n<20 (usually <10) it's manageable. $\endgroup$ Feb 13, 2015 at 9:49
  • $\begingroup$ Actuaslly the greater the number of posible votes the more difficult it becomes becouse different combination of them can result in same sum. For instance average of votes 5,4,4 is same as average of votes 5,5,3 so you end up with multiple results. So this means that it is practically inposible to calculate the exact number of votes in such scenario. $\endgroup$ Feb 13, 2015 at 10:15
  • $\begingroup$ Yes, but see my two comments above regarding capturing the average rating over time. It helps to resolve this. $\endgroup$ Feb 13, 2015 at 10:19
  • $\begingroup$ FWIW, 4.6 is the bottom-end acceptable long-term average, meaning 92% or more of my ratings must be 5s. The mean rating for the statistical community I'm in is something like 4.65. My long-term average is 4.7, which I'm told is "above average". We don't get to see individual ratings, but we can see the average of ratings given over the past 24 hours, which can be updated at any time. It drives me nuts that my rating bounces around as much as it does, so I'm really curious about ways to correlate it more closely with actual events that are fresh in my mind. $\endgroup$ Feb 13, 2015 at 10:33
0
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ Does this recursive relation on rate sets yield a recursive relation for $|A|$ which does not require keeping track of the rate sets themselves? $\endgroup$ Feb 13, 2015 at 9:32
  • $\begingroup$ This looks nice in theory, but as a programmer, it looks like overkill. How many combinations of 5s, 4s, 3s, 2s and 1s can result in a given average rating of, say, 4.5, with no more than 10 possible ratings -- which you know is probably capped at 60% (or 6) as a real max rating count? I'm not going to start at the minimum and work up, but at the maximum and work down, because I know the majority of ratings will be 5s and 4s most of the time. Again it's not a bell curve. Some days you get eight 5s out of 12 possible ratings, for an average of 5 (which is indistinguishable from one 5). $\endgroup$ Feb 13, 2015 at 9:35
  • $\begingroup$ The question was to generate all possible ratings. They are in exponential number, so no surprise the algorithm does not run in polytime. If you want to get all possible ratings, you cannot use statistical uncertain assumptions? Heuristically, you may still limit the value of $l$ for low rates. If you go top-down, you can still cache the values to fasten the recursion. $\endgroup$
    – borisd
    Feb 13, 2015 at 9:44
  • $\begingroup$ @MarioCarneiro: yes you could proceed in a two pass algorithm. The first one just computes the parameters for which $A(i,r,k)$ is not empty. The second one actually computes the sets, knowing that most of parameters combinations are useless. @ David Schwartz: This can be a start of a solution to the combinatorial explosion? $\endgroup$
    – borisd
    Feb 13, 2015 at 9:51
  • $\begingroup$ Looks like Christian's answer above solves the exponential blowup problem by not counting $(5,5,4)$ and $(4,5,5)$ as distinct (which adds a ${n\choose k}$-type term to the number of solutions). That way it's only a $5$-dimensional space and so the number of lattice points is polynomial. $\endgroup$ Feb 13, 2015 at 9:54

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.