With Lemma 1 and Lemma 2,we have proved that have K1≤L」，and R(K,F,P)>R(K,F1,P2).In the following analysis for the first part of Theorem 1,we will focus on R(K,F1,P2).Note P(K2K)≥2 (13) that the system (K,F1,P2)is precisely the "System 2"that we discussed in Section III-A.Next,we will derive a lower This follows from the result in [17],which shows that any bound on the average transmission rate of System 2,which median must lie in the interval [np],[np]],for a binomial also provides a lower bound on R(K,F,P).We will derive distribution B(n,p) this lower bound on the average transmission rate of System 2 by relating it to a lower bound on the worst-case transmission In other words,with probability no less than 0.5,no less rate.Note that since all files have equal popularity in System 2, than K users request non-empty files.Still,some of these the fact that its average transmission rate is at most a constant K users may request a common file.Next,we are interested factor away from its worst-case transmission rate is in fact in the number of distinct files that are requested.Denote this known from the results in [9]and [131.For example,we number as Kd. can obtain a lower bound on the average transmission rate Lemma 4:Given that there are K users requesting non- of System 2 from Theorem 2 in [9]by choosing c=1, empty files,the probability that Ka(i.e.,the number of distinct N=Ni there and by choosing K in [9]as the number files requested)is no smaller than min],K]}is of users requesting popular files.However,the lower bound greater than or equal to 0.91. derived in this way involves an expectation over Ki.Since later we will use System 2 again to deal with unpopular files, Proof:Clearly,we only need to consider K<K we wish to obtain a lower bound that is a function of the total (because a larger value of K,only increases the number of number of users K.The following derivation accounts for such distinct files).When K =1,2,or 3,we have that technical details,and at the same time yields the factor 1/11 equals 0 or 1.In this case,it is easy to see that this lemma in (6).(In contrast,an explicit expression for such a factor holds,since there must be at least one distinct file requested. is not provided in [13]).We note that some of the reduction For K,>4,consider only those Kr users requesting non- techniques below and in Sections IV-B to IV-C are also similar empty files.Each user requests one file from the No non-empty to [913].although here we exploit the fact that pN to obtain the 1/11 factor (see Proposition 1 below). files uniformly randomly and independently.There are N possible request patterns for the Kr users,each of which is Towards this end,rather than only proving the lower bound equally likely.For some of these request patterns,the number for System 2.we instead prove a more general result that will of distinct files are smaller than K2K.The number of be used again in Subsections C-E.Specifically,consider a sys- such request patterns must be smaller than CKTo see tem(K,F P).Its file set isF={F,F,...,FNo},and the this,note that the first term is the number of ways to choose corresponding popularity distribution is p={po,p.),K2 files from the No non-empty files.The second term is the wherep<KM and po =1-Nop >0.Note that (K,F,P') number of ways that each user can choose one of the k2 files. becomes the"System 2"when No=Ni and p=K We thus have Proposition 1:With K users requesting files independently in F according to the corresponding popularity distribution P(Kd≤K2lKr)< p,the lower bound on the expected transmission is N evNo(Na)No RKr,P八≥7p-(6-AM, (12) V/2π(N0-K2)(-2)Na-K e for any M≥o. 1 K2 K From now till Subsection C,we will prove Proposition 1. V2mK2()K（N Note that in the system (K,F,P),it is possible that some e No No-K2 file is requested by multiple users.In Section IV-B,we will OK2-K （No-K2 reduce it to the third system where every non-empty requested file is requested exactly once.Towards that end,we first Here,we have used Stirling's formula in the second step,i.e., characterize the number of distinct files requested in system (K,F,P'). v2m() ≤m≤m()” For a given system setting (K,F,P),let I;=1 if user i requests a non-empty file,and let I;=0 if user i requests the In the third step.we have useda1.due to empty file.Denote K.Then,K is the number of K2≥2andK2≤No.It is easy to prove that(1+x)z≤e for any >0.Therefore, users who request non-empty files.All Ii are i.i.d.distributed with mean Nop.The probability distribution for Kr is given No No-K2 K2 NogKa.Ka by No-K2 =（1+ No-K2 P(K =K1)=CK (Nop)K:(1-Nop)K-K: Recall that at the beginning of the proof,we have restricted our attention to K,≤K1andK,≥4.Since K2≌L2K,J, Lemma3:Define K1≌KNop.Since p≤t,we we have2≤K2≤是Kr.Hence,using Lemma3,we have8 With Lemma 1 and Lemma 2, we have proved that R(K, F,P) ≥ R(K, F1,P2). In the following analysis for the first part of Theorem 1, we will focus on R(K, F1,P2). Note that the system (K, F1,P2) is precisely the “System 2” that we discussed in Section III-A. Next, we will derive a lower bound on the average transmission rate of System 2, which also provides a lower bound on R(K, F,P). We will derive this lower bound on the average transmission rate of System 2 by relating it to a lower bound on the worst-case transmission rate. Note that since all files have equal popularity in System 2, the fact that its average transmission rate is at most a constant factor away from its worst-case transmission rate is in fact known from the results in [9] and [13]. For example, we can obtain a lower bound on the average transmission rate of System 2 from Theorem 2 in [9] by choosing c = 1, Nl = N1 there and by choosing Kl in [9] as the number of users requesting popular files. However, the lower bound derived in this way involves an expectation over Kl . Since later we will use System 2 again to deal with unpopular files, we wish to obtain a lower bound that is a function of the total number of users K. The following derivation accounts for such technical details, and at the same time yields the factor 1/11 in (6). (In contrast, an explicit expression for such a factor is not provided in [13]). We note that some of the reduction techniques below and in Sections IV-B to IV-C are also similar to [9][13], although here we exploit the fact that pN1 ≈ 1 KMr to obtain the 1/11 factor (see Proposition 1 below). Towards this end, rather than only proving the lower bound for System 2, we instead prove a more general result that will be used again in Subsections C-E. Specifically, consider a sys￾tem (K, F ′ ,P ′ ). Its file set is F ′ = {F0, F1, ..., FN0 }, and the corresponding popularity distribution is P ′ = {p0, p, ..., p}, where p ≤ 1 KMr and p0 = 1−N0p ≥ 0. Note that (K, F ′ ,P ′ ) becomes the “System 2” when N0 = N1 and p = 1 KMr . Proposition 1: With K users requesting files independently in F ′ according to the corresponding popularity distribution P ′ , the lower bound on the expected transmission is R(K, F ′ ,P ′ ) ≥ 1 11 Kp · (N0 − M), (12) for any M ≥ 0. From now till Subsection C, we will prove Proposition 1. Note that in the system (K, F ′ ,P ′ ), it is possible that some file is requested by multiple users. In Section IV-B, we will reduce it to the third system where every non-empty requested file is requested exactly once. Towards that end, we first characterize the number of distinct files requested in system (K, F ′ ,P ′ ). For a given system setting (K, F ′ ,P ′ ), let Ii = 1 if user i requests a non-empty file, and let Ii = 0 if user i requests the empty file. Denote Kr = PK i=1 Ii . Then, Kr is the number of users who request non-empty files. All Ii are i.i.d. distributed with mean N0p. The probability distribution for Kr is given by P(Kr = K1) = C K1 K (N0p) K1 (1 − N0p) K−K1 . Lemma 3: Define K1 , ⌊KN0p⌋. Since p ≤ 1 KMr , we have K1 ≤ ⌊ N0 Mr ⌋, and P(Kr ≥ K1) ≥ 1 2 . (13) This follows from the result in [17], which shows that any median must lie in the interval [⌊np⌋, ⌈np⌉], for a binomial distribution B(n, p). In other words, with probability no less than 0.5, no less than K1 users request non-empty files. Still, some of these K1 users may request a common file. Next, we are interested in the number of distinct files that are requested. Denote this number as Kd. Lemma 4: Given that there are Kr users requesting non￾empty files, the probability that Kd (i.e., the number of distinct files requested) is no smaller than min{⌊ 1 2Kr⌋, ⌊ 1 2K1⌋} is greater than or equal to 0.91. Proof: Clearly, we only need to consider Kr ≤ K1 (because a larger value of Kr only increases the number of distinct files). When Kr = 1, 2, or 3, we have that ⌊ 1 2Kr⌋ equals 0 or 1. In this case, it is easy to see that this lemma holds, since there must be at least one distinct file requested. For Kr ≥ 4, consider only those Kr users requesting non￾empty files. Each user requests one file from the N0 non-empty files uniformly randomly and independently. There are N Kr 0 possible request patterns for the Kr users, each of which is equally likely. For some of these request patterns, the number of distinct files are smaller than K2 , ⌊ 1 2Kr⌋. The number of such request patterns must be smaller than C K2 N0 ·K Kr 2 . To see this, note that the first term is the number of ways to choose K2 files from the N0 non-empty files. The second term is the number of ways that each user can choose one of the K2 files. We thus have P(Kd ≤ K2|Kr) < C K2 N0 K Kr 2 N Kr 0 ≤ e √ N0( N0 e ) N0 È 2π(N0 − K2)( N0−K2 e )N0−K2 · 1 √ 2πK2( K2 e )K2 K2 N0 ‹Kr ≤ e 2π  N0 N0 − K2 ‹N0−K2 · ( N0 K2 ) K2−Kr . Here, we have used Stirling’s formula in the second step, i.e., √ 2πn n e n ≤ n! ≤ e √ n n e n . In the third step, we have used È N0 K2(N0−K2) ≤ 1, due to K2 ≥ 2 and K2 ≤ 1 2N0. It is easy to prove that (1 + x) 1 x ≤ e for any x > 0. Therefore,  N0 N0 − K2 ‹N0−K2 =  1 + K2 N0 − K2 ‹ N0−K2 K2 ·K2 ≤ e K2 . Recall that at the beginning of the proof, we have restricted our attention to Kr ≤ K1 and Kr ≥ 4. Since K2 , ⌊ 1 2Kr⌋, we have 2 ≤ K2 ≤ 1 2Kr. Hence, using Lemma 3, we have