10 requesting distinct non-empty files.Each user has a cache,la- f(K3)≥f(1) beled Mi,M2,...,MKa,each of which has a common storage size M. =1总 There are No!permutations for the No files.For each per- mutation,we split it into subgroups,each with K3 files. =G%-M 1 (23) Denote r(i,j)as the rate needed to meet the users'requests if their request pattern is the same as the j-th subgroup in the ≥5K(%-M0 i-th permutation,i.e.,when the k-th user requests the k-th file Next,we consider the case KNop 5.By definition,we in the subgroup,k =1,2,...,K3. have For each permutation i,consider all the sub-groups (i.e., request patterns)as a whole.Recall that the cache con- K= tent is fixed when these request patterns vary.Consider a feasible cache placement and transmission scheme 3. 2K1- (since Ki is an integer) Based on the cached content Mi,...,MKa.and the transmis- 1 sions from the server for each request pattern (with rates =KNop]-2 (24) r(i,1),.r(i,).respectively),the Ka users together 1 must be able to reconstruct all K files.Hence. ≥2(Kop-1)-2 2KVop-1≥0.3KN0n, Ka ∑r6,)+∑M≥K No (19) where in the last step we have used KNop >5.Since M >3. =1 k=1 we have Summarizing over all No!permutations,we have f(K3)=K3- K3M No! r(位，)≥ K3-K3M )No!. (20) M ≥K3 1一 -1 K Note that there are AN request patterns Wji,while M (25) 2K3 1- (using Kp ≥M,≥3) there areNo!subgroups among all the No!permuta- tions.By symmetry2,each Wi E Hi appears an equal number of times in these subgroups.Hence,the number of times ≥05KNop-)(-3MKp） each Wi EHi appears in the summation in Equation(20) isN Hence. ≥5p(No-M0, where the last inequality is due to ∑w,emr(K,W) NaL等」 (05KNop-1).(1-MKp)-Kp(No-M) A rs(i,j) ·No 1 1 21 20.5kop-1)号-言n(o-0 2 」No Nol( No K3-K3) ≥品KMp-号+写KpM 21 Ka-KaM >0, (26) 兴 where the first inequality is due to KMp<1,and the third (21)inequality is due to KNop>5 and KMp >0. We therefore conclude this lemma. ◆ Using both (23)and (25)into (22),we conclude that the Denote the right hand side of Equation(18)by f(K3).From minimum expected rate needed for W(K,F,P)is bounded Lemmas 5 and 6,the minimum expected rate can be bounded by by 1 R(K,F,P)≥R(K,W3) R(K,F,P)≥0.455·5po-M+ (27) =(1-π(K1)·R(K,W4) (22) 1 ≥(1-π(K1)f(K3). ≥立po-M+ Therefore,we have proved Proposition 1. Recall that K1≌LKNop]≤L0」and K3≌L号K小.We Applying Proposition 1 to System 2(K,F1,P2)(i.e.,with now consider two cases. No=Ni and p=),we immediately have the following If KNop≤5，it is easy to verify that lower bound for the expected transmission rate of System 2: 2 We note that this is similar to the symmetrization argument in[9. RKP≥i-AM (28)10 requesting distinct non-empty files. Each user has a cache, la￾beled M1, M2, ..., MK3 , each of which has a common storage size M. There are N0! permutations for the N0 files. For each per￾mutation, we split it into ⌊ N0 K3 ⌋ subgroups, each with K3 files. Denote r(i, j) as the rate needed to meet the users’ requests if their request pattern is the same as the j-th subgroup in the i-th permutation, i.e., when the k-th user requests the k-th file in the subgroup, k = 1, 2, ..., K3. For each permutation i, consider all the sub-groups (i.e., request patterns) as a whole. Recall that the cache con￾tent is fixed when these request patterns vary. Consider a feasible cache placement and transmission scheme F. Based on the cached content M1, ..., MK3 , and the transmis￾sions from the server for each request pattern (with rates r(i, 1), ..., r(i, ⌊ N0 K3 ⌋), respectively), the K3 users together must be able to reconstruct all K3 · ⌊ N0 K3 ⌋ files. Hence,  N0 K3  X j=1 rF(i, j) +X K3 k=1 Mk ≥ K3 · › N0 K3 ž . (19) Summarizing over all N0! permutations, we have X N0! i=1  N0 K3  X j=1 rF(i, j) ≥ › N0 K3 ž · K3 − K3M ‹ · N0!. (20) Note that there are A K3 N0 request patterns Wj ∈ Hi , while there are š N0 K3  · N0! subgroups among all the N0! permuta￾tions. By symmetry2 , each Wj ∈ Hi appears an equal number of times in these subgroups. Hence, the number of times each Wj ∈ Hi appears in the summation in Equation (20) is  N0 K3  ·N0! A K3 N0 . Hence, P Wj∈Hi rF(K, Wj ) A K3 N0 = 1 š N0 K3  · N0! · X N0! i=1  N0 K3  X j=1 rF(i, j) ≥ 1 š N0 K3  · N0! · N0!(› N0 K3 ž K3 − K3M) = š N0 K3  K3 − K3M š N0 K3  . (21) We therefore conclude this lemma. Denote the right hand side of Equation (18) by f(K3). From Lemmas 5 and 6, the minimum expected rate can be bounded by R(K, F ′ ,P ′ ) ≥ R(K, W3) = (1 − π(K1)) · R(K, W4) ≥ (1 − π(K1))f(K3). (22) Recall that K1 , ⌊KN0p⌋ ≤ ⌊ N0 Mr ⌋ and K3 , ⌊ 1 2K1⌋. We now consider two cases. If KN0p ≤ 5, it is easy to verify that 2 We note that this is similar to the symmetrization argument in [9]. f(K3) ≥ f(1) = 1 − M N0 = 1 N0 (N0 − M) ≥ 1 5 Kp(N0 − M). (23) Next, we consider the case KN0p > 5. By definition, we have K3 = › 1 2 K1 ž ≥ 1 2 K1 − 1 2 (since K1 is an integer) = 1 2 ⌊KN0p⌋ − 1 2 ≥ 1 2 (KN0p − 1) − 1 2 = 1 2 KN0p − 1 ≥ 0.3KN0p, (24) where in the last step we have used KN0p > 5. Since Mr ≥ 3, we have f(K3) = K3 − K3M š N0 K3  ≥ K3 ‚ 1 − M N0 K3 − 1 Œ ≥ K3 ‚ 1 − M 10 3Kp − 1 Œ ≥ K3 ‚ 1 − M 3 Kp Œ (using 1 Kp ≥ Mr ≥ 3) ≥ (0.5KN0p − 1) ·  1 − 1 3 MKp‹ ≥ 1 5 Kp (N0 − M), (25) where the last inequality is due to (0.5KN0p − 1) ·  1 − 1 3 MKp‹ − 1 5 Kp (N0 − M) ≥ (0.5KN0p − 1) 2 3 − 1 5 Kp(N0 − M) ≥ 2 15 KN0p − 2 3 + 1 5 KpM > 0, (26) where the first inequality is due to KM p ≤ 1, and the third inequality is due to KN0p > 5 and KM p ≥ 0. Using both (23) and (25) into (22), we conclude that the minimum expected rate needed for W(K, F,P) is bounded by R(K, F ′ ,P ′ ) ≥ 0.455 · 1 5 Kp [N0 − M]+ ≥ 1 11 Kp [N0 − M]+ . (27) Therefore, we have proved Proposition 1. Applying Proposition 1 to System 2 (K, F1,P2) (i.e., with N0 = N1 and p = 1 KMr ), we immediately have the following lower bound for the expected transmission rate of System 2: R(K, F1,P2) ≥ 1 11Mr (N1 − M). (28)