1

On the Gap Between Decentralized and Centralized
Coded Caching Schemes

arXiv:1605.04626v2 [] 1 Aug 2017

Qifa Yan, Xiaohu Tang, and Qingchun Chen

Abstract—Caching is a promising solution to satisfy the
ongoing explosive demands for multi-media traffics. Recently,
Maddah-Ali and Niesen proposed both centralized and decentralized coded caching schemes, which are able to attain
significant performance gains over uncoded caching schemes.
Particular, their work indicates that there exists a performance
gap between the decentralized coded caching scheme and the
centralized coded caching scheme. In this paper, we investigate
this gap. As a result, we prove that the multiplicative gap (i.e.,
the ratio of their performances) is between 1 and 1.5. The
upper bound tightens the original one of 12 by Maddah-Ali
and Niesen, while the lower bound verifies the intuition that
the centralized coded caching scheme always outperforms its
decentralized counterpart. Notably, both bounds are achievable
in some cases. Furthermore, we prove that the gap can be
arbitrarily close to 1 if the number of users is large enough,
which suggests the great potential in practical applications to use
the less optimal but more practical decentralized coded caching
scheme.
Index Terms—Centralized, Decentralized, Coded Caching,
Gap, Content Delivery Networks

I. I NTRODUCTION
With the dramatic increasing demands for video streams
in many applications such as Youtube and Netflix, a huge
burden is placed on the underlying networks that deliver the
streaming data to users. One promising technique to mitigate
this burden is caching [3], whereby relatively popular contents
are prefetched at the local cache memories of the end users.
Based on the cached contents and users demands, the server
sends a signal to enable the users decode their requested files.
With the help of the content in the caches, the amount of the
transmission is reduced.
Usually, the caching network operates in two distinct
phases: In the placement phase, some fractions of the content
are disseminated to all the users’ caches in off peak times. It
should be noted that the operations in placement phase do not
depend on the actual user requests, since the server does not
have that information at this moment. In the delivery phase that
happens in peak time, the user requests are uncovered. Then
the server responds by sending a signal over the shared link to
satisfy the user requests. In conventional caching design, the
key idea is to deliver part of the content to caches close to the
end users, so that the requested content can be served locally.
Coding in the cached content or/and the transmitted signal
was typically not considered. Recently, in their seminal work
[1], [2], Maddah-Ali and Niesen showed that, by exploiting
The authors are with The School of Information Science and Technology, Southwest Jiaotong University, Chengdu, China, 610031. E-mails:
qifa@my.swjtu.edu.cn, xhutang@swjtu.edu.cn, qcchen@swjtu.edu.cn.

the cached content in the users, multicasting opportunities
can be created and thus the central server is able to send
distinct content to different users by jointly designing the
cached contents and delivered signals. This achieves a global
gain depending on the normalized cumulative caching size
in reducing the amount of delivered signals. This type of
technique is termed coded caching.
The proposed coded caching schemes in [2] and [1] are
essentially centralized and decentralized respectively. In the
centralized coded caching scheme [2], [5], the placement
phase should be coordinated by a central sever carefully
so that the content in different caches overlap to create
coded-multicasting opportunities among users with different
demands. In the delivery phase, once receiving the requests
of users, the server sends a predesignated signal that fully
exploits the coded-multicasting opportunities. Whereas, in the
decentralized coded caching scheme [1], the cached contents
at the placement phase are independent across the users. Later
in the delivery phase, after acquiring the information about
the set of users, their cached contents and requests, the server
sends a signal that efficiently exploits the coded-multicasting
opportunities existed in the contents of the end users.
Obviously, an advantage of the decentralized coded caching
scheme is that it extends the application of coded caching.
In real networks, the centralized coordination may not be
available at the placement phase in many cases. For example,
the server may not have the knowledge of the identity or even
just the number of active users in advance, or the users may
be in distinct networks during the placement phases. Whereas,
the decentralized coded caching scheme can be applied to such
circumstances, such as online scenarios [4] and random access
[6]. Notably, Maddah-Ali and Niesen proved in [1] that, the
performance of decentralized coded caching scheme is within
a constant multiplicative gap of its centralized counterpart, i.e.,
the ratio of their performances does not exceed 12. Moreover,
they claimed that the gap can be tighten to 1.6 numerically
for any system parameters.
Notably, the scheme proposed by Maddah-Ali and Niesen
achieves the best performance within uncoded scheme in
most cases [7]. Thus, it is meaningful to investigate the
aforementioned performance gap. Specifically, we prove that
the gap is between 1 and 1.5 for any system parameter setup
theoretically. The upper bound tightens the proved bound 12
and justifies the claimed numerical bound 1.6 by MaddahAli and Niesen. The lower bound verifies that the decentralized scheme is always inferior to its centralized counterpart.
Though the later conclusion seems intuitively correct, the theoretical justification has not been found to the best knowledge

2

of the authors. Furthermore, we show that in case of large
number of users, the gap always approaches 1. This indicates
that in large systems, the decentralized coded caching scheme
can be utilized in terms of both the achieved performance and
realization requirement.
The remainder of this paper is organized as follows: In
Section II, we review the network model in [1], [2] and the
corresponding schemes and performances. In Section III, we
present the main result. Section IV gives the proof of the main
result. Finally, we conclude this paper in Section V.

Generally speaking, given the parameters M, N, K and
the request (d1 , · · · , dK ), R(d1 ,··· ,dK ) should be as small as
possible. Let
4

R = max R(d1 ,··· ,dK )
d1 ,··· ,dK

be the worst-case normalized rate for a caching scheme.
Therefore, the objective is to design schemes to minimize R
in the literature.
B. Maddah-Ali and Niesen’s Coded Caching Schemes

II. N ETWORK M ODEL AND C ODED C ACHING S CHEMES
We review the model studied by Maddah-Ali and Niesen in
[1], [2] firstly, and then present their schemes and results in
this section.
A. Network Model
Consider a system consisting of a server with N popular
files W1 , W2 , · · · , WN , each of size F bits. The server is
connected to K (K ≥ 2) users K through an error-free shared
link, where K = {1, 2, · · · , K} is the set of users. Each user
k is provisioned with an isolated cache Zk with size M F bits,
where M ∈ (0, N ]1 . The system is illustrated in Fig. 1.

Fig. 1: A central server with N popular files connected to K
users through an error-free shared link. Each file is of F bits
and each user is equipped with a cache of size M F bits. In
the figure, N = K = 3, M = 1.

Maddah-Ali and Niesen first investigated the above model
and proposed a centralized and decentralized coded caching
scheme in [2] and [1], respectively. Both schemes are proved
to outperform the conventional uncoded scheme, whose rate
is given by 2




N
M
· min 1,
(1)
RU (M ) = K 1 −
N
K
In the centralized scheme, the central server is able to jointly
design the content placement in the caches Z1 , Z2 , · · · , ZK .
While in a decentralized coded caching scheme, the content in
caches Z1 , Z2 , · · · , ZK should be independent of each other.
As mentioned in Section I, since the decentralized scheme is
easier to be implemented compared to the centralized scheme,
it is worth clarifying the performance difference between them.
Theorem 1 elaborates the performance of the centralized
scheme in [2].
Theorem 1. (Centralized Coded Caching [2]) For N ∈ N+
files and K ∈ N+ users each with cache of size M = s·N/K,
s ∈ {0, 1, · · · , K}, the centralized coded caching scheme
achieves a rate




M
1
N
4
RC (M ) = K · 1 −
· min
,
N
1 + KM/N K


1
N
= (K − s) · min
,
(2)
1+s K
For general 0 < M ≤ N , the lower convex envelop of these
points is achievable, i.e.,
RC (M ) = θRC ((s − 1)N/K) + (1 − θ)RC (sN/K)

(3)

where s ∈ {1, 2, · · · , K} and θ ∈ [0, 1) satisfy

The system operates in two phases:
1. In the placement phase, the users are able to access the
whole files W1 , W2 , · · · , WN at the server. Then each
user k fills its cache Zk with some content relevant to the
files. The only constraint is that, the size of the content
should not exceed its cache size M F bits.
2. In the delivery phase, each user k requests Wdk from
the server where k ∈ K and dk ∈ {1, 2, · · · , N }. Then
the server responds by sending a signal of R(d1 ,··· ,dK ) F
bits to the users through the shared link. Then each
user k decodes its requested file Wdk from the received
signal as well as the pre-stored content in its cache Zk .
Specifically, R(d1 ,··· ,dK ) is called the rate of the system
under the request (d1 , · · · , dK ).

Comparing (1) and (4) with (2), we see that the rate in (2)
is a result of combining Algorithm 1 and the conventional
uncoded caching scheme (i.e., the server always chooses

1 For notational simplicity, we consider M ∈ (0, N ] and K ≥ 2. It is
trivial to include the case M = 0 or/and K = 1 in the result.

2 To simplify the notations, the symbols N, K do not appear in notations
of achievable rates in (1), (2) and (5).

M = θ · (s − 1)

N
N
+ (1 − θ) · s
K
K

For M ∈ {0, N/K, 2N/K, · · · , N }, Algorithm 1 illustrates
the coded caching scheme proposed in [2], where ⊕ in Line 14
is bit-wise XOR operation. It was shown in [2] that Algorithm
1 achieves the following rate


M
1
K 1−
(4)
N 1 + KM/N

3

the approach that leads to smaller rate between Algorithm
1 and the conventional uncoded scheme). For more general
M ∈ [0, N ], any point on the lower convex envelop given by
(3) is also achievable by employing so-called memory sharing
technique [2].
Algorithm 1 Centralized Coded Caching Scheme
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

procedure P LACEMENT(W1 , · · · , WN )
t ← KM
N
T ← {T ⊂ K : |T | = t}
for n ∈ {1, · · · , N } do
Split Wn into {Wn,T : T ∈ T} of equal size
end for
for k ∈ K do
Zk ← {Wn,T : n ∈ {1, · · · , N }, T ∈ T, k ∈ T }
end for
end procedure

procedure D ELIVERY(W1 , · · · , WN , d1 , · · · , dK )
t ← KM
N
S ← {S ⊂ K : |S| = t + 1}
14:
Server sends {⊕k∈S Wdk ,S\{k} : S ∈ S}
15: end procedure

11:
12:
13:

Theorem 2 depicts the performance of the decentralized
coded caching scheme in [1].
Theorem 2. (Decentralized Coded Caching [1]) For N ∈ N+
files and K ∈ N+ users each with cache of size M ∈ (0, N ],
the decentralized coded caching scheme achieves the following
rate
4

RD (M ) =
(


M
N
· min
K · 1−
N
KM



M
1− 1−
N

K !

N
,
K

)

(5)
The rate in (5) can be achieved by employing Algorithm
2, where Vk,S in Line 9 corresponds the bits of file Wdk that
are present in the cache of every user in S and absent in the
cache of the users outside S, and all the elements Vk,S\{k}
are assumed to be zero padded to the length of the longest
element. Algorithm 2 composes of two delivery procedures,
where Delivery1 and Delivery2 correspond to the first and
second items in the braces of (5) respectively. In fact, it selects
the procedure with smaller rate.
In [1], Maddah-Ali and Niesen proved that for any K, N ∈
N+ , M ∈ (0, N ],
RD (M )
≤ 12
RC (M )
Specifically, they also showed via numerical experiment that
RD (M )
≤ 1.6
RC (M )
III. M AIN R ESULTS
In this section, we first introduce the primary result of this
paper in Theorem 3.

Algorithm 2 Decentralized Coded Caching Scheme
procedure P LACEMENT(W1 , W2 , · · · , WN )
for k ∈ K, n ∈ {1, · · · , N } do
User k independently caches a subset of M F/N
bits of file Wn , chosen uniformly at random
4:
end for
5: end procedure
1:
2:
3:

procedure D ELIVERY 1(W1 , · · · , WN , d1 , · · · , dK )
for s = K, K − 1, · · · , 1 do
for S ⊂ K : |S| = s do
Server sends ⊕k∈S Vk,S\{k}
end for
11:
end for
12: end procedure
6:
7:
8:
9:
10:

procedure D ELIVERY 2(W1 , · · · , WN , d1 , · · · , dK )
for n ∈ {1, · · · , N } do
15:
Server sends enough random linear combinations
of bits in file Wn for all users requesting it to decode
16:
end for
17: end procedure
13:
14:

Theorem 3. For N ∈ N+ files and K ≥ 2 ∈ N+ users
each with a cache of size M ∈ (0, N ], the ratio between
the rates achieved by the decentralized coded caching scheme
in Algorithm 1 and the centralized coded caching scheme in
Algorithm 2 can be bounded by:
1≤

RD (M )
≤ 1.5
RC (M )

(6)

Moreover, for any fixed N ∈ N+ files and cache size M ∈
(0, N ],
lim

K→∞

RD (M )
=1
RC (M )

(7)

Firstly, the lower bound in (6) indicates that for any K, N ∈
N+ , M ∈ (0, N ],
RD (M ) ≥ RC (M )
Naturally, since all users’ caches are coordinated by the central
server jointly, the centralized coded caching scheme can
always outperform the decentralized coded caching scheme.
Though this fact is intuitively correct, the theoretical justification is not trivial.
Secondly, the upper bound of 1.5 in (6) provides a tighter
upper estimate of 12 in [1]. Actually, the upper bound is
even tighter than the numerical experimental bound of 1.6
in [1]. Indeed, this result indicates that the performance of
decentralized scheme is very close to that of the centralized
scheme for any system parameters. Furthermore, it is shown
in Section IV that
• The lower bound is achieved whenever dKM/N e <
K/N − 1 (see (21));
• The upper bound is achieved when K = 2, N ≥ 2 and
M = N/2 (see (22));

4

Thus, both the lower bound and the upper bound in (6) are
tight.
Finally, (7) depicts the case of large number of users. It is
an essentially surprising result, since it says that the rate of the
decentralized coded caching scheme approaches the rate of the
centralized coded caching scheme, for any fixed cache size M
and number of files N . In other words, for a system with large
number of users, decentralized coded caching scheme is able
to achieve almost the same rate with the centralized coded
caching. Thus in cases where the centralized coded caching
scheme can not be implemented, it is reasonable to be replaced
by the decentralized counterpart.
IV. P ROOFS OF T HEOREM 3

2) If K/N − 1 ≤ s < K/N , then
K −s
K −s+1
+ (1 − θ) ·
K
s+1
< reC (q, K)
(15)

RC (M ) = θ · N ·

3)
RD (M )
= min{rD (q, K), N − M }
(16)
(

K !
K −s+θ
K −s+θ
= min
· 1−
,
s−θ
K

K −s+θ
(17)
N·
K

A. Preliminaries
In order to derive our proof, it is more convenient to set
s = dKM/N e ∈ {1, 2, · · · , K}

Finally, we elaborate the relations between rC (q, K),
reC (q, K), and rD (q, K) as follows, which associated with
(14)-(16), will play a key role in our proof.
Lemma 1. For ∀ q ∈ (0, 1], ∀ K ∈ N+ ,

rewrite
s−1
s
s−θ
M
=θ·
+ (1 − θ) ·
=
,
N
K
K
K
θ = dKM/N e − KM/N ∈ [0, 1),
and re-express RC (M ) given by (3) as the following piecewise
function

rC (q, K) ≤ reC (q, K) ≤ rD (q, K)

(18)

and moreover, if K ≥ 3, then
rD (q, K)
< 1.5
rC (q, K)

(19)


Furthermore, for any fixed q ∈ (0, 1],
K −s+1
K −s


θ·
+ (1 − θ) ·
,


s
s
+
1


rD (q, K)


if K/N ≤ s ≤ K
(8)
=1
(20)
lim



K→∞
rC (q, K)

K −s+1
K −s
θ·N ·
+ (1 − θ) ·
,
RC (M ) =
K
s+1

The proof of Lemma 1 is left in Appendix.



if K/N − 1 ≤ s < K/N (9)





N − M,



if 1 ≤ s < K/N − 1
(10) B. Proof of The Lower Bound in Theorem 3
The proof is divided into 2 cases according to the expresFurther, to simplify the proof, we define three functions as
sions of RC (M ) in (8)-(10).
4 K(1 − q)
Case K/N − 1 ≤ s ≤ K: In this case, applying Lemma 1
(11)
rC (q, K) =
1 + Kq
to (14) and (15), we have


s

s−1
4
reC (q, K) = θ · rC
, K + (1 − θ) · rC
,K
RC (M ) ≤ reC (q, K) ≤ rD (q, K)
K
K
(12)
On the other hand, we always have

4 1−q
rD (q, K) =
1 − (1 − q)K
(13)
q
K −s
K −s+1
+ (1 − θ) · N ·
RC (M ) ≤ θ · N ·
K
K
where q ∈ (0, 1], K ∈ N+ , s = dKqe, and θ = s − Kq.
N
Obviously, if setting
=
(K − s + θ)
K

M
s−θ
q=
=
N
1
−
N
K


then we get the following relations between RC (M ) and
M
= N 1−
reC (q, K), as well as RD (M ) and rD (q, K):
N
1) If K/N ≤ s ≤ K, then
= N −M
K −s+1
K −s
+ (1 − θ) ·
s
s+1
= reC (q, K)
(14)

RC (M ) = θ ·

Thus, by (16), we have
RC (M ) ≤ RD (M )

5

Case 1 ≤ s < K/N −1: By Lemma 1, we have rC (q, K) ≤
rD (q, K), which gives

K !
1
N
M
<
1− 1−
1 + KM/N
KM
N

•

If K ≥ 3, then by (14) and (16)
RD (M ) ≤ rD (q, K)
RC (M ) = reC (q, K)
Applying Lemma 1, we have

for q = M/N ∈ (0, 1] and K ∈ N+ . Besides, note that

RD (M )
rD (q, K)
rD (q, K)
≤
≤
< 1.5
RC (M )
reC (q, K)
rC (q, K)

1
1
N
<
≤
K
1+s
1 + KM/N

Case K/N − 1 ≤ s < K/N : In this case,

Then, the above two inequalities imply

K !
N
N
M
<
1− 1−
K
KM
N

RC (M )
K −s+1
K −s
=θ · N ·
+ (1 − θ) ·
K
s+1
K
K −s+1
K −s
≥θ ·
·
+ (1 − θ) ·
s+1
K
s+1
K −s+θ
=
s+1

which means RD (M ) = N − M by (5). Whereas RC (M ) =
N − M in this case by (10), i.e.,
RC (M ) = RD (M )

(21)

Combing these two cases, we derive the lower bound.

(24)

by (15).
• If s = 1, then

C. Proof of The Upper Bound in Theorem 3
Hereafter we only need to verify the upper bound for s ≥
K/N − 1 since we have shown that RC (M ) = RD (M ) for
1 ≤ s < K/N − 1 in (21).
Case K/N ≤ s ≤ K:
• If K = 2, then
– If N = 1, then s = 2, as implied by K/N ≤ s ≤ K.
Then by (8) and (17), we have
θ
2
– If N ≥ 2, then s = 1, 2. By (8) and (17), we can
derive
3θ + (2 − s)s
RC (M ) =
s(s + 1)
RC (M ) = RD (M ) =

and
RD (M )


2−s+θ
(2 − s + θ) · (4 − s + θ)
,N ·
= min
4
2
(2 − s + θ) · (4 − s + θ)
=
4
Thus,
RD (M )
s(s + 1) (2 − s + θ) · (4 − s + θ)
=
·
RC (M )
4
3θ + s(2 − s)

(1 + θ)(3 + θ)/ (6θ + 2) , if s = 1
=
(2 + θ)/2,
if s = 2
It is easy to verify that (1 + θ)(3 + θ)/ (6θ + 2)
decreases with θ while (2 + θ)/2 increases with θ
on (0, 1). Therefore,

RD (M )
(1 + θ)(3 + θ)/ (6θ + 2)|θ=0 , if s = 1
≤
(2 + θ)/2|θ=1 ,
if s = 2
RC (M )
(22)
= 1.5

(23)

N
1
≤
<1
2
K

(25)

We can deduce two upper bounds on RD (M )/RC (M ).
On one hand, by (17) and (23), we have
RD (M )
RC (M )
N (K − 1 + θ)/K
≤
θN + (1 − θ)(K − 1)/2
θ + (1 − θ)(K − 1)/K
=
θ + (1 − θ)(K − 1)/(2N )
θ + (1 − θ)(K − 1)/K
≤
θ + (1 − θ)(K − 1)/(2(K − 1))
1 − (1 − θ)/K
=2 ·
 1+θ

2
K −2
= · 1+
K
1+θ

(26)
(27)
(28)

where in (26) we use the fact N ≤ K − 1 given by (25).
On the other hand, with (17) and (24), we then have
RD (M )
RC (M )
(K − 1 + θ)/(1 − θ) · (1 − ((K − 1 + θ)/K)K )
≤
(K − 1 + θ)/2
1 − (1 − (1 − θ)/K)K
=2 ·
(29)
1−θ


K−1
i
2 X K −1+θ
= ·
(30)
K i=0
K
Note that, by observing (27) and (28), the first upper
bound increases with K and decreases with θ. With the
n
fact that 1 − nx increases with n for n > x, (29) and
(30) indicates that the second upper bound decreases with
K and increases with θ. So, we decompose this case into
five subcases:

6

– If 2 ≤ K ≤ 3, with (28), we have


RD (M )
2
1
≤ · 1+
RC (M )
3
1+θ
4
≤
3
< 1.5
– If 4 ≤ K ≤ 8, θ > 6/25, still with (28),


RD (M )
2
6
< · 1+
RC (M )
8
1 + 6/25
181
=
124
< 1.5
– If 4 ≤ K ≤ 8, θ ≤ 6/25, with (30), we have
i
3 
RD (M )
2 X 3 + 6/25
< ·
RC (M )
4 i=0
4
≈ 1.4988
< 1.5

According to (18), we have
1≤

•

rD (q, K)
rD (q, K)
≤
reC (q, K)
rC (q, K)

The limit then follows from (20).
If M < 1, we use the expressions of RC (M ) and RD (M )
in (2) and (5), i.e.,




K
M
· min
,N
RC (M ) = 1 −
N
1 + KM/N
RD (M ) =
(
)



K !
M
N
M
1−
· min
1− 1−
,N
N
M
N
Note that as K → ∞, the first items in the braces of the
above expressions approaches N/M > N for M < 1,
we then conclude that for sufficiently large K,


M
RD (M ) = RC (M ) = N 1 −
N

Therefore, the limit is proved.

– If K ≥ 9, θ > 1/3, with (27),
2
RD (M )
<
RC (M )
1+θ
2
<
1 + 1/3
= 1.5
– If K ≥ 9, θ ≤ 1/3, with (30),
i
8 
2 X 8 + 1/3
RD (M )
≤
RC (M )
9 i=0
9
≈ 1.4993
< 1.5
•

If s ≥ 2, then by (17) and (24), we have
RD (M )
N · (K − s + θ)/K
≤
RC (M )
(K − s + θ)/(s + 1)
N
=
· (s + 1)
K
s+1
<
s
≤ 1.5

V. C ONCLUSIONS
In this paper, we investigated the ratio between the rates
of the decentralized and centralized coded caching schemes
proposed by Maddah-Ali and Niesen. We proved that for any
system parameters, the ratio is between 1 and 1.5. This verified
two facts: Firstly, the centralized scheme always outperforms
the decentralized scheme due to the central coordination of the
server. Secondly, the rate of the decentralized coded caching
scheme is within a constant multiplicative gap 1.5 of the rate
of the centralized coded caching scheme, which is tighter than
the claimed numerical upper bound 1.6 in [1]. Both the upper
bound and the lower bound are tight since they can be achieved
in some cases. Finally, we showed that when the number of
users K goes to infinity, the ratio always approaches 1. This
suggests that in the systems with large number of users, even
without the centralized coordination from the central server,
the decentralized coded caching scheme is able to achieve
almost the same performance with its centralized counterpart. Therefore, the decentralized coded caching scheme is
a reasonable alternative solution for the centralized coded
caching scheme in scenarios that the centralized coordination
is unavailable.

Collecting all the above cases, we deduce the desired upper
bound.

A PPENDIX
A. Proof of Lemma 1

D. Proof of The Limit in Theorem 3
In this subsection, we prove (7). For any fixed N ∈ N+ ,
M ∈ (0, N ],
• If M ≥ 1, since s = dKM/N e ≥ K/N , then RC (M ) is
given by (14). It is easy to check that RD (M ) is evaluated
by the first item in (5), thus RD (M ) = rD (q, K) by (16).
Therefore,
RD (M )
rD (q, K)
=
RC (M )
reC (q, K)

Proof of (18): We prove that for ∀ q ∈ (0, 1], K ∈ N+ ,
rC (q, K) ≤ reC (q, K) ≤ rD (q, K)
Note that rC (q, K) is convex on q ∈ (0, 1). Moreover, we
have
s−θ
q=
(31)
K
s−1
s
=θ
+ (1 − θ)
K
K

7

since s = dKqe and θ = s − Kq. Then, the first inequality
follows from the well-known Jensen’s inequality.
For the second inequality, by substituting (31) into (12) and
(13) respectively, it is therefore sufficient to prove
K −s+1
K −s
+ (1 − θ) ·
s
s+1

K !
s−θ
1 − (s − θ)/K
1− 1−
≤
(s − θ)/K
K


s−θ
K +1
K +1
θ
+
−1
K
s(s + 1)
s+1


K !

s−θ
s−θ
· 1− 1−
≤ 1−
K
K
θ·

⇔

f (θ, n, s)
n−s
n+1 2
≥
+
θ
n(s + 1) ns(s + 1)

n+1

s n+1
s−1
− (1 − θ) 1 −
−θ 1−
n
n

n−s
n+1
s n+1
=
+
− 1−
n(s + 1)
n
ns(s + 1)
!!

n+1 
s−1
ns(s + 1)
s n+1
2
1−
· θ −θ
− 1−
n+1
n
n
(32)

In what follows, we only need to verify f (θ, n, s) ≥ 0 for
any θ, n and s, s.t., θ ∈ [0, 1), n, s ∈ N+ , n ≥ s.
+
• If s = n ∈ N ,
 n+1
θ2
θ
f (θ, n, n) = 2 −
n
n
 n−1 !
θ
θ2
= 2 1−
n
n
≥0
•

If s ≥ 2 and n > s, we begin with a lower bound for
f (θ, n, s). Note that (1 − x)n+1 is convex on x ∈ (0, 1).
Thus, using Jensen’s inequality we have
n+1

s−θ
1−
n
n+1

s
s−1
− (1 − θ)
= 1−θ
n
n

n+1

s−1
s n+1
≤θ 1 −
+ (1 − θ) 1 −
n
n
Then by (32),

for all K ∈ N+ , s ∈ {1, 2, · · · , K} and θ ∈ [0, 1)
Define
f (θ, n, s)
 

n 

s−θ
s−θ
· 1− 1−
= 1−
n
n


s−θ
n+1
n+1
−
θ
+
−1
n
s(s + 1)
s+1

n+1
n−s
n+1 2
s−θ
=
+
θ − 1−
n(s + 1) ns(s + 1)
n

•

If s = 1 and n > s, then

n+1
n−1+θ
n−1 n+1 2
+
θ −
2n
2n
n


n 
∂f (θ, n, 1)
n+1
n−1+θ
=
θ−
(33)
∂θ
n
n

When θ
=
ns(s + 1)/(2(n
+ 1)) ·

(1 − (s − 1)/n)n+1 − (1 − s/n)n+1 , the righthand
side achieves its minimal value, which is defined as
g(n, s)

n−s
s n+1 1 ns(s + 1)
=
− ·
− 1−
n(s + 1)
n
4
n+1
!2

n+1 

s−1
s n+1
·
1−
− 1−
n
n


1
s
s n+1 s(s + 1)
n
=
−
− 1−
−
·
s + 1 n(s + 1)
n
4
n+1

2n+2

n+1 !2
s−1
1
· 1−
· 1− 1−
n
n−s+1
4

f (θ, n, 1) =

and
∂ 2 f (θ, n, 1)
n+1
=
∂θ2
n


1−

n−1+θ
n

n−1 !

∀ θ ∈ (0, 1)

> 0,
(34)

(34) tells us that (33) is increasing on θ ∈ (0, 1).
Therefore, it follows that
∂f (θ, n, 1)
∂f (θ, n, 1)
<
∂θ
∂θ

= 0, ∀ θ ∈ (0, 1)
θ=1

which indicates that f (θ, n, 1) is decreasing on θ ∈ [0, 1),
thus
f (θ, n, 1) ≥ f (1, n, 1) = 0, ∀ θ ∈ [0, 1)

Note the fact that both the items (1 − s/n)n+1 and
2n+2
(1 − (s − 1)/n)
strictly increases with n > s and

s n+1
= e−s
lim 1 −
n→∞
n

2n+2
s−1
lim 1 −
= e−2s+2
n→∞
n
which implies (1 − s/n)n+1
<
e−s and
2n+2
−2s+2
(1 − (s − 1)/n)
<e
. Therefore, we have
g(n, s)
s
e2 s(s + 1)
1
−
− e−s −
·
≥
s + 1 n(s + 1)
4
e2s
!
2

n+1
1
· 1− 1−
n−s+1
4

=h(n, s)

8

Up to now, we have derived

•

f (θ, n, s) ≥ g(n, s) ≥ h(n, s) ∀ θ ∈ [0, 1)

If x ∈ (0, 3],
ln (x) ≤ sup ln (z)

(35)

z∈(0,3]

≤ sup l3 (z)

Note that h(n, s) increases with n since the positive numn+1
ber (1 − 1/(n − s + 1))
increases with n. Therefore,

z 3 − 8z 2 + 18z + 27
27
z∈(0,3]

= sup

– If s ≥ 4, it is easy to check that e2s > 4s(s + 1)3
and es > 2(s+1)2 for s ≥ 4. Consequently, we have

z 3 − 8z 2 + 18z + 27
27
√
1001 + 20 10
=
729
≈ 1.4599
=

h(n, s)
≥h(s + 1, s)
1
s
e2 s(s + 1)
− e−s −
>
−
·
2
s + 1 (s + 1)
4
e2s
1
1
e2
s
1
>
−
−
−
·
2
2
s + 1 (s + 1)
2(s + 1)
16 (s + 1)2


2
e
1
1
−
·
=
2 16
(s + 1)2
>0
(36)
where in (36) we make use of the fact e2 < 8.
– If s = 3, n ≥ 5, we have
h(n, 3) ≥ h(5, 3) ≈ 0.0045 > 0

– For other cases, i.e, s = 3, n = 4 or s = 2, n =
3, 4, 5, 6, 7, we compute g(n, s) directly
g(4, 3) ≈ 0.0593 > 0,

g(3, 2) ≈ 0.0602 > 0

g(4, 2) ≈ 0.0845 > 0,

g(5, 2) ≈ 0.0953 > 0

g(6, 2) ≈ 0.1012 > 0,

g(7, 2) ≈ 0.1047 > 0

Therefore, we conclude f (θ, n, s) > 0 for θ ∈ [0, 1) and
2 ≤ s < n, by (35).
Proof of (19): We prove that
rD (q, K)
< 1.5
rC (q, K)
for all K ≥ 3 ∈ N+ and q ∈ (0, 1].
Note from (11) and (13),

4

4

ln (x) =


1+x
x n 
1− 1−
< 1.5
x
n

for any x ∈ (0, n], where n ≥ 3 and n ∈ N+ .

< 1.5

•

where in (38) we use the fact that for any fixed z ∈ (0, 3],
n
(1 − z/n) increases with n.
If 3 < x ≤ n, then
1+x
ln (x) ≤
x
1+3
<
3
< 1.5

R EFERENCES

h(n, 2) ≥ h(8, 2) ≈ 0.0004 > 0

where x = Kq. Therefore, it suffices to show

√

z= 8−3 10

Proof of (20): The limit (20) is clear from the expression
(37).

– If s = 2, n ≥ 8, we have


rD (q, K)
1 + Kq
=
1 − (1 − q)K
rC (q, K)
Kq



1+x
x K
=
1− 1−
x
K

(38)

z∈(0,3]

(37)

[1] M. A. Maddah-Ali and U. Niesen, “Decentralized coded caching
attains order-optimal memory-rate tradeoff,” IEEE/ACM Transactions
on Networking, vol. 23, no. 4, pp. 1029–1040. [Online]. Available:
http://dx.doi.org/10.1109/TNET.2014.2317316
[2] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,”
IEEE Transactions on Information Theory, vol. 60, no. 5, pp. 2856–2867,
2014.
[3] N. Golrezaei, A. F. Molisch, A. G. Dimakis, and G. Caire, “Femtocaching
and device-to-device collaboration: A new architecture for wireless video
distribution,” Communications Magazine, IEEE, vol. 51, no. 4, pp. 142–
149, 2013.
[4] R. Pedarsani, M. A. Maddah-Ali, and U. Niesen, “Online coded
caching,” in IEEE International Conference on Communications, ICC
2014, Sydney, Australia, June 10-14, 2014, 2014, pp. 1878–1883.
[5] Q. Yan, M. Cheng, X. Tang, and Q. Chen, “On the placement
delivery array design for centralized coded caching scheme,” IEEE
Transactions on Information Theory, 2017. [Online]. Available: http:
//dx.doi.org/10.1109/TIT.2017.2725272
[6] Q. Yan, U. Parampalli, X. Tang, and Q. Chen, “Online coded caching
with random access,” Communications Letters, IEEE, vol. 21, no. 3, pp.
552–555, March, 2017.
[7] K. Wan, D. Tuninetti and P. Piantanida, “On the optimality of uncoded
cache placement,” in IEEE Information Theory Workshop, (ITW), Sep,
11-15, 2016, 2016.

