11 less cache and lower transmission rate)to serve the second system because there is less "diversity".This statement is D.Lower Bound Accounting for Both Popular Unpopular made precise below. Files Lemma 8:Let R(K.71.1)be the minimum expected rate required to meet the requests by K users,each of which The earlier proof only considers the more "popular"files, randomly requests a file in 7 according to the popularity i.e.,files with popularity larger than a threshold.Now we distribution 21.Let R(K,72,22)be defined similarly for 22 will move our attention to the unpopular files and prove We have the first term in the lower bound 6,i.e.,R(K,F,P)> N+N2-M]+To the best of our knowledge,this R(K,Ti,1)>R(K,T,Q2). (30) treatment of unpopular files has not been reported in the Proof:The request set for(K,T1,Q1)is W(K,T1,Q1)= literature.Intuitively,depending on the system setting,the Wi},where Wi={fi,fi2,...,fik}and fij E Ti.We first lower bound may be dominated by either the popular files construct a mapping from W(K,7i,21)to W(K,72,22). or the unpopular files.Thus,we believe that our capability to For every request Wi e W(K,71,21),we map it to a quantify the impact of unpopular files is the key reason that request WiE W(K,T2,Q2)as follows.If file T-1 or T in we can obtain the improved constant-factor characterization in Ti is requested in Wi.we replace it by T+1. this paper,even in non-asymptotic settings. For a cache placement and transmission scheme suppose Interestingly,readers will see soon that we will re-apply that each user can retrieve the file requested in Wi with rate the results for System 2 constructed in Section IV.A.Recall ra(K,Wi).Using the same 3,with the replacement of T+ that in System 2 all users either request one of the non-empty for Ti-1 or Tt in both cache placement and transmissions, files with a common popularity that is no less than 1/K Mr,or the rate rs(K,Wi)must be able to satisfy the request of W:. request the empty file.For the unpopular files,their popularity Therefore,we have is lower than 1/KM,,and hence we cannot directly use (31) the results for System 2.However,next we introduce a new T(K,W)≥T(K,W). "merging"idea that will eventually allow us to re-apply the Further,if Wi follows the distribution with which patterns results for System 2.Specifically,we will merge several are requested in W(K,T1,1),W;will follow the distribution unpopular files into one file,so that the popularity of the new with which patterns are requested in W(K,72,22).To see file is no less than 1/KMr.We will show that this merging this,consider any request pattern [f1,...,fK}.Fix a user k. step will only lower the achievable rate for serving unpopular If f T+1,the probability that user k requests fi in the files.Thus,in the end we obtain a new system similar to mapped request pattern W is exactly the probability that user System 2,from which a lower bound for the achievable rate k requests fk in W(K,72,Q2).If fk=T+1,note that user of the original system can be derived.The detail analysis is k requesting T+1 in W:corresponds to either Ti or T as follows. being requested in Wi.Hence,the probability that user k in Recall that the original set of files is F.and the mapped request pattern W requests file T is equal to the corresponding popularity distribution is P. P+p-1=pt+1,which is also the same as the probability that Consider another system,where the set of files is user k requests T+1 in W(K,72,22).Finally,note that the F3={Fo,F1,...,FN,FN:+1,FN+2,...,FN}(recall that Fo probability with which a pattern is requested is the product is again the empty file).The corresponding popularity dis- of the probability that each file in the pattern is requested tribution is Ps =(poKKAPN:+1,PN+2PN 1 by the corresponding user.Therefore,W must have the same wherep%=1-点∑M+1P.In other words,we N. distribution as in system W(K,72,2).Thus,by the coupling decrease the popularity of files F1,F2,...,FN,in the original method [19].we must have system to Following exactly the same way as the proof Rs(K,Ti,Q1)>Rs(K,T2,Q2) (32) of Lemma 2,we can prove that The results of this lemma then follows. 0 R(K,F,P)≥R(K,F3,P3) (29) Next,we create a new system (K,F4,P)originated from (K,F3,P3),by merging multiple files in F3 to a new file in Again,we will perform a series of further reductions and F4(described below)and combining their popularity(similar finally construct a system with a smaller rate,which can utilize to the mapping from i to 2).We denote this new file the results in previous analysis of"System 2". set asF={Fo,F1,...,FN,Vi,...,VNa}and the popularity To proceed,we need the lemma below.Denote a file set distribution as P=vo,RMRM,v1,v2,UN).Here, by Ti =[T1,T2,...,Ti}.Each element Ti can either be a isgain the empty file and=1-产-∑，4 regular file or the empty file.Let its corresponding popularity The other files Vi,...,VN are non-empty files and we pick distribution be =(1,2..q).where-1.them in such a way that they all have similar popularity Denote another file set by T=(T2,..T-2,+with 1/KM.Specifically,recall thatr>PN+1 popularity distribution Q2 ={q1,92,...,qt-2,qt+1).Here PN1+2 2...PN.Let ho =0.Pick h as the smallest In other words.the two fleand integer such that We then replace T in the first system are replaced by one file T in the files FF by one file Vi.whose popularity is second system.Intuitively,it should be easier(i.e..requiringSimilarly,for eachi.3..we pickh 、W1+h111 D. Lower Bound Accounting for Both Popular & Unpopular Files The earlier proof only considers the more “popular” files, i.e., files with popularity larger than a threshold. Now we will move our attention to the unpopular files and prove the first term in the lower bound 6, i.e., R(K, F,P) ≥ 1 11Mr [N1 + N2 − M]+. To the best of our knowledge, this treatment of unpopular files has not been reported in the literature. Intuitively, depending on the system setting, the lower bound may be dominated by either the popular files or the unpopular files. Thus, we believe that our capability to quantify the impact of unpopular files is the key reason that we can obtain the improved constant-factor characterization in this paper, even in non-asymptotic settings. Interestingly, readers will see soon that we will re-apply the results for System 2 constructed in Section IV.A. Recall that in System 2 all users either request one of the non-empty files with a common popularity that is no less than 1/KMr, or request the empty file. For the unpopular files, their popularity is lower than 1/KMr, and hence we cannot directly use the results for System 2. However, next we introduce a new “merging” idea that will eventually allow us to re-apply the results for System 2. Specifically, we will merge several unpopular files into one file, so that the popularity of the new file is no less than 1/KMr. We will show that this merging step will only lower the achievable rate for serving unpopular files. Thus, in the end we obtain a new system similar to System 2, from which a lower bound for the achievable rate of the original system can be derived. The detail analysis is as follows. Recall that the original set of files is F, and the corresponding popularity distribution is P. Consider another system, where the set of files is F3 = {F0, F1, ..., FN1 , FN1+1, FN1+2, ..., FN } (recall that F0 is again the empty file). The corresponding popularity dis￾tribution is P3 = {p ′ 0 , 1 KMr , ..., 1 KMr , pN1+1, pN1+2, ..., pN } where p ′ 0 = 1 − N1 KMr − PN i=N1+1 pi . In other words, we decrease the popularity of files F1, F2, ..., FN1 in the original system to 1 KMr . Following exactly the same way as the proof of Lemma 2, we can prove that R(K, F,P) ≥ R(K, F3,P3). (29) Again, we will perform a series of further reductions and finally construct a system with a smaller rate, which can utilize the results in previous analysis of “System 2”. To proceed, we need the lemma below. Denote a file set by T1 = {T1, T2, ..., Tt}. Each element Ti can either be a regular file or the empty file. Let its corresponding popularity distribution be Q1 = {q1, q2, ..., qt}, where Pt i=1 qi = 1. Denote another file set by T2 = {T1, T2, ..., Tt−2, Tt+1} with popularity distribution Q2 = {q1, q2, ..., qt−2, qt+1}. Here qt+1 = qt−1 + qt. In other words, the two files Tt−1 and Tt in the first system are replaced by one file Tt+1 in the second system. Intuitively, it should be easier (i.e., requiring less cache and lower transmission rate) to serve the second system because there is less “diversity”. This statement is made precise below. Lemma 8: Let R(K, T1, Q1) be the minimum expected rate required to meet the requests by K users, each of which randomly requests a file in T1 according to the popularity distribution Q1. Let R(K, T2, Q2) be defined similarly for Q2. We have R(K, T1, Q1) ≥ R(K, T2, Q2). (30) Proof: The request set for (K, T1, Q1) is W(K, T1, Q1) = {Wi}, where Wi = {fi1, fi2, ..., fiK} and fij ∈ T1. We first construct a mapping from W(K, T1, Q1) to W(K, T2, Q2). For every request Wi ∈ W(K, T1, Q1), we map it to a request W ′ i ∈ W(K, T2, Q2) as follows. If file Tt−1 or Tt in T1 is requested in Wi , we replace it by Tt+1. For a cache placement and transmission scheme F, suppose that each user can retrieve the file requested in Wi with rate rF(K, Wi). Using the same F, with the replacement of Tt+1 for Tt−1 or Tt in both cache placement and transmissions, the rate rF(K, Wi) must be able to satisfy the request of W ′ i . Therefore, we have rF(K, Wi) ≥ rF(K, W ′ i ). (31) Further, if Wi follows the distribution with which patterns are requested in W(K, T1, Q1), W ′ i will follow the distribution with which patterns are requested in W(K, T2, Q2). To see this, consider any request pattern {f1, ..., fK}. Fix a user k. If fk ̸= Tt+1, the probability that user k requests fk in the mapped request pattern W′ i is exactly the probability that user k requests fk in W(K, T2, Q2). If fk = Tt+1, note that user k requesting Tt+1 in W′ i corresponds to either Tt or Tt−1 being requested in Wi . Hence, the probability that user k in the mapped request pattern W′ i requests file Tt+1 is equal to pt+pt−1 = pt+1, which is also the same as the probability that user k requests Tt+1 in W(K, T2, Q2). Finally, note that the probability with which a pattern is requested is the product of the probability that each file in the pattern is requested by the corresponding user. Therefore, W′ i must have the same distribution as in system W(K, T2, Q2). Thus, by the coupling method [19], we must have RF(K, T1, Q1) ≥ RF(K, T2, Q2). (32) The results of this lemma then follows. Next, we create a new system (K, F4,P4) originated from (K, F3,P3), by merging multiple files in F3 to a new file in F4 (described below) and combining their popularity (similar to the mapping from Q1 to Q2). We denote this new file set as F4 = {F0, F1, ..., FN1 , V1, ..., VN2 } and the popularity distribution as P4 = {v0, 1 KMr , ..., 1 KMr , v1, v2, ...vN2 }. Here, F0 is again the empty file and v0 = 1 − N1 Mr − PN2 i=1 vi . The other files V1, ..., VN2 are non-empty files and we pick them in such a way that they all have similar popularity vi ≈ 1/KMr. Specifically, recall that 1 KMr > pN1+1 ≥ pN1+2 ≥ ... ≥ pN . Let h0 = 0. Pick h1 as the smallest integer such that PN1+h1 j=N1+1 pj ≥ 1/KMr. We then replace files FN1+1, ..., FN1+h1 by one file V1, whose popularity is v1 = PN1+h1 j=N1+1 pj . Similarly, for each i = 2, 3, ..., we pick hi