Recommender systems and information retrieval platforms rely on ranking algorithms to present the most relevant items to users, thereby improving engagement and satisfaction. Assessing the quality of these rankings requires reliable evaluation metrics. Among them, Mean Average Precision at cutoff k (MAP@k) is widely used, as it accounts for both the relevance of items and their positions in the list for some groups of users.
It seems obvious that intelligent ranking algorithms should outperform recommendations generated at random. But how can we measure how much better they work? In this article, we have established the expected value and variance of the average accuracy at k (AP@k), as they can be used as a foundation for efficiency criteria for MAP@k. Here, we considered two widely used evaluation models: offline and online, together with corresponding randomization models for them, and calculated the expected value and variance of AP@k in both cases. The numerical study for different scenarios was also performed.
Recommendation systemsInformation retrievalRanking algorithmsAP@kMAP@kEvaluation metricsExpectation and varianceRandom rankings60E0560C0562R0768T05The second author, Tetiana Ianevych, was supported by the Ministry of Education and Science of Ukraine within the grant for the prospective development of the scientific field “Mathematical Sciences and Natural Sciences” at Taras Shevchenko National University of Kyiv.
This paper is dedicated to the 85th anniversary of the birth of Prof. Yuriy Kozachenko.
Introduction
Recommendation systems play a pivotal role in modern digital environments, designed to predict and suggest items such as movies on streaming platforms, products on e-commerce sites, or news articles on media platforms based on users’ preferences and historical interactions. These systems leverage sophisticated algorithms that analyze user behavior, item attributes, and contextual data to provide personalized recommendations, thereby enhancing user satisfaction and engagement.
Ranking algorithmsare fundamental to recommendation systems, as they determine the order in which items are presented to users. These algorithms prioritize relevant items and arrange them in a sequence designed to maximize user engagement and satisfaction.
Metrics that assess the effectiveness of these rankings are essential for evaluating algorithmic performance. Among various evaluation metrics, Average Precision at k (AP@k) plays a crucial role in recommendation systems due to its ability to assess the precision of recommended items up to a specified rank k. It not only accounts for the relevance of the items but also their position in the recommendation list, providing a comprehensive evaluation of ranking effectiveness. A review of this and other relevant metrics is provided in [7, 9], offering a deeper exploration of the evaluation methods.
AP@k is particularly important for evaluations of algorithms developed for scenarios where users are more likely to interact with top-ranked items, like book propositions on Amazon, short videos on YouTube, or news on Google News. While AP@k evaluates the ranking quality for individual users, MAP@k provides an overall measure of the algorithm’s performance across the entire user base, giving a more generalized assessment of the system’s ability to rank relevant items consistently.
There are a variety of different ranking methods, but none of them is the best. The effectiveness of a ranking algorithm depends on the particular problem, the data available, what rank must represent, and what properties are needed. The most well-known so far is the PageRank method used in search engines like Google (for details, see [4, 5] and the references therein).
In this paper, we calculated the closed-form expressions for the expected value and the variance of AP@k under random rankings. Since MAP@k averages user-level AP@k, the expectation of AP@k specifies the random baseline for the metric MAP@k, whereas the variance determines the scale of random fluctuations around that baseline. For a good ranking algorithm, MAP@k is expected to be significantly greater than the expectation of AP@k. This baseline supports principled benchmarking and guides the optimization of recommendation strategies. Together, these basic probabilistic parameters can be used for testing hypotheses on whether the algorithm is substantially better than just random ranking.
The paper is organized as follows. Section 2 introduces two evaluation settings that we consider (offline and online) in connection with corresponding randomization models and explains their practical relevance. Section 3 provides formal definitions of AP@k and MAP@k and clarifies their relationship. Sections 4 and 5 present closed-form expressions for the expectation and variance of AP@k in both offline and online scenarios. Section 6 presents some numerical examples and simulation results and comparative tables that illustrate the particularities of AP@k in several scenarios, whereas Section 7 summarizes the main findings and suggests directions for future research. The proofs of the theorems from the Sections 4 and 5 are placed in the Appendix.
Offline and online evaluation
In the evaluation of recommendation systems, two principal approaches are widely used: offline evaluation and online one. A comprehensive discussion of these methods can be found in [1, 6]. In both these approaches, we restrict ourselves to treating item relevance as binary — classifying items as relevant or not — but they differ in the methodology.
It is important to note that the notion of relevance itself is not universal and is typically defined by the underlying business objective of the system. Depending on the task, relevance may correspond to different user actions, such as clicking on an item, visiting a product page, completing a purchase, or consuming a certain fraction of the content. For instance, in a recommendation system optimized for traffic generation, a click or page visit may be treated as a relevant outcome, whereas in a revenue-oriented setting, relevance may be defined by a completed transaction. Consequently, while AP@k and MAP@k assume a binary relevance indicator, the definition of this indicator is inherently task-dependent and reflects the specific optimization goal of the application.
Offline evaluation relies on historical data, where the relevance of items for each user is known. It is particularly useful when comprehensive, labeled data, such as historical interactions, is available, making it possible to test recommendation algorithms in a controlled environment. In this case, we can design a training set and a test set according to our preferences. The common practice is to group the users who have the same number of relevant items in the list in order to make them homogeneous in some sense and comparable. We can explore several groups with a different number m of relative items in the list.
What if we do not use the advanced ranking algorithms but propose the items to the user randomly? And what does it mean by ‘randomly’? What will the expected value of AP@k be in this case? First of all, we need to define the random experiment that can be utilized under such a scenario. We can consider the experiment in which one random result differs from another only at the places where m relevant elements (no matter which) are located among N available places. It is stochastically equivalent to sampling m items from N with equal probabilities and without replacement (SWOR).
The offline evaluation is easier and reproducible. But it does not always predict online behavior and trends. Therefore, the offline evaluation is usually followed by the online evaluation. Online evaluation attempts to evaluate recommender systems by a method called A/B testing, where a part of users are served by recommender system A and another part of users by recommender system B in real-time mode, and then compare them with each other. We refer the interested reader to [1, 6] for more details on this issue. In A/B testing, one of the systems (i.e., B) can propose the items randomly. With time, all the recommender algorithms degrade, and the level of their degradation is regularly monitored, but instead of conducting an online test with random sorting of recommendations, which is quite costly and leads to reduced user satisfaction, it can be simulated using the randomization model.
We propose a model that also treats item relevance as binary. But it is unreasonable to require a predefined number of relevant items m within a set of N items per user, as was in the offline evaluation framework, since the model will be unrealistic. Instead, it is important to ensure that every participant in the sample testing the recommender system is shown at least k items from the recommendation list. For reliable evaluation in this scenario, two key conditions must be met: the pool of items used to generate the recommendation list must be sufficiently large, and the proportion of relevant items should remain approximately stable across all users in the treated group. In practice, it means that we need to choose users with similar characteristics, like gender or age. This comparison is facilitated by the probability p, which represents the likelihood of each item being relevant. The probability p can be estimated from the historical data. Given this probability, it is possible to calculate the expected value and the variance of the evaluation metric AP@k under random item ranking.
One possible random experiment that can be considered to fit this setting is Bernoulli sampling. It assumes that we have N items, and every item can be either relevant or not, independently of each other, with a probability of being relevant equal to p. This is equivalent to sampling from N items, where m=pN (m is assumed to be natural) with equal probabilities and with replacement (SWR). The number of relevant items for each user under this model is not fixed, but on average it is equal to Np=m.
Average Precision at <italic>k</italic> and Mean Average Precision at <italic>k</italic>
Having established the context of offline and online evaluation, we now turn to the formal definition of the metrics Average Precision at k (AP@k) and Mean Average Precision at k (MAP@k), which are central to this paper. To begin, we first define AP@k for a single user, which serves as the building block for MAP@k.
The Average Precision at k measures the ranking quality of relevant items proposed to one user by averaging precision values at positions where relevant items appear. Formally, it is defined as: AP@k=1k∑i=1kP@i·Ii, where:
k is the length of the recommendation list;
P@i=∑j=1iIji is the precision at position i;
Ii∈{0,1} is a binary indicator, equal to 1 if the item at position i is relevant and 0 otherwise.
In this general form, the denominator k normalizes the metric over the entire recommendation list shown to the user. However, when the total number of relevant items m is smaller than k, a modified normalization factor, min(m,k), should be used: AP@k=1min(m,k)∑i=1kP@i·Ii.
This adjustment ensures that the metric appropriately handles situations where there are fewer relevant items than the length of the recommendation list, avoiding artificially deflated scores. Without this modification, even in the best scenario – where all m relevant items are ranked in the top positions – the AP@k score would never reach 1, because the denominator would be larger than m, preventing the score from reaching its maximum value.
As it was mentioned before, MAP@k aggregates the AP@k values across all users in the dataset and provides a more comprehensive evaluation of the recommendation system, thereby reflecting the system’s overall performance of ranking. Formally, MAP@k is computed as: MAP@k=1|U|∑u∈UAP@ku, where:
U is the set of all users in the dataset;
AP@ku is the AP@k score for user u.
Turning to the interpretation of the MAP@k metric, a high MAP@k value indicates that most users encounter relevant items ranked highly, reflecting an effective recommendation system. Conversely, a low MAP@k suggests that relevant items appear lower, signaling a less efficient algorithm. The metric ranges from 0 to 1, where 1 means all relevant items are within the top-k positions, and 0 means none are included. However, for a comprehensive evaluation, it is essential to compare the MAP@k score with the expected value derived from random recommendation generation. While one might assume that this expected value equals the proportion of relevant items in the collection, this is not the case. As demonstrated by Yves Bestgen in his work [2], the expected average precision for random recommendations is more complex and varies depending on various factors such as the number of relevant items in the list and other characteristics. In the current study, we derive precise formulas for the calculation of random baselines for both random ranking algorithms described above (sampling without and with replacement).
Expectation and variance of AP@k under sampling without replacement for the case of offline ranking evaluation
If we want to determine how much the algorithm outperforms random chance, we can compare MAP@k calculated for the developed ranking algorithm with the expected value of AP@k if randomness is imposed by sampling without replacement. The expected AP@k alone is not sufficient for a comprehensive evaluation, but it provides the crucial baseline against which meaningful improvements can be interpreted. In addition, the variance quantifies the spread of AP@k values around this baseline, completing the picture by indicating the scale of random fluctuations.
We begin with the offline evaluation setting described in Section 2, corresponding to sampling without replacement. In this case, among N items, exactly m are relevant, and one random outcome differs from another only by the positions of the m relevant items in the ranking. Equivalently, the random ranking can be viewed as a uniformly random permutation of all N items, so that the m relevant items are placed at random positions. From the mathematical point of view, this means that for each item j=1,2,…,N we define a binary random variable Ij, with Ij=1 if the item at position j is relevant and Ij=0 otherwise. Furthermore, ∑j=1NIj=m and the random variables I1, I2, ..., IN are not independent.
Under this model, the probability that the j-th item is relevant can be calculated as P(Ij=1)=CN−1m−1CNm=mN.
So, E(Ij)=m/N for every j and the random variable ∑j=1iIj, which counts the number of relevant items among the first i items, follows the Hypergeometric distribution with parameters N, m and i. Moreover E(P@i)=1i∑j=1iE(Ij)=mN,i=1,...,k. In this case, we should compute AP@k according to formula (2), where the normalization is made by min(m,k).
Hereafter, for the identification that the expectations are calculated with respect to different random models, we used different subscripts (SWOR and SWR) in the theorems’ formulation. In the proofs placed in Appendix A, we omit these subscripts to simplify the formulas.
The explicit expressions for the expected value E(AP@k) and the variance Var(AP@k) under the random model corresponding to sampling without replacement (SWOR) are established in the following theorem.
Assume that among N available items, exactly m are relevant for each user and their places are chosen randomly with equal probability by sampling without replacement. Then the expectation and the variance ofAP@kwith respect to all possible random results are equal toESWOR(AP@k)=mN·min(k,m)m−1N−1k+N−mN−1Hk,VarSWOR(AP@k)=1min(k,m)2mN[k(C+2(E−F)+(k−1)G)++Hk(B−2(E−kF))+Hk2·D+Hk2(A−D)],whereA=1−mN−m−1N−13−2m−2N−2−mN2−m−1N−1;B=m−1N−131−m−2N−2−2mN1−m−1N−1;C=m−1N−1m−2N−2−m(m−1)N(N−1);D=m−1N−12−5m−2N−2+3(m−2)(m−3)(N−2)(N−3)−mN1−m−1N−12;E=m−1N−13m−2N−21−m−3N−3−mN1−m−1N−1;F=m−1N−1m−2N−21−m−3N−3−mN1−m−1N−1;G=m−1N−1(m−2)(m−3)(N−2)(N−3)−mNm−1N−1;Hk=∑i=1k1i;Hk(2)=∑i=1k1i2.
The valuesHk=∑i=1k1iare, actually, the partial sums of the harmonic series. They were named ‘harmonic’ numbers in 1968 by Donald Knuth [8]. For quite big k, the well-known formula (see [3])Hk=lnk+γ+12k−εk,can be used. Hereγ≈0.5772is the Euler–Mascheroni constant and0≤εk≤1/8k2which tends to 0 ask→∞.
For small k, the valuesHkandHk(2)can be calculated exactly by ordinary summation.
Expectation and variance of AP@k under sampling with replacement in case of the online ranking evaluation
We now turn to the online evaluation setting described in Section 2. Here, we assume that each item is relevant to a user with a constant probability p. The randomness can be modeled as a sequence of independent Bernoulli trials, or equivalently, as sampling with replacement (SWR), where each item has probability p of being sampled. In this case, the decision whether a recommendation is relevant is assumed to be independent for each item. Moreover, we assume a uniform relevance probability p for all recommendations and all users. These probabilistic assumptions differ from the offline case and lead to distinct formulas for the expectation and variance of AP@k.
From a mathematical point of view, this means that for each recommendation j=1,2,...,N, we define the random variables Ij=1 if it is relevant and Ij=0 otherwise, as in the previous section. But here the random variables I1, I2, ..., IN are independent with mean E(Ij)=p and variance Var(Ij)=p(1−p), where p is assumed to be known. Of course, this assumption is quite strong and can be applied only when the users are relatively similar (homogeneous), as described in Section 2 for the online evaluation scenario.
Under these assumptions and notations, we have the following: P@i=1i∑j=1iIj,E(P@i)=1i∑j=1iE(Ij)=p,andAP@k=1k∑i=1kP@i·Ii.
The basic benchmarking characteristics for MAP@k under random recommendations corresponding to the sampling with replacement are presented in the following theorem.
If, for each user, every item is assumed to be independently relevant with constant probability p and the places for the relevant items in the list of N items are chosen using sampling with replacement with probability p, then the expectation and the variance ofAP@kare equal toESWR(AP@k)=pp+1−p1kHk;VarSWR(AP@k)=5k·p3(1−p)+1k2·p(1−p)p(1−2p)(3Hk+Hk2)+(1−p)(1−3p)Hk2.HereHk=∑i=1k1iis the k-th harmonic number andHk2=∑i=1k1i2is the k-th partial sum of the 2nd order harmonic series as well as in Theorem1.
Numerical examples and simulations results
Before presenting some practical results, it is helpful to summarize the key differences in the formulas for the offline and online settings. In the offline case, the distribution of AP@k depends on the total number of items N, the number of relevant items m, and the cut-off k that specifies how many top-ranked positions are taken into account. This reflects the fact that evaluation is performed on a finite set of items, where exactly m out of N are relevant and their positions in the ranking determine the outcome. In the online setting, by contrast, the parameter N does not appear in the formulas, since evaluation is restricted to the top-k recommendations and each of them is modeled as an independent Bernoulli trial with relevance probability p. This makes the outcome depend only on k and p, regardless of the overall size of the candidate pool, which in practice may be very large. Conceptually, the probability p plays a role analogous to the ratio m/N in the offline case: while offline evaluation fixes the proportion of relevant items deterministically, online evaluation assumes it probabilistically.
To cover a representative range of conditions, N=50 is fixed, and several choices of m and k are examined. The half-density case (m=25) with varying cut-offs illustrates the situations m>k, m=k, and m<k. Lower prevalences (m=10 and m=2) are also included along with a high-prevalence setting (m=35, corresponding to p>0.5). These scenarios span the spectrum from very sparse to very dense relevance distributions, thereby testing the formulas under diverse conditions. The selected configurations are summarized in Table 1.
Examined scenarios
Scenario
Offline:(N,m)
Online:p
k
Characteristic
A1
(50, 25)
0.50
5
m>k, balanced case (50% relevant)
A2
(50, 25)
0.50
25
m=k, balanced case (50% relevant)
A3
(50, 25)
0.50
40
m<k, balanced case (50% relevant)
B
(50, 10)
0.20
20
moderate proportion of relevant items
C
(50, 2)
0.04
20
very low proportion of relevant items
D
(50, 35)
0.70
20
high proportion of relevant items (p>0.5)
Table 2 reports the theoretical (derived from the formulas in Sections 4 and 5) means and variances of AP@k for the selected scenarios. The offline and online settings are placed side by side, allowing examination of their behavior under comparable conditions and observation of where the two randomization schemes produce similar outcomes and where differences emerge.
Values of expectation and variance for AP@k for scenarios from Table 1
Scenario
SWOR Expectation
SWR Expectation
SWOR Variance
SWR Variance
A1
0.36139
0.36416
0.05464
0.05884
A2
0.28387
0.28816
0.00735
0.01234
A3
0.43550
0.27674
0.00699
0.00775
B
0.13221
0.06878
0.00786
0.00294
C
0.07865
0.00851
0.01563
0.00023
D
0.52426
0.52778
0.01502
0.02195
As seen in Table 2, the comparison between offline (SWOR) and online (SWR) shows no uniform pattern: in some scenarios the two models behave very similarly, while in others their outcomes diverge noticeably. The observed differences reflect the min(m,k) normalization in offline evaluation and the independence structure of online sampling. Together, these results provide a clear basis for interpreting MAP@k under the random rankings.
In addition to the values reported in Table 2, Figures 1 and 2 show the simulated distributions of AP@k for two representative scenarios. These examples illustrate how SWOR and SWR can differ not only in their means but also in their variability.
Histogram of AP@k values for Scenario A3 (N=50,m=25,p=0.5,k=40). The SWOR distribution (blue) is shifted to higher values compared to SWR (orange), reflecting normalization by min(m,k) in the offline case.
Histogram of AP@k values for Scenario C (N=50,m=2,p=0.04,k=20). The SWR distribution (orange) is tightly concentrated around zero, while the SWOR distribution (blue) shows wider variability due to the finite number of relevant items.
In Scenario A3 (m<k), the distributions are shifted relative to each other: the offline case yields systematically higher values due to normalization by min(m,k), while the online case, which models relevance probabilistically, results in lower means.
In Scenario C (very low prevalence), the contrast lies in variability. The SWR distribution is sharply concentrated, reflecting that almost always no relevant items appear in the top-k, whereas the SWOR distribution remains wider because the fixed number of relevant items can still occupy different positions in the ranking.
Conclusions and discussion
The results obtained clarify what levels of AP@k are expected under random ranking and how much variability surrounds them. From a practical standpoint, these findings offer two key insights. First, the expected value of AP@k serves as a clear reference point against which observed performance can be compared. Second, the variance quantifies the random fluctuations around this reference, helping to distinguish genuine improvements from chance outcomes. Together, expectation and variance can be used to build the statistical test to check the hypothesis on whether the studied new ranking algorithm is significantly better than a random one or not by comparing the empirical MAP@k obtained from offline or online evaluation procedure with E(AP@k). But this task is left for future research. It will also be interesting to extend this analysis to other related metrics and investigate how statistical testing frameworks can build on these results for a robust comparison of ranking systems.
Appendix. Proofs of Theorem <xref rid="x1-4001r-1">1</xref> and <xref rid="x1-5001r-2">2</xref>
In the proofs, we need some technical results, which we formulate as a lemma.
For anyk≥1
∑i=1k−1∑l=i+1k1i=k(Hk−1);
∑i=1k−1∑l=i+1k1l=k−∑l=1k1l=k−Hk;
∑i=1k−1∑l=i+1k1i·l=12(Hk2−Hk2),
whereHk=∑i=1k1iis a standard harmonic number;Hk2=∑i=1k1i2is the k-th partial sum of the 2nd order harmonic series.
(ii) ∑i=1k−1∑l=i+1k1l=∑l=2k∑i=1l−11l=∑l=2kl−1l=k−1−(∑l=1k1l−1)=k−∑l=1k1l=k−Hk. (iii) For the calculation of the last equality, we can use the fact that for any finite collection of numbers {ail}i,l=1k, such that ail=ali if i≠l∑i=1k−1∑l=1+1kail=12(∑i=1k∑l=1kail−∑i=1kaii). So, ∑i=1k−1∑l=i+1k1i·l=12(∑i=1k∑l=i+1k1i·l−∑i=1k1i2)=12((∑i=1k1i)2−∑i=1k1i2)=12(Hk2−Hk2). □
For the expectation.E(AP@k)=1min(m,k)∑i=1kE(P@i·Ii). Let’s first calculate the following: E(P@i·Ii)=E(E(P@i·Ii|Ii))==E(P@i·Ii|Ii=1)P{Ii=1}+E(P@i·Ii|Ii=0)P{Ii=0}==E(P@i|Ii=1)·mN=1i((i−1)m−1N−1+1)·mN, since, if we know that Ii=1, then P@i is distributed as 1i·(Hypergeometric(N−1,m−1,i−1)+1). Therefore, E(AP@k)=1min(m,k)·mN∑i=1k((1−1i)m−1N−1+1i)==1min(m,k)·mNk·m−1N−1+(1−m−1N−1)∑i=1k1i.
For the variance.
Since Var(AP@k)=Var1k∑i=1kP@i·Ii=1k2∑i=1k∑l=1kcil, we need to calculate all the coefficient cil taking into account that for every i≠lcil=cli=cov(P@i·Ii,P@l·Il) and for all icii=Var(P@i·Ii).
Let us calculate them step by step, starting from the coefficients cii, i=1,2,...,k. Since in this case the random variables I1, ..., In are not independent, it is worth applying formulas that use conditional expectations. In particular, for two random variables X and Y, we can calculate the variance by the formula: Var(X)=E(Var(X∣Y))+Var(E(X∣Y)). So, cii=Var(P@i·Ii)=E(Var(P@i·Ii∣Ii)+Var(E(P@i·Ii∣Ii))=t1+t2. If Ii=0, then P@i·Ii=0, and E(P@i·Ii∣Ii=0)=0, Var(P@i·Ii∣Ii=0)=0.
If Ii=1, then E(P@i·Ii∣Ii=1)=1i(i−1)m−1N−1+1 and Var(P@i·Ii∣Ii=1)=E(P@i·Ii)2∣Ii=1−(E(P@i·Ii∣Ii=1))2.
First of all E((P@i·Ii)2∣Ii=1)=E1i∑j=1i−1IjIi+Ii22∣Ii=1==1i2E1+2∑j=1i−1Ij+∑j=1i−1Ij2∣Ii=1==1i2E1+2∑j=1i−1Ij+∑j=1i−1Ij2+∑∑j≠rIjIr∣Ii=1==1i21+3∑j=1i−1E(Ij∣Ii=1)+∑∑j≠rE(IjIr∣Ii=1)==1i21+3(i−1)·m−1N−1+(i−1)(i−2)(m−1)(m−2)(N−1)(N−2), as E(Ij∣Ii=1)=CN−2m−2CN−1m−1=m−1N−1 and E(IjIr∣Ii=1)=CN−3m−3CN−1m−1=(m−1)(m−2)(N−1)(N−2).
Then Var(P@i·Ii∣Ii=1)=1i21+3(i−1)·m−1N−1+(i−1)(i−2)(m−1)(m−2)(N−1)(N−2)−1i2(i−1)m−1N−1+12 and thus we obtain the first term in (6): t1=E(Var(P@i·Ii∣Ii))=Var(P@i·Ii∣Ii=1)·mN==mN·1i21+3(i−1)·m−1N−1+(i−1)(i−2)(m−1)(m−2)(N−1)(N−2)−((i−1)m−1N−1+1)2.
Secondly, if Ii=1 the random variable E(P@i·Ii∣Ii) takes the value 1i·((i−1)m−1N−1+1) with probability mN and 0 otherwise. Therefore, t2=Var(E(P@i·Ii∣Ii))=E((E(P@i·Ii∣Ii))2)−(E(E(P@i·Ii∣Ii)))2==1i2(i−1)m−1N−1+12·mN−1i2(i−1)m−1N−1+12·mN2==1i2(i−1)m−1N−1+12·mN1−mN. So, finally, we have the following expression after collecting the coefficients near 1ir,r=0,1,2. cii=Var(P@i·Ii)=t1+t2==mN·1i21+3(i−1)·m−1N−1+(i−1)(i−2)(m−1)(m−2)(N−1)(N−2)−−mN·1i2(i−1)m−1N−1+12+1i2(i−1)m−1N−1+12·mN1−mN==mN1−mN−m−1N−13−2m−2N−2−mN2−m−1N−11i2++mN(m−1)(N−1)31−m−2N−2−2mN1−m−1N−11i++mN(m−1)(N−1)(m−2)(N−2)−m(m−1)N(N−1)2. (ii) For all such i and l that 1<i<l≤kcil=cli=cov(P@i·Ii,P@l·Il)=E(P@i·Ii·P@l·Il)−E(P@i·Ii)·E(P@l·Il). Here, we can also use the conditional expectation for calculation E(P@iIi·P@lIl)=E(E(P@iIi·P@lIl∣IiIl))=E(P@iIi·P@lIl∣IiIl=1)P(IiIl=1). If IiIl=1, then we know that the items in the ith and lth places are relevant, so we should take into account the possible arrangements of the other m−2 relevant items between the N−2 places. So, P(IiIl=1)=CN−2m−2CNm=m(m−1)N(N−1). And then E(P@i·Ii·P@l·Il∣IiIl=1)=E1i∑j=1iIj·1l∑r=1lIr∣IiIl=1=1i·lE1+∑j=1i−1Ij1+∑r=1i−1Ir+∑r=i+1l−1Ir+1∣IiIl=1=1i·lE2+4∑r=1i−1Ir+∑r=i+1l−1Ir+2∑j=1i−r∑r=j+1i−1IjIr+∑j=1i−1∑r=i+1l−1IjIr∣IiIl=1=1i·l2+4(i−1)m−2N−2+(l−1−i)m−2N−2+(i−1)(i−2)(m−2)(m−3)(N−2)(N−3)+(i−1)(l−1−i)(m−2)(m−3)(N−2)(N−3)==1i·l2+m−2N−2(3i−5+l)+(m−2)(m−3)(N−2)(N−3)(i−1)(l−3). So, after putting all the components together and doing some algebra, we obtain cil=m(m−1)N(N−1)1i·l2−5m−2N−2+i·3m−2N−2+lm−2N−2+i·l(m−2)(m−3)(N−2)(N−3)−−i·3(m−2)(m−3)(N−2)(N−3)−l(m−2)(m−3)(N−2)(N−3)+3(m−2)(m−3)(N−2)(N−3)−−mN21i·l1+(i−1)m−1N−11+(l−1)m−1N−1==mN1i·lm−1N−12−5m−2N−2+3(m−2)(m−3)(N−2)(N−3)−mN1−m−1N−12++im−1N−13m−2N−21−m−3N−3−mN1−m−1N−1++lm−1N−1m−2N−21−m−3N−3−mN1−m−1N−1++i·lm−1N−1(m−2)(m−3)(N−2)(N−3)−mNm−1N−1. Using the notations from the Theorem 1 statement and M=min(m,k) for shortness, along with results from Lemma 1, we’ll get: VarSWOR(AP@k)=1M2(∑i=1kcii+2∑i=1k−1∑l=i+1kcil)==1M2[∑i=1kmN(Ai2+Bi+C)+2∑i=1k−1∑l=i+1kmN(Di·l+El+Fi+G)]==1M2mN[A·Hk2+B·Hk+kC+D(Hk2−Hk2)++2Ek(Hk−1)+2F(k−Hk)+Gk(k−1)]==1M2mN[k[C+2(E−F)+(k−1)G]+Hk(B−2(E−kF))++Hk2·D+Hk2(A−D)]. This completes the proof. □
For the expectation.
If we examine the model of relevance of proposals that corresponds to sampling with replacement with a fixed probability of success p, then we can use 1k for normalization purposes, since in this case it is possible that all k items can be relevant. So, by the definition of AP@k, we have E(AP@k)=E(1k∑i=1kP@i·Ii)=1k∑i=1kE(1i∑j=1iIj·Ii)=1k∑i=1k(1i∑j=1iE(Ij·Ii)). For all j≠i, E(Ij·Ii)=E(Ij)·E(Ii)=p2, as these random variables are independent. If j=i, then E(Ii2)=E(Ii)=P{Ii=1}=p. So, E(AP@k)=1k∑i=1k1i(∑j=1i−1E(Ij·Ii)+E(Ii))=1k∑i=1k1i((i−1)p2+p)==pk∑i=1k(p+(1−p)1i)=p2+p(1−p)1k∑i=1k1i.
For the variance. As before, Var(AP@k)=Var1k∑i=1kP@i·Ii=1k2∑i=1k∑l=1kcil, and we need to calculate the coefficient cil taking into account that for every i≠lcil=cli=cov(P@i·Ii,P@l·Il) and for all icii=Var(P@i·Ii).
Let us calculate them again one by one.
(i) For i=1,2,...,kcii=Var1i∑j=1iIjIi=1i2Var∑j=1i−1IjIi+Ii2==1i2VarIi1+∑j=1i−1Ij. Here, the random variables Ii and 1+∑j=1i−1Ij are independent. The variance of the product of two independent random variables X and Y can be calculated using the following rule: Var(X·Y)=E(X2)E(Y2)−(E(X))2(E(Y))2. As far as E(Ii2)=E(Ii)=p,
E1+∑j=1i−1Ij=1+∑j=1i−1E(Ij)=1+(i−1)p, and E1+∑j=1i−1Ij2=E1+2∑j=1i−1Ij+∑j=1i−1Ij2==E1+2∑j=1i−1Ij+∑j=1i−1Ij2+2∑j=1i−2∑r=j+1i−1IjIr==1+3(i−1)p+(i−1)(i−2)p2, then cii=1i2VarIi·1+∑j=1i−1Ij==1i2EIi2E1+∑j=1i−1Ij2−E(Ii)2E1+∑j=1i−1Ij2==1i2p1+3(i−1)p+(i−1)(i−2)p2−p21+(i−1)p2==p(1−p)p2+p(3−2p)1i+(1−3p+p2)1i2. (ii) For all i and l for which 1<i<l≤kcil=cli=cov(Ii·P@i,Il·P@l)=E(Ii·P@i·Il·P@l)−E(Ii·P@i)·E(Il·P@l). Here E(Ii·P@i·Il·P@l)=1i·lE(Ii(1+∑j=1i−1Ij)·Il(1+∑r=1l−1Ir))=1i·lE(IiIl(1+∑j=1i−1Ij)(1+∑r=1i−1Ir+Ii+∑r=i+1l−1Ir))=1i·lE(IiIl(1+∑j=1i−1Ij)2+Ii2Il(1+∑j=1i−1Ij)+IiIl(1+∑j=1i−1Ij)(∑r=i+1l−1Ir))=p2i·l(2+(3i−5+l)p+(i−1)(l−3)p2). Therefore, cil=p2i·l(2+(3i−5+l)p+(i−1)(l−3)p2−(1+(i−1)p)(1+(l−1)p))==1lp2(1−p)((1−2p)1i+2p). Summing up all the coefficients {cil}i,l=1k we obtain ∑i=1k∑l=1kcil=∑i=1kcii+2∑i=1k−1∑l=i+1kcil==∑i=1k(p(1−p)(p2+p(3−2p)1i+(1−3p+p2)1i2))++2∑i=1k−1∑l=i+1kp2(1−p)((1−2p)1i·l+2p1l)==kp3(1−p)+p2(3−2p)∑i=1k1i+p(1−3p+p2)∑i=1k1i2++2p2(1−p)(1−2p)∑i=1k−1∑l=i+1k1i·l+4p3(1−p)∑i=1k−1∑l=i+1k1l.
Using the results from Lemma 1 we, finally, get Var(AP@k)=1k2(∑i=1kcii+2∑i=1k−1∑l=i+1kcil)==1k2(p(1−p)∑i=1k(p2+p(3−2p)1i+(1−3p+p2)1i2)++2p2(1−p)∑i=1k−1∑l=i+1k((1−2p)1i·l+2p1l))==5kp3(1−p)+1k2p(1−p)p(1−2p)(3Hk+Hk2)+(1−p)(1−3p)Hk(2). □
Acknowledgments
The authors thank anonymous referees for their careful reading of the first version of the manuscript and valuable remarks that helped to significantly improve the paper.
ReferencesAgarwal, D.K., Chen, B.-C.: Evaluation Methods pp. 55–78. Cambridge University Press (2016)Bestgen, Y.: Exact expected average precision of the random baseline for system evaluation. The Prague Bulletin of Mathematical Linguistics103, 131–138 (2015). https://doi.org/10.1515/pralin-2015-0007Boas, R.P., Wrench, J.W.: Partial sums of the harmonic series. The American Mathematical Monthly78(8), 864–870 (1971). MR0289994. https://doi.org/10.2307/2316476Brin, S., Page, L.: The anatomy of a large-scale hypertextual web search engine. In: Proceedings of the Seventh International Conference on World Wide Web, pp. 107–117. Elsevier Science Publishers B. V. (1998). https://snap.stanford.edu/class/cs224w-readings/Brin98Anatomy.pdfEngström, C., Silvestrov, S.: Pagerank for networks, graphs and markov chains. Theory of Probability and Mathematical Statistics96, 61–83 (2017). MR3666872. https://doi.org/10.1090/tpms/1034Gebremeskel, G.G., de Vries, A.P.: Recommender systems evaluations: Offline, online, time and a/a test. In: Balog, K., Cappellato L, F.N.M.C. (eds.) Working Notes of CLEF 2016 – Conference and Labs of the Evaluation Forum. CEUR Workshop Proceedings, vol. 1609, pp. 642–656 (2016). https://ceur-ws.org/Vol-1609/16090642.pdfJadon, A., Patil, A.: A Comprehensive Survey of Evaluation Techniques for Recommendation Systems (2024). https://arxiv.org/abs/2312.16015Knuth, D.E.: Harmonic numbers1st edn. pp. 73–78. Addison-Wesley (1968)Valcarce, D., Bellogín, A., Parapar, J., Castells, P.: Assessing ranking metrics in top-n recommendation. Information Retrieval Journal23(4), 411–448 (2020). https://doi.org/10.1007/s10791-020-09377-x