TABLE II:Brief introduction of constructed systems satisfying property (a).We then map Wi to another request Systems Definition W:,such that the first N elements in W;remain the same as Map the“unpopular”files from N+1to in W:,while other elements are mapped to the empty file.Let System 1 N to a virtual empty file with their sum be the transmission rate to serve the request pattern W.. probability. By such a construction,we now verify property (b)holds. Reduce the popularity of files F1...FN to We wish to show that the probability with which the mapped System 2 K.Some users may request a same file. request patterns is W!={f1,f2...fk},where fk is the With probability (K1),all users request file requested by user k,is the same as the probability with the empty file.With probability 1-(K1), which the same pattern Wi=[f1,f2,...,fr}is requested in System 3 W(K,F1,P1).We first fix a user k and compare the probabili- exactly K3 users request K3 distinct files, ty that user k requests file fk.If f E [F1,F2,...,FN},since and other users request empty files. we did not change their popularity,the probability pw(f) In each request pattern,exactly K3 users request K3 distinct files,and other users that user k requests fk in the mapped request pattern is the System 4 request empty files. same as the probability pw,(f)that user k requests fr in W(K,F1,P1).If fr=0,according to our construction,the (K,F3,P3) Reduce the the popularity of files F1....,FN probability pw(f)that user k requests fr in the mapped in(K,F,P)to立 request pattern is equal to the probability that user k re- (K,F4,P) Merge the unpopular files into virtual files quests any file in [FN+1,...,FN}in W(K,F,P).which is with popularity 2KM and <KM. NPo Hence,it is also the same as the probability Reduce the probability of all files (except the pw,(f)that user k requests the empty file in W(K,F1,P1). (K,F4:Ps) empty file)towhich is similar to the Finally,the probability that the mapped request pattem is W, System 2. 不 P(W={i,,fK})= IIpw:(fe) new system should require a lower transmission rate than the k=1 original system,which is stated in the following lemma. Lemma 1:Let R(K,F1,P1)be the minimum expected rate Πpw,(f) required to meet the requests by the K users,each of which k=1 randomly requests a file in F1 according to the popularity =P(Wj={f1,....fk}) distribution P1.We have Thus,W:has the same distribution as Wi,and hence r and R(K,F,P)≥R(K,F,P) (10) r'have the same distribution,satisfying property (b). Proof:For a given cache placement and transmission Further,for any caching and transmission scheme that can scheme 3,let r=r(Wi)be the transmission rate for satisfy users'request Wi.it must can satisfy W,since W the random request pattern Wi in W(K,F,P),where Wi can be seen as a subset of Wi.Hence,the rate to serve the is chosen randomly in W(K,F,P).Note that since Wi is request pattern W!is clearly no larger than the rate to serve random,r is also a random variable.Further,the average the request pattern Wi.Thus we have r'almost surely, transmission rate is R3(K,F,P)=E[r].Similarly,let satisfying property (c).The result of the lemma then follows. r=r(Wi)denote the transmission rate,where Wi is ■ chosen randomly from the new distribution in W(K,F1,P). We next create another new system by a further adjustment Again,R(K,F1,P1)=Er'].Note that the two expectations on the tuple (K,F1,P1).Note that N<KM.Otherwise, corresponding to two distributions,driven by W(K,F,P)and we will have∑1A>KM,~pNa≥1，which is a contra- W(K,F1,P1),respectively.Therefore,r and r'cannot be diction to1.Define a new popularity distribution directly compared in a pointwise manner,e.g.,the number P2=(1-ki Kit:Kht:Kir}over the files F1.In of request patterns in W(K,F,P)is larger than that in other words,compared to (K,F1,P1),in this new system, W(K,F1,P1). each non-empty file is requested with a smaller probability In the following,we will show that r'sr,i.e.,r'is KMIntuitively,its expected transmission rate should be even stochastic dominated by r.To do so,we will use Theorem 3.1 lower,which is stated below. in [19].Specifically,we need to find two coupled variablesf Lemma 2:Let R(K,F1,P2)be the minimum expected rate and r with the following properties: required to meet the requests by K users,each of which (a)r and f have the same distribution; randomly requests a file in Fi according to the popularity (b)r'and r'have the same distribution; distribution P2.We have (c)r≥ralmost surely.. Then,applying Theorem 3.1 in [19].we can conclude that R(K,F1,P1)>R(K,F1,P2). (11) r'<D r and E(r)=E(f)>E(r)=E(r'). This lemma is similar to the uniformization argument in It remains to show the existence of and which are the proof of Claim 2 in [9].The proof can also use a similar constructed as follows.For every WiE W(K,F,P),we let coupling idea as in Lemma 1.For completeness,we provide r=r and thus they must have exactly the same distribution, the proof in the appendix.7 TABLE II: Brief introduction of constructed systems Systems Definition System 1 Map the “unpopular” files from N1 + 1 to N to a virtual empty file with their sum probability. System 2 Reduce the popularity of files F1,..., FN1 to 1 KMr . Some users may request a same file. System 3 With probability π(K1), all users request the empty file. With probability 1 − π(K1), exactly K3 users request K3 distinct files, and other users request empty files. System 4 In each request pattern, exactly K3 users request K3 distinct files, and other users request empty files. (K, F3,P3) Reduce the the popularity of files F1,..., FN1 in (K, F,P) to 1 KMr . (K, F4,P4) Merge the unpopular files into virtual files with popularity ≥ 1 KMr and < 2 KMr . (K, F4,P5) Reduce the probability of all files (except the empty file) to 1 KMr , which is similar to the System 2. new system should require a lower transmission rate than the original system, which is stated in the following lemma. Lemma 1: Let R(K, F1,P1) be the minimum expected rate required to meet the requests by the K users, each of which randomly requests a file in F1 according to the popularity distribution P1. We have R(K, F,P) ≥ R(K, F1,P1). (10) Proof: For a given cache placement and transmission scheme F, let r = rF(Wi) be the transmission rate for the random request pattern Wi in W(K, F,P), where Wi is chosen randomly in W(K, F,P). Note that since Wi is random, r is also a random variable. Further, the average transmission rate is RF(K, F,P) = E[r]. Similarly, let r ′ = rF(Wj ) denote the transmission rate, where Wj is chosen randomly from the new distribution in W(K, F1,P1). Again, RF(K, F1,P1) = E[r ′ ]. Note that the two expectations corresponding to two distributions, driven by W(K, F,P) and W(K, F1,P1), respectively. Therefore, r and r ′ cannot be directly compared in a pointwise manner, e.g., the number of request patterns in W(K, F,P) is larger than that in W(K, F1,P1). In the following, we will show that r ′ ≤D r, i.e., r ′ is stochastic dominated by r. To do so, we will use Theorem 3.1 in [19]. Specifically, we need to find two coupled variables rˆ and rˆ′ with the following properties: (a) r and rˆ have the same distribution; (b) r ′ and rˆ′ have the same distribution; (c) rˆ ≥ rˆ′ almost surely. Then, applying Theorem 3.1 in [19], we can conclude that r ′ ≤D r and E(r) = E(ˆr) ≥ E(rˆ′) = E(r ′ ). It remains to show the existence of rˆ and rˆ′ , which are constructed as follows. For every Wi ∈ W(K, F,P), we let rˆ = r and thus they must have exactly the same distribution, satisfying property (a). We then map Wi to another request W′ i , such that the first N1 elements in Wi remain the same as in W′ i , while other elements are mapped to the empty file. Let rˆ ′ be the transmission rate to serve the request pattern W′ i . By such a construction, we now verify property (b) holds. We wish to show that the probability with which the mapped request patterns is W′ i = {f1, f2, ..., fK}, where fk is the file requested by user k, is the same as the probability with which the same pattern Wj = {f1, f2, ..., fK} is requested in W(K, F1,P1). We first fix a user k and compare the probabili￾ty that user k requests file fk. If fk ∈ {F1, F2, ..., FN1 }, since we did not change their popularity, the probability pW′ i (fk) that user k requests fk in the mapped request pattern is the same as the probability pWj (fk) that user k requests fk in W(K, F1,P1). If fk = ∅, according to our construction, the probability pW′ i (fk) that user k requests fk in the mapped request pattern is equal to the probability that user k re￾P quests any file in {FN1+1, ..., FN } in W(K, F,P), which is N i=N1+1 pi = p0. Hence, it is also the same as the probability pWj (fk) that user k requests the empty file in W(K, F1,P1). Finally, the probability that the mapped request pattern is W′ i , is P(W′ i = {f1, ..., fK}) = Y K k=1 pW′ i (fk) = Y K k=1 pWj (fk) = P(Wj = {f1, ..., fK}). Thus, W′ i has the same distribution as Wj , and hence rˆ′ and r ′ have the same distribution, satisfying property (b). Further, for any caching and transmission scheme that can satisfy users’ request Wi , it must can satisfy W′ i , since W′ i can be seen as a subset of Wi . Hence, the rate to serve the request pattern W′ i is clearly no larger than the rate to serve the request pattern Wi . Thus we have rˆ ≥ rˆ′ almost surely, satisfying property (c). The result of the lemma then follows. We next create another new system by a further adjustment on the tuple (K, F1,P1). Note that N1 ≤ KMr. Otherwise, we will have PN i=1 pi > KMr · pN1 ≥ 1, which is a contra￾diction to PN i=1 pi = 1. Define a new popularity distribution P2 = {1 − N1 KMr , 1 KMr , 1 KMr , ..., 1 KMr } over the files F1. In other words, compared to (K, F1,P1), in this new system, each non-empty file is requested with a smaller probability 1 KMr . Intuitively, its expected transmission rate should be even lower, which is stated below. Lemma 2: Let R(K, F1,P2) be the minimum expected rate required to meet the requests by K users, each of which randomly requests a file in F1 according to the popularity distribution P2. We have R(K, F1,P1) ≥ R(K, F1,P2). (11) This lemma is similar to the uniformization argument in the proof of Claim 2 in [9]. The proof can also use a similar coupling idea as in Lemma 1. For completeness, we provide the proof in the appendix