9 K,≤Ki≤l」≤3No.Therefore,.we have It remains to show that,if W;is chosen according to the PK≤KK<会( K2-K, distribution of W(K,F1,P2),then the resulting W:has the same distribution as that of request patterns in W3(K3,K1). To see this,note that the probability with which W;requests ≤2ea6Ka-K no empty files is exactly 1-(K1).Further,due to symmetry 6 K2-K, on the files and the users in W(K,F1,P2),along with the < e2K2-Kr symmetry of our mapping,each pattern W:that requests non- empty files must occur with equal probability,i.e.,there are 6 -2 ≤2元 CA request patterns each of equal probability,that sums to the probability 1-(K1).We then conclude that each W where the third inequality is due to K2≤号K,≤aNo,and occurs with the same probability as in Wa(K3,K1). the fourth inequality is due to K2<Kr.Finally,P(Kd Thus,with the coupling method [19],we have K2|K)=1-P(Kd<K2|K)>0.91. ■ Rs(K,F,P)≥Rs(K,W3) (16) B.Reduction Step 3 and the result then follows. ■ Combing Lemma 3 and Lemma 4,we can show that,with probability no less than 0.455,the number of distinct files C.Reduction Step 4 the Lower Bound for Popular files requested is no smaller than K1].We now perform the We now consider the 4th system W4.In this system,there third reduction.For W(K,F,P'),we divide all the possible are always K3 users requesting K3 distinct non- request patterns into two subsets.The first subset contains empty files and all the other users request the empty file.We those request pattems such that the number of users requesting have distinct files is no smaller than K3.The other request Lemma 6:R(K,W3)=(1-(K1))R(K,Wa). patterns constitute the second subset.The sum probability for Proof:Recall that in the third system W3(K3,K1),with the second subset is denoted as (K1). probability (K1)the users all request the empty file,which We then construct the third system as follows:in the third requires zero rate.With probability 1-(K1),exactly K3 system,with probability (K1)the users will all request the users request exactly K3 distinct files.Each such pattern empty file.With probability 1-(K1),exactly K3 users will request exactly K3 distinct non-empty files from F1,...,FNo. cthprobabity爱器In the fourh ysem网a. all request patterns have exactly K3 users requesting exactly and all other users will request the empty file.Note that there K3 distinct files,and each pattern occurs with probability are exactly CA request patterns where exactly Ka users request K3 distinct non-empty files.We let each such request Therefore,the rate needed for the third systes pattern occur with equal probability 1-元(K1 linear combination of zero rate (with portion (K1))and the rate needed for the fourth system (with portion 1-(K1)). Let this third system be denoted by W3(K3,K1),and let The lemma then follows. ■ R(K,W3)be the corresponding minimum expected transmis- Next we focus on the system W4. sion rate.Then.we have the following lemma. Let Hi.i=1,2.ca be the CK choices of picking Lemma 5: K3 users out of the K users.In system W4,if in a request R(K,F,P)≥R(K,W3) (14)Wj,the users requesting distinct non-empty files are exactly in Hi,we denote it by WiE Hi.In other words,Hi is the set Proof:The proof uses coupling [19].For every Wie of request patterns in which the users requesting non-empty W(K,Fp).map it to a random Wi EW3(K3,K1)as files is exactly the same as in Hi.Note that there are AN= follows.If the number of users requesting non-empty files in No! (KKa such patterns in each Hi.We have the following Wi is less than K1,or the number of distinct non-empty files result. requested is less than K3≌L」，then in W:all users request Lemma 7:Consider systems W4 where there are always the empty file.Otherwise,we perform the mapping described exactly K3 users requesting distinct files in F and the below. other K-K3 users request the empty file.For any Hi. For every remaining W;with K>Ka,we conduct the i=1,2,.C,the following holds, following splitting procedure. For each non-empty file that is requested by some users, ∑(K,W)≥A 0」K3-KM randomly choose one user requesting it.Note that there (17) WEH 兴 are Kd such chosen users. Among the chosen users,randomly choose K3 of them. Note that Lemma 7 immediately implies that These K3 users now request distinct non-empty files,and we let all other users request the empty file. R(K,W4)≥ 」K-KM (18) Given any cache placement and transmission scheme 3, 岩 since W requests a subset of the files in Wi,we have Proof:Without loss of generality,suppose that Hi= rs(K,W)≥Ts(K,W): (15){1,1,...,1,0,0,...,0}.In other words,user 1,2.....K3 are9 Kr ≤ K1 ≤ ⌊ N0 Mr ⌋ ≤ 1 3N0. Therefore, we have P(Kd ≤ K2|Kr) < e 2π e K2 ·  N0 K2 ‹K2−Kr ≤ e 2π e K2 · 6 K2−Kr < e 2π e 2K2−Kr ·  6 e ‹K2−Kr ≤ e 2π  6 e ‹−2 , where the third inequality is due to K2 ≤ 1 2Kr ≤ 1 6N0, and the fourth inequality is due to K2 ≤ 1 2Kr. Finally, P(Kd > K2|Kr) = 1 − P(Kd ≤ K2|Kr) > 0.91. B. Reduction Step 3 Combing Lemma 3 and Lemma 4, we can show that, with probability no less than 0.455, the number of distinct files requested is no smaller than ⌊ 1 2K1⌋. We now perform the third reduction. For W(K, F ′ ,P ′ ), we divide all the possible request patterns into two subsets. The first subset contains those request patterns such that the number of users requesting distinct files is no smaller than K3 , ⌊ K1 2 ⌋. The other request patterns constitute the second subset. The sum probability for the second subset is denoted as π(K1). We then construct the third system as follows: in the third system, with probability π(K1) the users will all request the empty file. With probability 1 − π(K1), exactly K3 users will request exactly K3 distinct non-empty files from F1, ..., FN0 , and all other users will request the empty file. Note that there are exactly C K3 K A K3 N0 request patterns where exactly K3 users request K3 distinct non-empty files. We let each such request pattern occur with equal probability 1−π(K1) C K3 K A K3 N0 . Let this third system be denoted by W3(K3, K1), and let R(K, W3) be the corresponding minimum expected transmis￾sion rate. Then. we have the following lemma. Lemma 5: R(K, F ′ ,P ′ ) ≥ R(K, W3). (14) Proof: The proof uses coupling [19]. For every Wi ∈ W(K, F ′ ,P ′ ), map it to a random W ′ i ∈ W3(K3, K1) as follows. If the number of users requesting non-empty files in Wi is less than K1, or the number of distinct non-empty files requested is less than K3 , ⌊ K1 2 ⌋, then in W ′ i all users request the empty file. Otherwise, we perform the mapping described below. For every remaining Wi with Kd ≥ K3, we conduct the following splitting procedure. • For each non-empty file that is requested by some users, randomly choose one user requesting it. Note that there are Kd such chosen users. • Among the chosen users, randomly choose K3 of them. These K3 users now request distinct non-empty files, and we let all other users request the empty file. Given any cache placement and transmission scheme F, since W ′ i requests a subset of the files in Wi , we have rF(K, Wi) ≥ rF(K, W ′ i ). (15) It remains to show that, if Wi is chosen according to the distribution of W(K, F1,P2), then the resulting W ′ i has the same distribution as that of request patterns in W3(K3, K1). To see this, note that the probability with which W′ i requests no empty files is exactly 1−π(K1). Further, due to symmetry on the files and the users in W(K, F1,P2), along with the symmetry of our mapping, each pattern W ′ i that requests non￾empty files must occur with equal probability, i.e., there are C K3 K A K3 N0 request patterns each of equal probability, that sums to the probability 1 − π(K1). We then conclude that each W′ i occurs with the same probability as in W3(K3, K1). Thus, with the coupling method [19], we have RF(K, F ′ ,P ′ ) ≥ RF(K, W3). (16) and the result then follows. C. Reduction Step 4 & the Lower Bound for Popular files We now consider the 4th system W4. In this system, there are always K3 , ⌊ K1 2 ⌋ users requesting K3 distinct non￾empty files and all the other users request the empty file. We have Lemma 6: R(K, W3) = (1 − π(K1))R(K, W4). Proof: Recall that in the third system W3(K3, K1), with probability π(K1) the users all request the empty file, which requires zero rate. With probability 1 − π(K1), exactly K3 users request exactly K3 distinct files. Each such pattern occurs with probability 1−π(K1) C K3 K A K3 N0 . In the fourth system W4, all request patterns have exactly K3 users requesting exactly K3 distinct files, and each pattern occurs with probability 1 C K3 K A K3 N0 . Therefore, the rate needed for the third system is a linear combination of zero rate (with portion π(K1)) and the rate needed for the fourth system (with portion 1 − π(K1)). The lemma then follows. Next we focus on the system W4. Let Hi , i = 1, 2, ..., CK3 K be the C K3 K choices of picking K3 users out of the K users. In system W4, if in a request Wj , the users requesting distinct non-empty files are exactly in Hi , we denote it by Wj ∈ Hi . In other words, Hi is the set of request patterns in which the users requesting non-empty files is exactly the same as in Hi . Note that there are A K3 N0 = N0! (K−K3)! such patterns in each Hi . We have the following result. Lemma 7: Consider systems W4 where there are always exactly K3 users requesting distinct files in F ′ and the other K − K3 users request the empty file. For any Hi , i = 1, 2, ..., CK3 K , the following holds, X Wj∈Hi rF(K, Wj ) ≥ A K3 N0 · š N0 K3  K3 − K3M š N0 K3  . (17) Note that Lemma 7 immediately implies that R(K, W4) ≥ š N0 K3  K3 − K3M š N0 K3  . (18) Proof: Without loss of generality, suppose that Hi = {1, 1, ..., 1, 0, 0, ..., 0}. In other words, user 1, 2,..., K3 are