13 of Theorem 2, Algorithm 2 Transmission Procedure Step 1:for s=K4;K4-1,...,1 R(K,F,P)≤min M-M±+∑Kp: max(1,M) for every S CUi such that S=s,do i>N (41) Server sends DkEsVk.s\k) KPN(N3-M)+∑KPm:): end for end for i>Na Step 2:for every user k EU2 where N3 M+1. Sever sends its requested file d Remark:We note that the first term is similar to the end for upper bound in [13].However,the denominator is max(1,M) instead of M.Further,the second term of(41)is new.These changes are important to deal with the case when N<M and when M is small.Please see scheme 2 and scheme 3 in the transmission received and its local storage.Hence,user K the proof below for details. must be able to decode the bit b. Proof of Theorem 2:We prove by considering 3 schemes. We first consider scheme 1,which is most useful when We now compute the rate required by the transmission Ni>M and M>1.The analysis for scheme 1 is similar to scheme.This analysis is similar to [8].We first calculate the [9,13],and we include the details below for the sake of com- rate R sent by the server in step 1.For a subset SC U and pleteness.We again divide the whole file set into two subsets IS]=s,a bit of file di is in V.s\)with probability F1=(F1;F2,...,FN}and F2=(FN:+1,FN1+2;...FN). The files in F1 are the"more popular"files whose popularity )-11一)K4-+ (42) is larger thanRecall that in our model each file is of unit length.The minimum indivisible portion of a file is called The expected number of bits in V.s is()1(1- a"bit".We have assumed that each file has F such bits.The 1.When the file size F is large.the number of bits cache placement strategy is given as follows. inV,s4 is Fl·(兴)-1(1-兴)K4-s+1+oF）with high probability.Therefore,the rate needed to be sent for a Algorithm 1 Cache Placement Procedure specific subset S is for1≤k≤K,1≤n≤Ni User randomly caches min bits of the file Okes Vk.SHk)=max IVk.sMk) Fn end for =l始r--总k-1+ (43) In the sequel,we focus on the "large file-size"regime and Note that we only cache fractions of the Ni popular files in ignore the factor o(F).For each s,there are Ck subsets S the users'storage.On the other hand,the files requested by the that satisfies SC U and S=s.Summing over all possible K users may also come from files in F2.Assume that there s and all subsets S,the rate needed in the first step (in the are K4 users requesting files in F1 and denote these users as unit of"bit")can be bounded by U1.Denote the other K-K4 users requesting files in F2 as 4-8+1 U2.For every S that is a subset of U and for every k E S, let Vk.s\)represent all the bits that are requested by user s立c(兴)-) k,that are stored in the cache of every other user of S except user k,and that are not stored in the caches of any other user =F1a- M1-(1-0)Ka (44) in U\S.Denote DksV.s\)as the XOR across the sets of N bitsVs)More precisely,order the bits in eachV. in some way.Then,each bit of ss\)is the XOR of <A0- the corresponding bits across V.s\),ES.Note that the Note that this bound does not depend on K4. size of sVk.s\k)equals to max{V.s\),kES). Now we are ready to present the transmission scheme, which econsists of two steps.In the first step,the server will a罗子、n出 send coded data (as in the decentralized coded caching scheme expected rate that it needs in stepisSum of [8])to meet the requests of users in U1.In the second step, ming over all K users,the expected rate of R2 (again in the the server sends uncoded data to meet the requests of users in unit of "bit")can be represented by U2.Recall that the size of U is K4. N After both steps,all requests of K users will be satisfied. R≤KF∑P (45) The reason is as follows.If a user is in U2,its request will be =N1+1 immediately satisfied in step 2.If a user k is in 01,a bit b of Combining (44)and (45),and by a conversion from the unit of its requested file will be in some V)for a specific set "bit”'to the unit of“fle”(recall that each file is unit length), S.After step 1,V.s\)will be retrieved by user k from we obtain that,the average transmission rate of scheme 1 must13 of Theorem 2, R(K, F,P) ≤ min [N1 − M]+ max(1, M) + X i>N1 Kpi , KpN3 (N3 − M) + X i>N3 Kpi ‹ , (41) where N3 = ⌊M⌋ + 1. Remark: We note that the first term is similar to the upper bound in [13]. However, the denominator is max(1, M) instead of M. Further, the second term of (41) is new. These changes are important to deal with the case when N1 < M and when M is small. Please see scheme 2 and scheme 3 in the proof below for details. Proof of Theorem 2: We prove by considering 3 schemes. We first consider scheme 1, which is most useful when N1 ≥ M and M ≥ 1. The analysis for scheme 1 is similar to [9, 13], and we include the details below for the sake of com￾pleteness. We again divide the whole file set into two subsets F1 = {F1, F2, ..., FN1 } and F2 = {FN1+1, FN1+2, ..., FN }. The files in F1 are the “more popular” files whose popularity is larger than 1 KMr . Recall that in our model each file is of unit length. The minimum indivisible portion of a file is called a “bit”. We have assumed that each file has |F| such bits. The cache placement strategy is given as follows. Algorithm 1 Cache Placement Procedure for 1 ≤ k ≤ K, 1 ≤ n ≤ N1 User k randomly caches min €M|F | N1 , |F| Š bits of the file Fn end for Note that we only cache fractions of the N1 popular files in the users’ storage. On the other hand, the files requested by the K users may also come from files in F2. Assume that there are K4 users requesting files in F1 and denote these users as U1. Denote the other K − K4 users requesting files in F2 as U2. For every S that is a subset of U1 and for every k ∈ S, let Vk,S\{k} represent all the bits that are requested by user k, that are stored in the cache of every other user of S except user k, and that are not stored in the caches of any other user in U1\S. Denote ⊕k∈SVk,S\{k} as the XOR across the sets of bits Vk,S\{k}. More precisely, order the bits in each Vk,S\{k} in some way. Then, each bit of ⊕k∈SVk,S\{k} is the XOR of the corresponding bits across Vk,S\{k}, k ∈ S. Note that the size of ⊕k∈SVk,S\{k} equals to max{|Vk,S\{k}|, k ∈ S}. Now we are ready to present the transmission scheme, which econsists of two steps. In the first step, the server will send coded data (as in the decentralized coded caching scheme of [8]) to meet the requests of users in U1. In the second step, the server sends uncoded data to meet the requests of users in U2. Recall that the size of U1 is K4. After both steps, all requests of K users will be satisfied. The reason is as follows. If a user is in U2, its request will be immediately satisfied in step 2. If a user k is in U1, a bit b of its requested file will be in some Vk,Sb\{k}, for a specific set Sb. After step 1, Vk,Sb\{k} will be retrieved by user k from Algorithm 2 Transmission Procedure Step 1: for s = K4, K4 − 1, ..., 1 for every S ⊂ U1 such that |S| = s, do Server sends ⊕k∈SVk,S\{k} end for end for Step 2: for every user k ∈ U2 Sever sends its requested file dk end for the transmission received and its local storage. Hence, user K must be able to decode the bit b. We now compute the rate required by the transmission scheme. This analysis is similar to [8]. We first calculate the rate R1 sent by the server in step 1. For a subset S ⊂ U1 and |S| = s, a bit of file dk is in Vk,S\{k} with probability ( M N1 ) s−1 (1 − M N1 ) K4−s+1 . (42) The expected number of bits in Vk,S\{k} is |F|·( M N1 ) s−1 (1− M N1 ) K4−s+1. When the file size F is large, the number of bits in Vk,S\{k} is |F| · ( M N1 ) s−1 (1 − M N1 ) K4−s+1 + o(|F|) with high probability. Therefore, the rate needed to be sent for a specific subset S is | ⊕k∈S Vk,S\{k}| = max k∈S |Vk,S\{k}| = |F| · ( M N1 ) s−1 (1 − M N1 ) K4−s+1 + o(|F|). (43) In the sequel, we focus on the “large file-size” regime and ignore the factor o(|F|). For each s, there are C s K4 subsets S that satisfies S ⊂ U1 and |S| = s. Summing over all possible s and all subsets S, the rate needed in the first step (in the unit of “bit”) can be bounded by R1 ≤ X K4 s=1 C s K4 · |F|  M N1 ‹s−1  1 − M N1 ‹K4−s+1 = |F|(1 − M N1 ) 1 − (1 − M N1 ) K4 M N1 < |F|( N1 M − 1). (44) Note that this bound does not depend on K4. Next, we calculate the rate needed for step 2. Since each user requests a file in F2 with probability PN i=N1+1 pi , the expected rate that it needs in step 2 is F PN i=N1+1 pi . Sum￾ming over all K users, the expected rate of R2 (again in the unit of “bit”) can be represented by R2 ≤ K|F| X N i=N1+1 pi . (45) Combining (44) and (45), and by a conversion from the unit of “bit” to the unit of “file” (recall that each file is unit length), we obtain that, the average transmission rate of scheme 1 must