bounds)estimated by the existing results can be arbitrarily is no larger than large depending on either the number of groups [9],the M 1 number of levels [10],or the parameter of the Zipf distribution K'(1- N1+K证 (9) [13].It is remarkable that such a simple coded caching N scheme,with a very simple choice of Ni,can achieve such a Now,suppose that the individual cache size M is much smaller strong performance guarantee,independently of the popularity than Ni,and the global cache size K'M is much larger than distribution. N(note that this is precisely the regime where coded caching As we mentioned earlier,although both our lower bound and will be most helpful[7).Then,we have 1-÷≈1and achievable bound have some similarity to those in [13],our 1+MM.Thus,the expression in (9)is approximately lower bound is sharper in the order sense because it accounts equal to N/M.The significance of this observation is that this for the contribution of unpopular files,and our achievable approximated expression is independent of K.In other words, bound is also tighter in the order sense because it divides in a suitable regime of interest,the exact popularity of the the files into 3 groups under some parameter settings.We "popular files"does not seem to matter!It is then plausible to believe that such difference is the main reason why we can argue that,even when we reduce the popularity values to attain constant-factor performance guarantees independent of in System 2,there is no substantial change in the lower-bound the popularity distribution,while the performance gap in [13] performance.Of course,this argument needs to be carefully only holds when the file popularity follows a Zipf distribution made.Further,we have to account for not only popular files, and when the system sizes approach infinity,and even then the but also unpopular files.The proofs in the next section will performance gap in [13]still depends on the parameter a of make this intuition precise. Zipf distribution(which may approach infinity as a approaches 1).A brief comparison with [13]is presented in Table I. IV.LOWER BOUND ON THE EXPECTED RATE We also note that,for certain ranges of the exponent a of the Zipf distributions,the performance characterization in [13] In this section,we present the proof of Theorem 1,i.e.,the for RLFU may be tighter than the 55 factor reported in(8). lower bound. Further,both our achievable scheme and RLFU are special The proof consists of two parts.Subsections A-C focus on cases of the larger class of RAP-GCC schemes reported in popular files 1 to Ni,and prove the part that R(K,F,P)> [13].Thus,the results in [13]and in this paper combined (N-M).where Mr =max{M,3).This proof is provide a more complete characterization of the performance composed of 5 steps.From the first step to the fourth one, guarantees for coded caching schemes across both Zipf and we map the original system into a series of reduced systems. non-Zipf distributions. whose information-theoretical rate is strictly smaller than previous ones.Then,we bound the rate needed for popular files in the fourth step.We note that the ideas used in the A.Main Intuition 1st to 4th reduction steps are similar to [9][13].In the fifth step,we introduce a novel "merging"technique in Subsection Before we present the proofs for these main results,we D to account for the unpopular files and prove the part that would like to illustrate the main intuition behind.First,con- R(KF,P)(N+N2-M).Finally,in Subsection sider only the "popular files"1 to N.i.e.,assuming that the E,we deal with the case when N+N2<M,and establish unpopular files N+1 to N are removed.Let us refer to the second term in(6).A brief summary of the constructed this system as "System 1".In our proof,we will consider systems are presented in Table II.As we discussed earlier, an alternate system where the popularity of all popular files while some of the techniques for quantifying the impact of is reduced toWe will refer to this alterate system 1 popular files are similar to [913],our treatment of unpopular as "System 2"(see Section IV-A).Intuitively,the average files is new and is the key reason for the sharper constant- transmission rate in System 2 is no larger than that in System factor characterization in our paper. 1.Further,since all files are with the same popularity in System 2,the average-case and the worst-case performance will not differ too much [9].Thus,one can then use System A.Reduction Steps I 2 2 to derive a lower bound on the average transmission rate, Recall that the set of files is given byF=[F1,F2,...,F} and compare it with an upper bound attained by an achievable and their popularity distribution is given by p scheme pi,p2,..,PN).Next,we will compare to a series of reduced However,the potential problem of this argument is that, systems with different sets of files and popularity distributions. when we reduce the popularity of all popular files to i. Again,let N be the integer defined in Theorem 1. some popularity values could be reduced by several orders of In the first constructed system,the set of files is given by magnitude.It is then unclear why the lower bound derived F={Fo,F1,F2,...,FN},where Fo denotes the empty file, from System 2 is still a reasonable lower bound for System which is introduced for ease of presentation.Its correspond- 1.The intuition behind this insensitivity can be explained as ing popularity distribution is P1={po,P1,p2,...,PN}and follows.Suppose that there are Kusers in System 1 that po-1-P In other words,we replace all unpopular request any of the popular files.Then,according to the result files FN+1,...,FN in the original system by the empty file in [7],the worst-case transmission rate to serve these K'users Fo,and reassign their popularity all to Fo.Intuitively,the6 bounds) estimated by the existing results can be arbitrarily large depending on either the number of groups [9], the number of levels [10], or the parameter of the Zipf distribution [13]. It is remarkable that such a simple coded caching scheme, with a very simple choice of N1, can achieve such a strong performance guarantee, independently of the popularity distribution. As we mentioned earlier, although both our lower bound and achievable bound have some similarity to those in [13], our lower bound is sharper in the order sense because it accounts for the contribution of unpopular files, and our achievable bound is also tighter in the order sense because it divides the files into 3 groups under some parameter settings. We believe that such difference is the main reason why we can attain constant-factor performance guarantees independent of the popularity distribution, while the performance gap in [13] only holds when the file popularity follows a Zipf distribution and when the system sizes approach infinity, and even then the performance gap in [13] still depends on the parameter α of Zipf distribution (which may approach infinity as α approaches 1). A brief comparison with [13] is presented in Table I. We also note that, for certain ranges of the exponent α of the Zipf distributions, the performance characterization in [13] for RLFU may be tighter than the 55 factor reported in (8). Further, both our achievable scheme and RLFU are special cases of the larger class of RAP-GCC schemes reported in [13]. Thus, the results in [13] and in this paper combined provide a more complete characterization of the performance guarantees for coded caching schemes across both Zipf and non-Zipf distributions. A. Main Intuition Before we present the proofs for these main results, we would like to illustrate the main intuition behind. First, con￾sider only the “popular files” 1 to N1, i.e., assuming that the unpopular files N1 + 1 to N are removed. Let us refer to this system as “System 1”. In our proof, we will consider an alternate system where the popularity of all popular files is reduced to 1 KMr . We will refer to this alternate system as “System 2” (see Section IV-A). Intuitively, the average transmission rate in System 2 is no larger than that in System 1. Further, since all files are with the same popularity in System 2, the average-case and the worst-case performance will not differ too much [9]. Thus, one can then use System 2 to derive a lower bound on the average transmission rate, and compare it with an upper bound attained by an achievable scheme. However, the potential problem of this argument is that, when we reduce the popularity of all popular files to 1 KMr , some popularity values could be reduced by several orders of magnitude. It is then unclear why the lower bound derived from System 2 is still a reasonable lower bound for System 1. The intuition behind this insensitivity can be explained as follows. Suppose that there are K′ users in System 1 that request any of the popular files. Then, according to the result in [7], the worst-case transmission rate to serve these K′ users is no larger than K′ (1 − M N1 ) 1 1 + K′M N1 . (9) Now, suppose that the individual cache size M is much smaller than N1, and the global cache size K′M is much larger than N1 (note that this is precisely the regime where coded caching will be most helpful [7]). Then, we have 1 − M N1 ≈ 1 and 1+ K′M N1 ≈ K′M N1 . Thus, the expression in (9) is approximately equal to N1/M. The significance of this observation is that this approximated expression is independent of K′ . In other words, in a suitable regime of interest, the exact popularity of the “popular files” does not seem to matter! It is then plausible to argue that, even when we reduce the popularity values to 1 KMr in System 2, there is no substantial change in the lower-bound performance. Of course, this argument needs to be carefully made. Further, we have to account for not only popular files, but also unpopular files. The proofs in the next section will make this intuition precise. IV. LOWER BOUND ON THE EXPECTED RATE In this section, we present the proof of Theorem 1, i.e., the lower bound. The proof consists of two parts. Subsections A-C focus on popular files 1 to N1, and prove the part that R(K, F,P) ≥ 1 11Mr (N1 − M), where Mr = max{M, 3}. This proof is composed of 5 steps. From the first step to the fourth one, we map the original system into a series of reduced systems, whose information-theoretical rate is strictly smaller than previous ones. Then, we bound the rate needed for popular files in the fourth step. We note that the ideas used in the 1st to 4th reduction steps are similar to [9][13]. In the fifth step, we introduce a novel “merging” technique in Subsection D to account for the unpopular files and prove the part that R(K, F,P) ≥ 1 11Mr (N1 + N2 − M). Finally, in Subsection E, we deal with the case when N1 + N2 ≤ M, and establish the second term in (6). A brief summary of the constructed systems are presented in Table II. As we discussed earlier, while some of the techniques for quantifying the impact of popular files are similar to [9][13], our treatment of unpopular files is new and is the key reason for the sharper constant￾factor characterization in our paper. A. Reduction Steps 1 & 2 Recall that the set of files is given by F = {F1, F2, ..., FN } and their popularity distribution is given by P = {p1, p2, ..., pN }. Next, we will compare to a series of reduced systems with different sets of files and popularity distributions. Again, let N1 be the integer defined in Theorem 1. In the first constructed system, the set of files is given by F1 = {F0, F1, F2, ..., FN1 }, where F0 denotes the empty file, which is introduced for ease of presentation. Its correspond￾ing popularity distribution is P1 = {p0, p1, p2, ..., pN1 } and p0 = 1 − PN1 i=1 pi . In other words, we replace all unpopular files FN1+1, ..., FN in the original system by the empty file F0, and reassign their popularity all to F0. Intuitively, the