1

Information-Theoretic Privacy for Smart Metering
Systems with a Rechargeable Battery

arXiv:1510.07170v4 [cs.IT] 15 Sep 2017

Simon Li, Ashish Khisti, and Aditya Mahajan

Abstract—Smart-metering systems report electricity usage of a
user to the utility provider on almost real-time basis. This could
leak private information about the user to the utility provider.
In this work we investigate the use of a rechargeable battery in
order to provide privacy to the user.
We assume that the user load sequence is a first-order Markov
process, the battery satisfies ideal charge conservation, and
that privacy is measured using normalized mutual information
(leakage rate) between the user load and the battery output.
We study the optimal battery charging policy that minimizes
the leakage rate among the class of battery policies that satisfy
causality and charge conservation. We propose a series reductions
on the original problem and ultimately recast it as a Markov
Decision Process (MDP) that can be solved using a dynamic
program.
In the special case of i.i.d. demand, we explicitly characterize
the optimal policy and show that the associated leakage rate can
be expressed as a single-letter mutual information expression. In
this case we show that the optimal charging policy admits an
intuitive interpretation of preserving a certain invariance property of the state. Interestingly an alternative proof of optimality
can be provided that does not rely on the MDP approach, but is
based on purely information theoretic reductions.

I. I NTRODUCTION
Smart meters are a critical part of modern power distribution
systems because they provide fine-grained power consumption
measurements to utility providers. These fine-grained measurements improve the efficiency of the power grid by enabling
services such as time-of-use pricing and demand response [1].
However, this promise of improved efficiency is accompanied
by a risk of privacy loss. It is possible for the utility provider—
or an eavesdropper—to infer private information including
load taxonomy from the fine-grained measurements provided
by smart meters [2]–[4]. Such private information could be
exploited by third parties for the purpose of targeted advertisement or surveillance. Traditional techniques in which an
intermediary anonymizes the data [5] are also prone to privacy
loss to an eavesdropper. One possible solution is to partially
obscure the load profile by using a rechargeable battery [6]. As
the cost of rechargeable batteries decreases (for example, due
to proliferation of electric vehicles), using them for improving
privacy is becoming economically viable.
Simon Li was with the University of Toronto when this work was done.
Ashish Khisti (akhisti@ece.utoronto.ca) is with the University of Toronto,
Toronto, ON, Canada. Aditya Mahajan (aditya.mahajan@mcgill.ca) is with
McGill University, Montreal, QC, Canada.
Preliminary version of this work was presented at the Signal Processing for
Advanced Wireless Communications (SPAWC), Jul. 2015, Stockholm, Sweden, International Zurich Seminar (IZS), Mar. 2-4, 2016, Zurich, Switzerland
and the American Control Conference (ACC), July 6-8, 2016, Boston, MA,
USA.

In a smart metering system with a rechargeable battery, the
energy consumed from the power grid may either be less than
the user’s demand—the rest being supplied by the battery; or
may be more than the user’s demand—the excess being stored
in the battery. A rechargeable battery provides privacy because
the power consumed from the grid (rather than the user’s
demand) gets reported to the electricity utility (and potentially
observed by an eavesdropper). In this paper, we focus on
the mutual information between the user’s demand and consumption (i.e., the information leakage) as the privacy metric.
Mutual Information is a widely used metric in the literature
on information theoretic security, as it is often analytically
tractable and provides a fundamental bound on the probability
of detecting the true load sequence from the observation [7].
Our objective is to identify a battery management policy
(which determine how much energy to store or discharge from
the battery) to minimize the information leakage rate.
We briefly review the relevant literature. The use of a
rechargeable battery for providing user privacy has been
studied in several recent works, e.g., [6], [8]–[11]. Most of the
existing literature has focused on evaluating the information
leakage rate of specific battery management policies. These
include the “best-effort” policy [6], which tries to maintain a
constant consumption level, whenever possible; and battery
conditioned stochastic charging policies [8], in which the
conditional distribution on the current consumption depends
only on the current battery state (or on the current battery state
and the current demand). In [6], the information leakage rate
was estimated using Monte-Carlo simulations; in [8], it was
calculated using the BCJR algorithm [12]. The methodology
of [8] was extended by [9] to include models with energy
harvesting and allowing for a certain amount of energy waste.
Bounds on the performance of the best-effort policy and hideand-store policy for models with energy harvesting and infinite
battery capacity were obtained in [10]. The performance of
the best effort algorithm for an individual privacy metric was
considered in [11]. None of these papers address the question
of choosing the optimal battery management policy.
Rate-distortion type approaches have also been used to study
privacy-utility trade-off [13]–[15]. These models allow the user
to report a distorted version of the load to the utility provider,
subject to a certain average distortion constraint. Our setup
differs from these works as we impose a constraint on the
instantaneous energy stored in the battery due to its limited
capacity. Both our techniques and the qualitative nature of the
results are different from these papers.
Our contributions are two-fold. First, when the demand is
Markov, we show that the minimum information leakage rate

2

and optimal battery management policies can be obtained by
solving an appropriate dynamic program. These results are
similar in spirit to the dynamic programs obtained to compute
capacity of channels with memory [16]–[18]; however, the
specific details are different due to the constraint on the battery
state. Second, when the demand is i.i.d., we obtain a single
letter characterization of the minimum information leakage
rate; this expression also gives the optimal battery management
policy. We prove the single letter expression in two steps. On
the achievability side we propose a class of policies with a
specific structure that enables a considerable simplification of
the leakage-rate expression. We find a policy that minimizes
the leakage-rate within this restricted class. On the converse
side, we obtain lower bounds on the minimal leakage rate and
show that these lower bound match the performance of the best
structured policy. We provide two proofs. One is based on the
dynamic program and the other is based purely on information
theoretic arguments.
After the present work was completed, we became aware
of [19], where a similar dynamic programming framework is
presented for the infinite horizon case. However, no explicit
solutions of the dynamic program are derived in [19]. To the
best of our knowledge, the present paper is the first work that
provides an explicit characterization of the optimal leakage
rate and the associated policy for i.i.d. demand.
A. Notation
Random variables are denoted by uppercase letters (X, Y ,
etc.), their realization by corresponding lowercase letters (x, y,
etc.), and their state space by corresponding script letters (X ,
Y, etc.). PX denotes the space of probability distributions on
X ; PX|Y denotes the space of condition distributions from Y
to X . Xab is a short hand for (Xa , Xa+1 , . . . , Xb ) and X b =
X1b . For a set A, 1A (x) denotes the indicator function of the
set that equals 1 if x ∈ A and zero otherwise. If A is a
singleton set {a}, we use 1a (x) instead of 1{a} (x).
Given random variables (X, Y ) with joint distribution
PX,Y (x, y) = PX (x)q(y|x), H(X) and H(PX ) denote the
entropy of X, H(Y |X) and H(q|PX ) denote conditional
entropy of Y given X and I(X; Y ) and I(q; PX ) denote the
mutual information between X and Y .
II. P ROBLEM F ORMULATION AND M AIN R ESULTS
A. Model and problem formulation
Consider a smart metering system as shown in Fig. 1. At
each time, the energy consumed from the power grid must
equal the user’s demand plus the additional energy that is either stored in or drawn from the battery. Let {Xt }t≥1 , Xt ∈ X ,
denote the user’s demand; {Yt }t≥1 , Yt ∈ Y, denote the energy
drawn from the grid; and {St }t≥1 , St ∈ S, denote the energy
stored in the battery. All alphabets are finite. For convenience,
we assume X := {0, 1, . . . , mx }, Y := {0, 1, . . . , my }, and
S = {0, 1, . . . , ms }. Here ms corresponds to the size of
the battery. We note that such a restriction is for simplicity
of presentation; the results generalize even when X and Y
are not necessarily contiguous intervals or integer valued. To

Home
Applicances

Demand: 𝑋𝑡

Consumption: 𝑌𝑡

Smart Meter
Controller

Power
Grid

𝑌𝑡 − 𝑋 𝑡
Battery
(State 𝑆𝑡 )

Eavesdropper/
Adversory

Fig. 1. A smart metering system.

guarantee that user’s demand is always satisfied, we assume
mx ≤ my or that X ⊆ Y holds more generally.
The demand {Xt }t≥1 is a first-order time-homogeneous
Markov chain1 with transition probability Q. We assume
that Q is irreducible and aperiodic. The initial state X1 is
distributed according to probability mass function PX1 . The
initial charge S1 of the battery is independent of {Xt }t≥1 and
distributed according to probability mass function PS1 .
The battery is assumed to be ideal and has no conversion
losses or other inefficiencies. Therefore, the following conservation equation must be satisfied at all times:
St+1 = St + Yt − Xt .

(1)

Given the history of demand, battery charge, and consumption, a randomized battery charging policy q = (q1 , q2 , . . . )
determines the energy consumed from the grid. In particular,
given the histories (xt , st , y t−1 ) of demand, battery charge,
and consumption at time t, the probability that current consumption Yt equals y is qt (y | xt , st , y t−1 ). For a randomized
charging policy to be feasible, it must satisfy the conservation
equation (1). So, given the current power demand and battery
charge (xt , st ), the feasible values of grid consumption are
defined by
Y◦ (st − xt ) = {y ∈ Y : st − xt + y ∈ S}.

(2)

Thus, we require that
qt (Y◦ (st − xt ) | xt , st , y t−1 ) :=

X

qt (y | xt , st , y t−1 ) = 1.

y∈Y◦ (st −xt )

The set of all such feasible policies is denoted by QA 2 . Note
that while the charging policy qt (·) can be a function of the
entire history, the support of qt (·) only depends on the present
value of xt and st through the difference st − xt . This is
emphasized in the definition in (2).
The quality of a charging policy depends on the amount
of information leaked under that policy. There are different
notions of privacy; in this paper, we use mutual information
as a measure of privacy. Intuitively speaking, given random
variables (Y, Z), the mutual information I(Y ; Z) measures
1 In practice, the energy demand is periodic rather than time homogeneous.
We are assuming that the total demand may be split into a periodic predictable
component and a time-homogeneous stochastic component. In this paper, we
ignore the predictable component because it does not affect privacy.
2 With a slight abuse of notation, we use Q to denote the battery policy
A
for both the infinite and finite-horizon problems

3

the decrease in the uncertainty about Y given by Z (or viceversa). Therefore, given a policy q, the information about
(X T , S1 ) leaked to the utility provider or eavesdropper is
captured by I q (X T , S1 ; Y T ), where the mutual information
is evaluated according to the joint probability distribution on
(X T , S T , Y T ) induced by the distribution q as follows:

𝑥 = 0/𝑦 = 0

𝑥 = 0/𝑦 = 0
𝑥 = 0/𝑦 = 1

𝑠=0

𝑠=1

𝑥 = 1/𝑦 = 0
Pq (S T = sT , X T = xT , Y T = y T )
𝑥 = 1/𝑦 = 1
𝑥 = 1/𝑦 = 1
T 
Y
= PS1 (s1 )PX1 (x1 )q1 (y1 | x1 , s1 )
1st {st−1 −xt−1 +yt−1 } Fig. 2. Binary System model. The battery can be either in s = 0 or s = 1.
The set of feasible transitions from each state are shown in the figure.
t=2

× Q(xt |xt−1 )qt (yt | xt , st , y t−1 ) .
B. Example: Binary Model
We use information leakage rate as a measure of the
We illustrate the special case when X = Y = S = {0, 1}
quality of a charging policy. For a finite planning horizon, the
in Fig. 2. The input, output, as well as the state, are all
information leakage rate of a policy q = (q1 , . . . , qT ) ∈ QA
binary valued. When the battery is in state st = 0, there
is given by
are three possible transitions. If the input xt = 1 then we
1 q T
T
(3) must select yt = 1 and the state changes to st+1 = 0. If
LT (q) := I (X , S1 ; Y ),
T
instead xt = 0, then there are two possibilities. We can select
while for an infinite horizon, the worst-case information leak- yt = 0 and have st+1 = 0 or we can select yt = 1 and
have st+1 = 1. In a similar fashion there are three possible
age rate of a policy q = (q1 , q2 , . . . ) ∈ QA is given by
transitions from the state st = 1 as shown in Fig. 2. We will
L∞ (q) := lim sup LT (q).
(4) assume that the demand (input) sequence is sampled i.i.d. from
T →∞
an equiprobable distribution, i.e., PX (0) = PX (1) = 12 .
We are interested in the following optimization problems:
Consider a simple policy that sets yt = xt and ignores the
Problem A. Given the alphabet X of the demand, the initial battery state. It is clear that such a policy will lead to maximum
distribution PX1 and the transistion matrix Q of the demand leakage LT = 1. Another feasible policy is to set yt = 1 − st .
process, the alphabet S of the battery, the initial distribution Thus whenever st = 0, we will set yt = 1 regardless of the
PS1 of the battery state, and the alphabet Y of the consump- value of xt , and likewise st = 1 will result in yt = 0. It turns
out that the leakage rate for this policy also approaches 1. To
tion:
T
1) For a finite planning horizon T , find a battery charging see this note thatT the eavesdropper having access to y also
s . Using the battery update equation (1) the
policy q = (q1 , . . . , qT ) ∈ QA that minimizes the in turn knows
T −1
sequence
x
is thus revealed to the eavesdropper, resulting
leakage rate LT (q) given by (3).
in
a
leakage
rate
of at least 1 − 1/T .
2) For an infinite planning horizon, find a battery charging
In
reference
[8],
a probabilistic battery charging policy is
policy q = (q1 , q2 , . . . ) ∈ QA that minimizes the
introduced
that
only
depends on the current state and input i.e.,
leakage rate L∞ (q) given by (4).
∆
qt (yt |xt , st ) = qt (yt |xt , st ). Furthermore the policy makes
The above optimization problem is difficult because we equiprobable decisions between the feasible transitions i.e.,
have to optimize a multi-letter mutual information expression
over the class of history dependent probability distributions.
qt (yt = 0|xt , st ) = q(yt = 1|xt , st ) = 1/2, if xt = st (5)
In the spirit of results for feedback capacity of channels
with memory [16]–[18], we show that the above optimization
problem can be reformulated as a Markov decision process and qt (yt |xt , st ) = 1xt (yt ) otherwise. The leakage rage for
where the state and action spaces are conditional probability this policy was numerically evaluated in [8] using the BCJR
distributions. Thus, the optimal policy and the optimal leakage algorithm and it was shown numerically that L∞ = 0.5. Such
rate can be computed by solving an appropriate dynamic numerical techniques seem necessary in general even for the
program. We then provide an explicit solution of the dynamic class of memoryless policies and i.i.d. inputs, as the presence
of the battery adds memory into the system.
program for the case of i.i.d. demand.
As a consequence of our main result it follows that the
Remark 1. We note that the class of policies we consider in
above policy admits a single-letter expression for the leakage
QA are randomized policies i.e., the output at any given time
rate3 L∞ = I(S ∗ − X; X), thus circumventing the need for
is governed by the conditional distribution qt (yt | xt , st , y t−1 ).
numerical techniques. Furthermore it also follows that this
The class of deterministic policies where yt = ht (xt , st , y t−1 )
leakage rate is indeed the minimum possible one among the
is a deterministic function of the past inputs, state and outputs
class of all feasible policies. Thus it is not necessary for the
is a special case of randomized policies where qt (·) is an
battery system to use more complex policies that take into
atomic distribution. As will be apparent from out results,
deterministic policies do not suffice to minimize the leakage
3 The random variable S ∗ is an equiprobable binary valued random variable,
rate and hence we focus on the class of randomized policies. independent of X. See Sec. II-E.

4

account the entire history. We note that a similar result was
shown in [20] for the case of finite horizon policies. However
the proof in [20] is specific to the binary model. In the present
paper we provide a complete single-letter solution to the case
of general i.i.d. demand, and a dynamic programming method
for the case of first-order Markovian demands, as discussed
next.
C. Main results for Markovian demand
We identify two structural simplifications for the battery
charging policies. First, we show (see Proposition 1 in Section III-A) that there is no loss of optimality in restricting
attention to charging policies of the form
qt (yt |xt , st , y t−1 ).

(6)

The intuition is that under such a policy, observing y t gives
partial information only about (xt , st ) rather than about the
whole history (xt , st ).
Next, we identify a sufficient statistic for y t−1 when the
charging policies are of the form (6). For that matter, given a
policy q and any realization y t−1 of Y t−1 , define the belief
state πt ∈ PX,S as follows: for all x ∈ X , s ∈ S,
πt (x, s) = Pq (Xt = x, St = s|Y t−1 = y t−1 ).

(7)

Then, we show (see Theorems 1 and 2 below) that there is no
loss of optimality in restricting attention to charging policies
of the form
qt (yt |xt , st , πt ).
(8)

where the function ϕ is a non-linear filtering equation defined
in Sec. III-C.
Our main results are the following:
Theorem 1. We have the following for Problem A with a finite
planning horizon T :
1) Value functions: Iteratively define value functions
Vt : PX,S → R as follows. For any π ∈ PX,S ,
VT +1 (π) = 0, and for t ∈ {T, . . . , 1},
Vt (π) = min[Ba Vt+1 ](π),
a∈A

∀(x, s) ∈ X × S . (9)
The set A is convex and compact.4
To succinctly write the dynamic program, for any a ∈ A, we
define the Bellman operator Ba : [PX,S → R] → [PX,S → R]
as follows: for any V : PX,S → R and any π ∈ PX,S ,
[Ba V ](π) = I(a; π)
X
+
π(x, s)a(y | x, s)V (ϕ(π, y, a)) (10)
x∈X ,s∈S,
y∈Y
4 If a , a ∈ A, then any linear combination a0 of them, where a0 =
1 2
λa1 + (1 − λ)a2 with λ ∈ (0, 1), also satisfies a0 (Y◦ (s − x | x, s) = 1
for all (x, s) ∈ X × S and, therefore, belongs to A. Hence A is convex.
Moreover, it is easy to see that A is closed and PY |X,s is compact. Therefore,
A is also compact.

(11)

Then, Vt (π) are is continuous and concave in π.
2) Optimal policy: Let ft∗ (π) denote the arg min of the
right hand side of (11). Then, optimal policy q∗ =
(q1∗ , . . . , qT∗ ) is given by
qt∗ (yt | xt , st , πt ) = at (yt | xt , st ), where at = ft∗ (πt ).
Thus, there is no loss of optimality in restricting attention to charging policies of the form (8).
3) Optimal leakage rate: The optimal (finite horizon) leakage rate is given by V1 (π1 )/T , where π1 (x, s) =
PX1 (x)PS1 (s).
See Section III for proof.
Theorem 2. We have the following for Problem A with an
infinite planning horizon:
1) Value function: Consider the following fixed point equation
J + v(π) = min[Ba v](π),
a∈A

Such a charging policy is Markovian in the belief state πt
and the optimal policies of such form can be searched using
a dynamic program.
To describe such a dynamic program, we assume that there
is a decision maker that observes y t−1 (or equivalently πt ) and
chooses “actions” at = qt (·|·, ·, πt ) using some decision rule
at = ft (πt ). We then identify a dynamic program to choose
the optimal decision rules.
Note that the actions at take vales in a subset A of PY |X,S
given by

A = a ∈ PY |X,S : a(Y◦ (s − x) | x, s) = 1,

∀π ∈ PX,S .

∀π ∈ PX,S ,

(12)

where J ∈ R is a constant and v : PX,S → R.
2) Optimal policy: Suppose there exists (J, v) that satisfy (12). Let f ∗ (π) denote the arg min of the right hand
side of (12). Then, the time-homogeneous optimal policy
q∗ = (q ∗ , q ∗ , . . . ) given by
q ∗ (yt | xt , st , πt ) = a(yt | xt , st ), where a = f ∗ (π)
is optimal. Thus, there is no loss of optimality in restricting attention to charging time-homogeneous policies of
the form (8).
3) Optimal leakage rate: The optimal (infinite horizon)
leakage rate is given by J.
Proof. Given the result of Theorem 1, the result of Theorem 2
follows from standard dynamic programming arguments. See,
for example, [21, Theorem 5.2.4 and Eq. (5.2.18)].
There are various conditions that guarantee the existence of
a (J, v) that satisfies (12). Most of these conditions require the
ergodicity of the process {Πt }t≥1 for every standary Markov
procily f : PX,S → A. We refer the reader to [22, Chapter 3]
and [23, Chapter 10] for more details.
The dynamic program above resembles the dynamic program for partially observable Markov decision processes
(POMDP) (see [24, Chapter 5]) with hidden state (Xt , St ), observation Yt , and action At . However, in contrast to POMDPs,
the expected per-step cost I(a; π) is not linear in π. Nonetheless, one could use computational techniques from POMDPs

5

to approximately solve the dynamic programs of Theorems 1
and 2. See Section III-D for a brief discussion.

E. Binary Model (Revisited)

Remark 2. Although the above results assume that the demand
is a first-order Markov chain, they extend naturally to the
case when the demand is higher-order Markov. In particular, suppose the demand {Xt }t≥1 is a k-th order Markov
chain. Then, we can define another process {X̃t }t≥1 where
X̃t = (Xt−k+1 , . . . , Xt ), and use X̃t in Theorems 1 and 2.

We revisit the binary model in Section II-B, where the
demand has equiprobable distribution, i.e., PX (x) = 12 for
x ∈ {0, 1}. Consider θ(0) = p, θ(1) = 1−p. Let W = S −X.
Then,

1

if w = −1
 2 p,
1
P(W = w) = 2 ,
(17)
if w = 0

1
(1
−
p),
if
w
=
1.
2

D. Main result for i.i.d. demand

Thus,

Assume the following:

I(W ; X) = H(W ) − H(S) = 1 − 21 h(p)

Assumption (A). The demand {Xt }t≥1 is i.i.d. with probability distribution PX .
We provide an explicit characterization of optimal policy
and optimal leakage rate for this case.
Define an auxiliary state variable Wt = St − Xt that takes
values in W = {s − x : s ∈ S, x ∈ X }. For any w ∈ W,
define:
D(w) = {(x, s) ∈ X × S : s − x = w}.

(13)

Theorem 3. Define
θ∈PS

θ∈PS

(14)

where X and S are independent with X ∼ PX and S ∼
∗
θ.
arg min in (14). Define ξ ∗ (w) =
P Let θ denote the
∗
(x,s)∈D(w) PX (x)θ (s). Then, under (A)
1) J ∗ is the optimal (infinite horizon) leakage rate.
2) Define b∗ ∈ PY |W as follows:
(
∗
if y ∈ X ∩ Y◦ (w)
PX (y) θ ξ(y+w)
∗ (w)
∗
b (y|w) =
0
otherwise .
(15)
We call b∗ as a structured policy with respect to (θ∗ , ξ ∗ ).
Then, the memoryless charging policy q∗ = (q1∗ , q2∗ , . . . )
given by
qt∗ (y | x, s, πt ) = b∗ (y | s − x)

h(p) = −p log p − (1 − p) log(1 − p).
Thus, the value of p that minimizes I(W ; X) is p∗ = 12 and
the optimal leakage rate is I(W ; X) = 21 .
The corresponding ξ ∗ is obtained by substituting p = 12
in (17). For ease of notation, we denote b∗ (·|w) as
[b∗ (0|w), b∗ (1|w)]. Then,
b∗ (·| − 1) = [0, 1],

Then, we have the following.


J ∗ = min I(S −X; X) = min H(S − X) − H(S)

where h(p) is the binary entropy function:

(16)

is optimal and achieves the optimal (infinite horizon)
leakage rate.
Note that the optimal charging policy is time-invariant and
memoryless, i.e., the distribution on Yt does not depend on πt
(and, therefore on y t−1 ).
The proof, which is presented in Section IV, is based
on the standard arguments of showing achievability and a
converse. On the achievability side we show that the policy
in (15) belongs to a class of policies that satisfies a certain
invariance property. Using this property the multi-letter mutual
information expression can be reduced into a single-letter
expression. For the converse we provide two proofs. The
first is based on a simplification of the dynamic program of
Theorem 2. The second is based on purely probabilistic and
information theoretic arguments.

b∗ (·|0) = [ 12 , 21 ],

b∗ (·| − 1) = [1, 0].

It can be shown that this strategy is the same as (5), which
was proposed in [8]. This yields an analytical proof of the
result in [8].
F. Salient features of the result for i.i.d. demand
Theorem 3 shows that even if consumption could take larger
values than the demand, i.e., Y ⊃ X , under the optimal policy,
Yt takes values only in X . This agrees with the intuition that
a consumption larger that mx reveals that the battery has low
charge and that the power demand is high. In extreme cases,
a large consumption may completely reveal the battery and
power usage thereby increasing the information leakage.
We now show some other properties of the optimal policy.
Property 1. The mutual information I(S − X; X) is strictly
convex in the distribution θ and, therefore, θ∗ ∈ int(PS ).
See Appendix A for proof.
As a consequence, the optimal θ∗ in (14) may be obtained
using the Blahut-Arimoto algorithm [25], [26].
Property 2. Under the battery charging policy specified in
Theorem 3, the power consumption {Yt }t≥1 is i.i.d. with
marginal distribution PX . Thus, {Yt }t≥1 is statistically indistinguishable from {Xt }t≥1 .
See Remarks 3 and 5 in Section IV-B for proof.
Property 3. If the power demand has a symmetric PMF, i.e.,
for any x ∈ X , PX (x) = PX (mx − x), then the optimal θ∗
in Theorem 3 is also symmetric, i.e., for any s ∈ S, θ∗ (s) =
θ∗ (ms − s).
Proof. For θ ∈ PS , define θ̄(s) = θ(ms − s). Let X ∼ PX ,
S ∼ θ and S̄ ∼ θ̄. Then, by symmetry
I(S − X; X) = I(S̄ − X; X).

(18)

6

For any λ ∈ (0, 1), let θλ (s) = λθ(s) + (1 − λ)θ̄(s) denote the
convex combination of θ and θ̄. Let Sλ ∼ θλ . By Property 1,
if θ 6= θ̄, then

Leakage Rates for Binomial Distributed Power Demand

1

10

Jeq for mx = 5
J* for mx = 5
Jeq for mx = 10

I(Sλ − X; X) < λI(S − X; X) + (1 − λ)I(S − X; X)

J* for mx = 10

0

= I(S − X; X),

10
Leakage Rate

where the last equation uses (18).
Thus, if θ 6= θ̄, we can strictly decrease the mutual
information by using θλ . Hence, the optimal distribution must
have the property that θ∗ (s) = θ∗ (ms − s).

Jeq for mx = 20
J*

for mx = 20

−1

10

Given a distribution µ on some alphabet M, we say that the
distribution is almost symmetric and unimodal around m∗ ∈
M if
−2

10

µm∗ ≥ µm∗ +1 ≥ µm∗ −1 ≥ µm∗ +2 ≥ µm∗ −2 ≥ . . .
where we use the interpretation that for m 6∈ M, µm = 0.
Similarly, we say that the distribution is symmetric and unimodal around m∗ ∈ M if

0

5

10

15

20

25
30
Battery Size

35

40

45

50

Fig. 3. A comparison of the performance of qeq ∈ QB as defined

in (19) with the optimal leakage rate for i.i.d. Binomial distributed
demand Binomial(mx , 0.5) for mx = {5, 10, 20}.

µm∗ ≥ µm∗ +1 = µm∗ −1 ≥ µm∗ +2 = µm∗ −2 ≥ . . .
Note that a distribution can be symmetric and unimodal only
if its support is odd.
Property 4. If the power demand is symmetric and unimodal
around bmx /2c, then the optimal θ∗ in Theorem 3 is almost
symmetric and unimodal around bms /2c. In particular, if ms
is even, then
∗
θm
∗

≥

∗
θm
∗ +1

=

∗
θm
∗ −1

≥

∗
θm
∗ +2

=

∗
θm
∗ −2

≥ ...

and if ms is odd, then
∗
∗
∗
∗
∗
θm
∗ = θm∗ +1 ≥ θm∗ −1 = θm∗ +2 ≥ θm∗ −2 = . . .

where m∗ = bms /2c.
Proof. Let X̄ = −X. Then, I(S − X; S) = H(S − X) −
H(S) = H(S + X̄) − H(S). Note that PX̄ is also symmetric
and unimodal around bmx /2c.
Let S ◦ and X̄ ◦ denote the random variables S − bms /2c
and X̄ − bmx /2c. Then X̄ ◦ is also symmetric and unimodal
around the origin and
I(S − X; X) = H(S ◦ + X̄ ◦ ) − H(S ◦ ).
Now given any distribution θ◦ of S ◦ , let θ+ be a permutation of θ◦ that is almost symmetric and unimodal with a
positive bias around origin. Then by [27, Corollary III.2],
H(PX ∗ θ◦ ) ≥ H(PX ∗ θ+ ). Thus, the optimal distribution
must have the property that θ◦ = θ+ or, equivalently, θ is
almost unimodal and symmetric around bms /2c.
Combining this with the result of Property 3 gives the characterization of the distribution when ms is even or odd.
G. Numerical Example: i.i.d. demand
Suppose there are n identical devices in the house and each
is on with probability p. Thus, X ∼ Binomial(n, p). We derive
the optimal policy and optimal leakage rate for this scenario
under the assumption that Y = X . We consider two specific
examples, where we numerically solve (14).

Suppose n = 6 and p = 0.5.
1) Consider S = [0:5]. Then, by numerically solving (14),
we get that the optimal leakage rate J ∗ is is 0.4616 and
the optimal battery charge distribution θ∗ is
{0.1032, 0.1747, 0.2221, 0.2221, 0.1747, 0.1032}.
2) Consider S = [0:6]. Then, by numerically solving (14),
we get that the optimal leakage rate J ∗ is is 0.3774 and
the optimal battery charge distribution θ∗ is
{0.0773, 0.1364, 0.1847, 0.2031, 0.1847, 0.1364, 0.0773}.
Note that both results are consistent with Properties 3 and 4.
We next compare the performance with the following timehomogeneous benchmark policy qeq ∈ QB : for all y ∈ Y, w ∈
W,
1Y◦ (wt ) {yt }
qt (yt |wt ) =
.
(19)
|Y◦ (wt )|
This benchmark policy chooses all feasible values of Yt with
equal probability. For that reason we call it equi-probably
policy and denote its performance by Jeq .
In Fig. 3, we compare the performance of q∗ and qeq as a
function of battery sizes for different demand alphabets.
Under qeq , the MDP converges to a belief state that is
approximately uniform. Hence, in the low battery size regime,
Jeq is close to optimal but its performance gradually worsens
with increasing battery size.
H. Numerical Example: Continuous Valued Alphabets
Although our setup assumes discrete alphabets, it can shown
that Theorem 3 can be extended to continuous alphabets under
mild technical conditions assuming that the density function
for X, say fX (x) exists; see [28] for details. As such we
provide two achievability proofs for Theorem 3. The weak
achievability in Section IV-B assumes that the distribution
of the initial state S1 can be selected by the user. The
strong achievability in Section IV-C assumes that the initial

7

state S1 can be arbitrary. The proof of the weak achievability extends immediately to continuous valued alphabets.
Furthermore the proof of the converse based on information
theoretic arguments in Section IV-E also extends to continuous
valued alphabets. We provide a numerical example involving
a continuous valued input.
Let X = [0, 1] be continuous valued, and let fX (x) = 1 for
x ∈ [0, 1]. We assume that S = [0, B] where B denotes the
storage capacity. We will assume that B ≥ 2 for convenience.
Following Theorem 3, it suffices to take the output alphabet
to be Y = [0, 1]. Note that for W = S − X, we have that
W = [−1, B] and that the support of the output for any given
w is given by:


−1 ≤ w ≤ 0,
[−w, 1],
Y◦ (w) = [0, 1],
(20)
0 ≤ w ≤ B − 1,


[0, B − w], B − 1 ≤ w ≤ B.

For the achievability, we evaluate the leakage rate by
selecting θ? (s) to be a uniform distribution over [0, B] and
using (21). The resulting leakage rate is given by

Let θ? (·) be the density function that minimizes (14) and S ?
denote the random variable with this density, independent of
X. Let W = S ? − X and ξ ? (w) be the associated density.
Then it follows from (15) that the optimal policy is given by

and thus it follows that

?

b? (y|w) =

θ (y + w)
,
ξ ? (w)

y ∈ Y◦ (w).

(21)

Instead of computing θ? (·) numerically, which is cumbersome
due to the density functions, we provide an analytical lower
bound on the leakage rate. Note that the objective in (14) can
be expressed as:
I(S − X; X) = h(S − X) − h(S)

(22)

where h(·) is the differential entropy. Using the entropy power
inequality [29], since S and X are independent, we have for
any density fS (·) that:
22h(S−X) ≥ 22h(S) + 22h(X) ,

L+ = h(W ) − h(S) = h(ξ) − log2 (B)
where the density ξ(w) for W

1+w

 B ,
ξ(w) = B1 ,

 B−w
B ,

(27)

= S − X is as follows:
−1 ≤ w ≤ 0
0≤w ≤B−1
B−1≤w ≤B

and we use that when θ(s) is a uniform density over [0, B],
it follows that h(S) = log2 (B). Through straightforward
computations it can be shown that
h(ξ) =

1
+ log2 (B)
2B ln 2

L+ =

(28)

1
2B ln 2

is achievable with a uniform distribution on the state. We note
that the analytical lower bound on the leakage rate in (26)
decays as 1/B 2 for large B while the achievable rate decays as
1/B. It will be interesting in future to determine the structure
of the optimal input distribution and study the associated
leakage rate.
III. P ROOF OF T HEOREM 1
One of the difficulties in obtaining a dynamic programming
decomposition for Problem
A is that the objective function
PT
is not of the form
cost(state
t , actiont ). We show that
t=1
there is no loss of optimality to restrict attention to a class of
policies QB and for any policy in QB , the mutual information
may be written in an additive form.

(23)

where we use the fact that h(−X) = h(X). Substituting
in (22) we have


1
I(S − X; X) ≥ log2 22h(S) + 22h(X) − h(S)
2


1
= log2 1 + 22h(X)−2h(S)
2


1
= log2 1 + 2−2h(S)
(24)
2


1
≥ min log2 1 + 2−2h(S)
S 2


1
= log2 1 + 2−2{maxS h(S)}
(25)
2


1
1
= log2 1 + 2
(26)
2
B
where we use the fact that when X ∼ Unif[0, 1], we have
that h(X) = 0, see e.g., [30] in (24) and the fact that the
expression in (25) is decreasing in h(S). Finally in (26) we use
the fact that a uniform distribution maximizes the differential
entropy when S = [0, B] is fixed and the maximum value is
h(S) = log2 B.

A. Simplification of optimal charging policies
Let QB ⊂ QA denote the set of charging policies that
choose consumption xd only on the consumption history,
current demand, and battery state. Thus, for q ∈ QB , at any
time t, given history (xt , st , y t−1 ), the consumption Yt is y
with probability qt (y | xt , st , y t−1 ). Then the joint distribution
on (X T , S T , Y T ) induced by q ∈ QB is given by
Pq (S T = sT , X T = xT , Y T = y T )
T 
Y
= PS1 (s1 )PX1 (x1 )q1 (y1 | x1 , s1 )
1st {st−1 −xt−1 +yt−1 }
t=2


× Q(xt |xt−1 )qt (yt | xt , st , y t−1 ) .
Proposition 1. In Problem A, there is no loss of optimality in
restricting attention to charging policies in QB . Moreover, for
any q ∈ QB , the objective function takes an additive form:
LT (q) =

T
1X q
I (Xt , St ; Yt | Y t−1 )
T t=1

8

where
I q (Xt , St ; Yt | Y t−1 )
X
=
Pq (Xt = xt , St = st , Y t = y t )
xt ∈X ,st ∈S
qt (yt | xt , st , y t−1 )
y t ∈Y t
× log q
.
P (Yt = yt | Y t−1 = y t−1 )
See Appendix B for proof. The intuition behind why policies in QB are no worse that others in QA is as follows.
For a policy in QA , observing the realization y t of Y t gives
partial information about the history (xt , st ) while for a policy
in QB , yt gives partial information only about the current
state (xt , st ). The dependence on (xt , st ) cannot be removed
because of the conservation constraint (1).
Proposition 1 shows that the total cost may be written in an
additive form. Next we use an approach inspired by [16]–[18]
and formulate an equivalent sequential optimization problem.
B. An equivalent sequential optimization problem
Consider a system with state process {Xt , St }t≥1 where
{Xt }t≥1 is an exogenous Markov process as before and
{St }t≥1 is a controlled Markov process as specified below.
At time t, a decision maker observes Y t−1 and chooses a
distribution valued action At ∈ A, where A is given by (9),
as follows:
At = ft (Y t−1 )
(29)
where f = (f1 , f2 , . . . ) is called the decision policy.
Based on this action, an auxiliary variable Yt ∈ Y is chosen
according to the conditional probability at (· | xt , st ) and the
state St+1 evolves according to (1).
At each stage, the system incurs a per-step cost given by
at (yt | xt , st )
. (30)
ct (xt , st , at , y t ; f ) := log f
P (Yt = yt | Y t−1 = y t−1 )
The objective is to choose a policy f = (f1 , . . . , fT ) to
minimize the total finite horizon cost given by
" T
#
1 f X
t
L̃T (f ) := E
ct (Xt , St , At , Y ; f )
(31)
T
t=1
where the expectation is evaluated with respect to the probability distribution Pf induced by the decision policy f .
Proposition 2. The sequential decision problem described
above is equivalent to Problem A. In particular,
1) Given q = (q1 , . . . , qT ) ∈ QB , let f = (f1 , . . . , fT ) be
ft (y t−1 ) = qt (· | ·, ·, y t−1 ).

Thus, the probability distribution on (X T , S T , Y T ) induced
by a decision policy f = (f1 , . . . , fT ) is given by
Pf (S T = sT , X T = xT , Y T = y T )
= PS1 (s1 )PX1 (x1 )q1 (y1 | x1 , s1 )

T 
Y
1st {st−1 −xt−1 +yt−1 }
t=2


× Q(xt |xt−1 )at (yt |xt , st ) .
where at = ft (y t−1 ). Under the transformations described
in the Proposition, Pf and Pq are identical probability distributions. Consequently, Ef [ct (Xt , St , At , Y t ; f )] =
I q (St , Xt ; Yt | Y t−1 ). Hence, LT (q) and L̃T (f ) are equivalent.
Eq. (32) implies that {Xt , St }t≥1 is a controlled Markov
process with control action {At }t≥1 . In the next section,
we obtain a dynamic programming decomposition for this
problem. For the purpose of writing the dynamic program,
it is more convenient to write the policy (29) as
At = ft (Y t−1 , At−1 ).

(33)

Note that these two representations are equivalent. Any policy
of the form (29) is also a policy of the form (33) (that simply
ignores At−1 ); any policy of the form (33) can be written
as a policy of the form (29) by recursively substituting At in
terms of Y t−1 . Since the two forms are equivalent, in the next
section we assume that the policy is of the form (33).
C. A dynamic programming decomposition
The model described in Section III-B above is similar to a
POMDP (partially observable Markov decision process): the
system state (Xt , St ) is partially observed by a decision maker
who chooses action At . However, in contrast to the standard
cost model used in POMDPs, the per-step cost depends on
the observation history and past policy. Nonetheless, if we
consider the belief state as the information state, the problem
can be formulated as a standard MDP.
For that matter, for any realization y t−1 of past observations
and any choice at−1 of past actions, define the belief state
πt ∈ PX,S as follows: For s ∈ S and x ∈ X ,
πt (x, s) = Pf (Xt = x, St = s|Y t−1 = y t−1 , At−1 = at−1 ).
If Y t−1 and At−1 are random variables, then the belief state
is a PX,S -valued random variable.
The belief state evolves in a state-like manner as follows.

Then L̃T (f ) = LT (q).
2) Given f = (f1 , . . . , fT ), let q = (q1 , . . . , qT ) ∈ QB be

Lemma 1. For any realization yt of Yt and at of At , πt+1 is
given by
qt (yt | xt , st , y t−1 ) = at (yt | xt , st ), where at = ft (y t−1 ).
πt+1 = ϕ(πt , yt , at )
(34)
Then LT (q) = L̃T (f ).
t

where ϕ is given by
t

Proof. For any history (x , s , y
t

t

t

t−1

t

), a ∈ A, and st+1 ∈ S,

t

t

t

t

t

P(St+1 = st+1 | X = x , S = s , Y = y , A = a )
X
=
1st+1 {st + yt − xt } at (yt | xt , st )
yt ∈Y

= P(St+1 = st+1 | Xt = xt , St = st , At = at ). (32)

ϕ(π, y, a)(x0 , s0 )
P
Q(x0 |x)a(y|x, s0 − x + y)π(x, s0 − x + y)
P
.
= x∈X
(x,s)∈X ×S a(y|x, s)π(x, s)
Proof. For ease of notation, we use P(xt , st |y t−1 , at−1 ) to
denote P(Xt = xt , St = st |Y t−1 = y t−1 , At−1 = at−1 ).

9

Similar interpretations hold for other expressions as well.
Consider
πt+1 (xt+1 , st+1 ) = P(xt+1 , st+1 |y t , at )
P(xt+1 , st+1 , yt , at |y t−1 , at−1 )
=
P(yt , at |y t−1 , at−1 )

(35)

Now, consider the numerator of the right hand side.
P(xt+1 , st+1 , yt , at |y t−1 , at−1 )
= P(xt+1 , st+1 , yt , at |y t−1 , at−1 , πt )
X
=
P(xt+1 |xt )1st+1 (st + xt − yt )

x∈X ,s∈S,
y∈Y

(xt ,st )∈X ×S

× at (yt |xt , st )1at (ft (y

t−1

t−1

,a

))πt (xt , st )

Lemma 2 implies that the objective function can be expressed
in terms of the state Πt and the action At . Thus, one can use
Markov decision theory [21] to identify the optimal policy.
Since both the state space and the action space are continuous
valued, we need to verify the standard technical conditions.
Define the stochastic kernel K : PX,S × A → PX,S as
follows. For any Borel subset B of PX,S and any π ∈ PX,S
and a ∈ A,
X
π(x, s)a(y | x, s)1B {ϕ(π, y, a))}.
K(B | π, a) =

(36)

Substituting (36) in (35) (and observing that the denominator of the right hand side of (35) is the marginal of
the numerator over (xt+1 , st+1 )), we get that πt+1 can be
written in terms of πt , yt and at . Note that if the term
1at (ft (y t−1 , at−1 )) is 1, it cancels from both the numerator
and the denominator; if it is 0, we are conditioning on a null
event in (35), so we can assign any valid distribution to the
conditional probability.
Note that an immediate implication of the above result is
that πt depends only on (y t−1 , at−1 ) and not on the policy f .
This is the main reason that we are working with a policy of
the form (33) rather than (29).
Lemma 2. The cost L̃T (f ) in (31) can be written as

X
T
1
L̃T (f ) = E
I(At ; Πt )
T
t=1
where I(at ; πt ) does not depend on the policy f and is
computed according to the standard formula
X
I(at ; πt ) =
πt (x, s)at (y | x, s)
x∈X ,s∈S,
at (y|x, s)
y∈Y
× log X
.
πt (x̃, s̃)at (y | x̃, s̃)
(x̃,s̃)∈X ×S

Proof. By the law of iterated expectations, we have
X

T
1
t
t−1
t−1
L̃T (f ) = E
E[ct (Xt , St , At , Y ; f )|Y
,A ]
T
t=1
(37)
Now, from (30), each summand may be written as
Ef [ct (Xt , St , At , Y t ; f ) | Y t−1 = y t−1 , At = at ]
X
=
πt (x, s)at (y | x, s)
x∈X ,s∈S,
at (y|x, s)
y∈Y
× log X
πt (x̃, s̃)at (y | x̃, s̃)
(x̃,s̃)∈X ×S

= I(at ; πt ).
Thus, Ef [ct (Xt , St , Y t ; f | Y t−1 , At ] = I(At , Πt ). Substituting this back in (37), we get the result of the Lemma.
Proof of Theorem 1. Lemma 1 implies that {Πt }t≥1 is a
controlled Markov process with control action At . In addition,

The sequential model of Sec. III-B has the following properties.
1) Based on (32), we can write the controlled dynamics of
the state (Xt , St ) as follows:
P(Xt+1 = x+ , St+1 = s+ | Xt = x, St = s, At = a)
X
=
Q(x+ |x)a(y)1s+ {s + y − x},
y∈Y

which is continuous in a.
2) The observations are given by
P(Yt = y|Xt = x, St = s, At = a) = a(y)
which is continuous in a.
3) The observations Yt are discrete.
Therefore, from [22, Sec 4.4 and Lemma 4.1], we get the
following:
4) The stochastic kernel K(dπ+ | π, a) is weakly continuous.
In addition, the model has the following properties:
5) The action set A is compact.
6) The per-step cost I(a, π) is continuous and bounded
below. (In fact, the per-step cost is also bounded above).
Properties 4)–6) imply [21, Condition 3.3.3], which by [21,
Theorem 3.3.5], implies the measurable selection condition [21, Assumption 3.3.1]. Under the measurable selection
condtion, the “inf” in the dynamic program can be replaced
by a “min”.
The continuity of the value function in π follows from
the continuity of the per-step cost I(a, π)and the controlled
stochastic kernel K(dπ+ | π, a). The concavity of the value
functions is proved in Appendix C.
From standard results in Markov decision theorem (e.g.,
see [21, Theorem 3.2.1]), it follows that the policy given in
part 2) of the theorem is optimal for the sequential model of
Sec III-B. Proposition 2 implies that this policy is also optimal
for Problem A.
D. Remarks about numerical solution
The dynamic programs of Theorems 1 and 2, both state and
action spaces are distribution valued (and, therefore, subsets of
Euclidean space). Although, an exact solution of the dynamic
program is not possible, there are two approaches to obtain
an approximate solution. The first is to treat it as a dynamic
program of an MDP with continuous state and action spaces

10

and use approximate dynamic programming [24], [31]. The
second is to treat it as a dynamic program for a POMDP and
use point-based methods [32]. The point-based methods rely
on concavity of the value function, which was established in
Theorem 1.
IV. P ROOF OF T HEOREM 3
We follow the standard approach and show that the proposed leakage rate is optimal by showing achievability and
a converse. As a preliminary step, we first show that under
assumption (A), the objective can be rewritten in a simpler
but equivalent form. To show achievability, we show that the
proposed optimal policy belongs to a class of policies that
satisfies a certain invariance property. Using this property the
multi-letter mutual information expression can be reduced into
a single-letter expression. For the converse we provide two
proofs: the first uses dynamic programming and the second
uses purely probabilistic and information theoretic arguments.
A. Simplification of the dynamic program
Define

Then, under Assumption (A), we can simplify the belief state
πt as follows:
πt (x, s) = P(Xt = x, St = s|Y t−1 = y t−1 , At−1 = at−1 )
(a)

= P(Xt = x|St = s, Y t−1 = y t−1 , At−1 = at−1 )
× P(St = s | Y t−1 = y t−1 , At−1 = at−1 )

(b)

= PX (x)θt (s)

where (a) follows from the product rule of probability and (b)
uses Assumption (A) and the definition of θt .
Since πt (x, s) = PX (x)θt (s), in principle, we can simplify
the dynamic program of Theorem 2 by using θt as an information state. However, for reasons that will become apparent, we
provide an alternative simplification that uses an information
state ξt ∈ PW .
Recall that Wt = St − Xt which takes values in W =
{s − x : s ∈ S, x ∈ X }. For any realization (y t−1 , at−1 ) of
past observations and actions, define ξt ∈ PW as follows: for
any w ∈ W,
ξt (w) = P (Wt = w | Y

t−1

=y

t−1

t−1

,A

=a

t−1

).

If Y t−1 and At−1 are random variables, then ξt is a PW valued random variable. As was the case for πt , it can be
shown that ξt does not depend on the choice of the policy f .
Lemma 3. Under Assumption (A), θt and ξt are related as
follows:
X
ξt (w) =
PX (x)θt (s).
(38)
(x,s)∈D(w)

Proof.
ξt (w) = Pf (Wt = w | Y t−1 = y t−1 , At−1 = at−1 )
= Pf (St − Xt = w | Y t−1 = y t−1 , At−1 = at−1 )
X
=
PX (x)θt (s).
(x,s)∈D(w)

Lemma 4. Given a ∈ A and π ∈ PX,S , define the following:
P
• ξ ∈ PW as ξ(w) =
(x,s)∈D(w) π(x, s)
• b ∈ B as follows: for all y ∈ Y, w ∈ W
P
(x,s)∈D(w) a(y | x, s)π(x, s)
;
b(y | w) =
ξ(w)
•

ã ∈ A as follows: for all y ∈ Y, x ∈ X , s ∈ S
ã(y|x, s) = b(y|s − x).

θt (s) = Pf (St = s | Y t−1 = y t−1 , At−1 = at−1 ).

f

Since πt (x, s) = PX (x)θt (s), Lemma 3 shows that ξt is a
function of πt . We will show that we can simplify the dynamic
program of Theorem 2 by using ξt as the information state
instead of πt . For such a simplification to work, we would
have to use charging policies of the form qt (yt |wt , y t−1 ). We
establish that restricting attention to such policies is without
loss of optimality. For that matter, define B as follows:

B = b ∈ PY |W : b(Y◦ (w) | w) = 1, ∀w ∈ W .
(39)

Then under Assumption (A), we have
1) Invariant Transitions: for any y ∈ Y, ϕ(π, y, a) =
ϕ(π, y, ã).
2) Lower Cost: I(a; π) ≥ I(ã; π) = I(b; ξ).
Therefore, in the sequential problem of Sec. III-B, there is no
loss of optimality in restricting attention to actions b ∈ B.
Proof. 1) Suppose (X, S) ∼ π and W = S − X, S+ =
W + Y , X+ ∼ PX . We will compare P(S+ |Y ) when
Y ∼ a(·|X, S) with when Y ∼ ã(·|X, S). Given w ∈ W
and y ∈ Y,
X
Pa (W = w, Y = y) =
a(y|x, s)π(x, s)
(x,s)∈D(w)

=

X

b(y|w)π(x, s)

(x,s)∈D(w)
(a)

=

X

ã(y|x, s)π(x, s)

(x,s)∈D(w)
ã

= P (W = w, Y = y)

(40)

where (a) uses that for all (x, s) ∈ D(w), s − x = w.
Marginalizing (40) over W , we get that Pa (Y = y) =
Pã (Y = y). Since S+ = W + Y , Eq. (40) also implies
Pa (S+ = s, Y = y) = Pã (S+ = s, Y = y). Therefore,
Pa (S+ = s|Y = y) = Pã (S+ = s|Y = y).
2) Let (X, S) ∼ π and W = S − X. Then W ∼ ξ.
Therefore, we have
I(a; π) = I a (X, S; Y ) ≥ I a (W ; Y ).
where the last inequality is the data-processing inequality. Under ã, (X, S) − W − Y , therefore,
I(ã; π) = I ã (X, S; Y ) = I ã (W ; Y ).
Now, by construction, the joint distribution of (W, Y ) is
the same under a, ã, and b. Thus,
I a (W ; Y ) = I ã (W ; Y ) = I b (W ; Y ).

11

Note that I b (W ; Y ) can also be written as I(b; ξ). The
result follows by combining all the above relations.
Once attention is restricted to actions b ∈ B, the update of
ξt may be expressed in terms of b ∈ B as follows:
Lemma 5. For any realization yt of Yt and bt of Bt , ξt+1 is
given by
ξt+1 = ϕ̃(ξt , yt , bt )
(41)
where ϕ̃ is given by
ϕ̃(ξ, y, b)(w+ )
P
=

x∈X ,w∈W

PX (x)1w+ {y + w − x}b(y | w)ξ(w)
P
.
w∈W b(y | w)ξ(w)

Proof. The proof is similar to the proof of Lemma 1.
For any b ∈ B and ξ ∈ PW , let us define the Bellman
operator B̃b : [PW → R] → [PW → R] as follows: for any
Ṽ : PW → R and any ξ ∈ PW ,
X

[B̃b Ṽ ](ξ) = I(b; ξ) +
ξ(w)b(y | w)Ṽ ϕ̃(ξ, y, b) .
y∈Y,w∈W

Theorem 4. Under assumption (A), there is no loss of optimality in restricting attention to optimal policies of the form
qt (yt |wt , ξt ) in Problem A.
1) For the finite horizon case, we can identify the optimal
policy q∗ = (q1∗ , . . . , qT∗ ) by iteratively defining value
functions Ṽt : PW → R. For any ξ ∈ PW , ṼT +1 (ξ) = 0,
and for t = T, T − 1, . . . , 1,
Ṽt (ξ) = min[B̃b Ṽt+1 ](ξ).

(42)

b∈B

Let ft◦ (ξ) denote the arg min of the right hand side
of (42). Then, the optimal policy q∗ = (q1∗ , . . . , qT∗ ) is
given by
qt∗ (yt |wt , ξt )

= bt (yt |wt ), where bt =

ft◦ (ξt ).

Moreover, the optimal (finite horizon) leakage
rate
is given by Ṽ1 (ξ1 )/T , where ξ1 (w)
=
P
P
(x)P
(s).
X
S
1
(x,s)∈D(w)
2) For the infinite horizon, suppose that there exists a
constant J˜ ∈ R and a function ṽ : PS → R which
satisfies the following fixed point equation:
J˜ + ṽ(ξ) = min[B̃b ṽ](ξ), ∀ξ ∈ PW .
b∈B

(43)

◦

Let f (ξ) denote the arg min of the right hand side
of (43). Then, the time-homogeneous policy q∗ =
(q ∗ , q ∗ , . . . ) given by
q ∗ (yt |wt , ξt ) = bt (yt |wt ), where bt = f ◦ (ξt )
is optimal. Moreover, the optimal (infinite horizon) leak˜
age rate is given by J.
Proof. Lemma 5 implies that {ξt }t≥1 is a controlled Markov
process with control action bt . Lemma 4, part 2), implies that
the per-step cost can be written as
X

T
1
E
I(bt ; ξt ) .
T
t=1

Thus, by standard results in Markov decision theory [21], the
optimal solution is given by the dynamic program described
above.
B. Weak achievability
To simplify the analysis, we assume that we are free to
choose the initial distribution of the state of the battery, which
could be done by, for example, initially charging the battery
to a random value according to that distribution. In principle,
such an assumption could lead to a lower achievable leakage
rate. For this reason, we call it weak achievability. In the next
section, we will show achievability starting from an arbitrary
initial distribution, which we call strong achievability.
Definition 1 (Constant-distribution policy). A timehomogeneous policy f ◦ = (f ◦ , f ◦ , . . . ) is
called a
constant-distribution policy if for all ξ ∈ PW , f ◦ (ξ) is a
constant. If f ◦ (ξ) = b◦ , then with a slight abuse of notation,
we refer to b◦ = (b◦ , b◦ , . . . ) as a constant-distribution
policy.
Recall that under a constant-distribution policy b ∈ B, for
any realization y t of Y t , θt and ξt are given as follows:
θt (s) = P(St = s | Y t−1 = y t−1 , B t−1 = bt−1 )
ξt (w) = P(Wt = w | Y t−1 = y t−1 , B t−1 = bt−1 ).
1) Invariant Policies: We next impose an invariance property on the class of policies. Under this restriction the leakage
rate expression will simplify substantially. Subsequently we
will show that the optimal policy belongs to this restricted
class.
Definition 2 (Invariance Property). For a given distribution θ1
of the initial battery state, a constant-distribution policy b ∈ B
is called an invariant policy if for all t, θt = θ1 and ξt = ξ1 ,
where ξ1 and θ1 satisfy (38).
Remark 3. An immediate implication of the above definition is that under any invariant policy b, the conditional
distribution Pb (Xt , St , Yt |Y t−1 ) is the same as the joint
distribution Pb (X1 , S1 , Y1 ). Marginalizing over (X, S) we get
that {Yt }t≥1 is an i.i.d. sequence.
Lemma 6. If the system starts with an initial distribution θ of
the battery state, and ξ and θ satisfy (38), then an invariant
policy b = (b, b, . . . ) corresponding to (θ, ξ) achieves a
leakage rate
LT (b) = I(W1 ; Y1 ) = I(b; ξ)
for any horizon T .
Proof. The proof is a simple corollary of the invariance property in Definition 2. Recall from the dynamic program of Theorem 4, that the performance of any policy b = (b1 , b2 , . . . )
such that bt ∈ B, is given by
X

T
1
I(bt ; ξt ) .
LT (b) = E
T
t=1

12

Now, we start with an initial distribution ξ1 = ξ and follow
the constant-distribution structured policy b = (b, b, . . . ).
Therefore, by Definition 2, ξt = ξ for all t. Hence, the leakage
rate under policy b is
LT (b) = I(b; ξ).

LT (b) =

1
T

I b (St , Xt ; Yt |Y t−1 ).

Pb (S2 = s2 , Y1 = y1 ) = Pb (S2 = s2 , Y1 = y1 , W1 = s2 − y1 )
= ξ1 (s2 − y1 )b(y1 |s2 − y1 )

Remark 4. Note that Lemma 6 can be easily derived independently of Theorem 4. From Proposition 1, we have that:
T
X

of S2 and y1 of Y1 . This means that w1 = s2 − y1 . Since Y1 is
chosen according to b(·|w1 ), it must be that y1 ∈ X ∩ Y◦ (w1 ).
Therefore,

(44)

t=1

From Remark 3, we have that I b (St , Xt ; Yt |Y t−1 ) =
I b (S1 , X1 ; Y1 ) = I b (W1 ; Y1 ), which immediately results in
Lemma 6.
For invariant policies we can express the leakage rate in the
following fashion, which is useful in the proof of optimality.
Lemma 7. For any invariant policy b,
I b (W1 ; Y1 ) = I b (W1 ; X1 ).
Proof. Consider the following sequence of simplifications:
I b (W1 ; Y1 ) = H b (W1 ) − H b (W1 |Y1 )
= H b (W1 ) − H b (W1 + Y1 |Y1 )
(a)

= H b (W1 ) − H b (S2 |Y1 )
(b)

= H b (W1 ) − H b (S1 )

(c)

= H b (W1 ) − H b (S1 |X1 )
(d)

= H b (W1 ) − H b (W1 |X1 )

= I b (W1 ; X1 ).
where (a) is due to the battery update equation (1); (b) is
because b is an invariant ; (c) is because S1 and X1 are
independent; and (d) is because S1 = W1 + X1 .
2) Structured Policy: We now introduce a class of policies
that satisfy the invariance property in Def. 2. This will be then
used in the proof of Theorem 3.
Definition 3 (Structured Policy). Given θ ∈ PS and ξ ∈ PW ,
a constant-distribution policy b = (b, b, . . . ) is called a
structured policy with respect to (θ, ξ) if:
(
PX (y) θ(y+w)
ξ(w) , y ∈ X ∩ Y◦ (w)
b(y|w) =
0,
otherwise.
Note that it is easy to verify that the distribution b defined
above is a valid conditional probability distribution.
Lemma 8. For any θ ∈ PS and ξ ∈ PW , the structured policy
b = (b, b, . . . ) given in Def. 3 is an invariant policy.
Proof. Since (θt , ξt ) are related according to Lemma 3, in
order to check whether a policy is invariant it is sufficient to
check that θt = θ1 for all t. Furthermore, to check if a timehomogeneous policy is an invariant policy, it is sufficient to
check that either θ2 = θ1 .
Let the initial distributions (θ1 , ξ1 ) = (θ, ξ) and the system
variables be defined as usual. Now consider a realization s2

= PX (y1 )θ1 (s2 ),

(45)

where in the last equality we use the fact that y1 ∈ X ∩
Y◦ (s2 − y1 ). Note that if y1 6∈ X ∩ Y◦ (s2 − y1 ), then Pb (S2 =
s2 , Y1 = y1 ) = 0. Marginalizing over s2 , we get Pb (Y1 =
y1 ) = PX (y1 ).
Consequently, θ2 (s2 ) = Pb (S2 = s2 |Y1 = y1 ) = θ1 (s2 ).
Hence, b is invariant as required.
Remark 5. As argued in Remark 3, under any invariant policy,
{Yt }t≥1 is an i.i.d. sequence. As argued in the proof of
Lemma 8, for a structured policy the marginal distribution of
Yt is PX . Thus, an eavesdropper cannot statistically distinguish
between {Xt }t≥1 and {Yt }t≥1 .
Proposition 3. Let θ∗ , ξ ∗ , and b∗ be as defined in Theorem 3.
Then,
1) (θ∗ , ξ ∗ ) satisfy (38);
2) b∗ is a structured policy with respect to (θ∗ , ξ ∗ ).
3) If the system starts in the initial battery state θ∗ and follows the constant-distribution policy b∗ = (b∗ , b∗ , . . . ),
the leakage rate is given by J ∗ .
Thus, the performance J ∗ is achievable.
Proof. The proofs of parts 1) and 2) follows from the definitions. The proof of part 3) follows from Lemmas 6 and 7.
This completes the proof of the achievability of Theorem 3.
C. Strong achievability
Lemma 9. Assume that for any x ∈ X , PX (x) > 0. Let
(θ◦ , ξ ◦ ) be a pair satisfying (38) and b◦ = (b◦ , b◦ , . . . ) be
the corresponding structured policy.
Assume that θ◦ ∈ int(PS ) or equivalently, for any w ∈ W
and y ∈ X ∩ Y◦ (w), b◦ (y|w) > 0. Suppose the system starts
in the initial state (θ1 , ξ1 ) and follows policy b◦ . Then:
1) the process {θt }≥1 converges weakly to θ◦ ;
2) the process {ξt }≥1 converges weakly to ξ ◦ ;
3) for any continuous function c : PW → R,
T
1X
E[c(ξt )] = c(ξ ◦ ).
T →∞ T
t=1

lim

(46)

4) Consequently, the infinite horizon leakage rate under
b◦ is
L∞ (b◦ ) = I(b◦ , ξ ◦ ).
Proof. The proof of parts 1) and 2) is presented in Appendix D. From 2), limt→∞ E[c(ξt )] = c(ξ ◦ ), which implies (46). Part 4) follows from part 3) by setting c(ξt ) =
I(b◦ , ξt ).
Proposition 1 implies that θ∗ defined in Theorem 3 lies in
int(PS ). Then, by Lemma 9, the constant-distribution policy
b∗ = (b∗ , b∗ , . . . ) (where b∗ is given by Theorem 3), achieves

13

the leakage rate I(b∗ , ξ ∗ ). By Lemma 7, I(b∗ , ξ ∗ ) is same as
J ∗ defined in Theorem 3. Thus, J ∗ is achievable starting from
any initial state (θ1 , ξ1 ).

Now consider
I(Wt ; Yt |Y t−1 ) = H(Wt |Y t−1 ) − H(Wt |Y t )
= H(Wt |Y t−1 ) − H(Wt + Yt |Y t )
(b)

= H(Wt |Y t−1 ) − H(St+1 |Y t )

D. Dynamic programming converse

(c)

We provide two converses. One is based on the dynamic
program of Theorem 4, which is presented in this section;
the other is based purely on information theoretic arguments,
which is presented in the next section.
In the dynamic programming converse, we show that for J ∗
given in Theorem 3, v ∗ (ξ) = H(ξ), and any b ∈ B,
J ∗ + v ∗ (ξ) ≤ [B̃b v ∗ ](ξ),

∀ξ ∈ PW ,

(47)

Since H(ξ) is bounded, from [21, Lemma 5.2.5(b)], we get
that J ∗ is a lower bound of the optimal leakage rate.
To prove (47), pick any ξ ∈ PW and b ∈ B. Suppose W1 ∼
ξ, Y1 ∼ b(·|W1 ), S2 = Y1 + W1 , X2 is independent of W1
and X2 ∼ PX and W2 = S2 − X2 . Then,
X
[B̃b v ∗ ](ξ) = I(b; ξ) +
ξ(w1 )b(y1 |w1 )v ∗ (ϕ̂(ξ, y1 , b))

= H(Wt |Y t−1 ) − H(St+1 |Y t , Xt+1 )
= H(Wt |Y t−1 ) − H(St+1 − Xt+1 |Y t , Xt+1 )
(d)

= H(Wt |Y t−1 ) − H(Wt+1 |Y t , Xt+1 )

where (b) follows from (1); (c) follows because of assumption (A); and (d) also follows from (1).
Substituting (51) in (50) (but expanding the last term as
H(WT |Y T −1 ) − H(WT |Y T ), we get
I(S1 , X T ; Y T ) ≥
=

T
X

t=2

T
X

(54)

I(Wt ; Xt |Y t−1 ) − H(WT |Y T ).

S̃2 ∼ θ2
(49)

where (a) uses S2 = Y1 + W1 and W2 = S2 − X2; (b) uses
the fact that H(A
 1 |B) − H(A1 − A2 |B) ≥ minPA1 H(A1 ) −
H(A1 − A2 ) for any joint distribution on (A1 , A2 , B).
The equality in (49) occurs when b is an invariant policy
and θ2 is same as θ∗ defined in Theorem 3. For ξ that are not
equivalent to θ∗ via (38), the inequality in (49) is strict.
We have shown that Eq. (47) is true. Consequently, J ∗ is a
˜
lower bound on the optimal leakage rate J.

Now, we take the limit T → ∞ to obtain a lower bound to
the leakage rate:
1
L∞ (q) = lim sup I(S1 , X T ; Y T )
T →∞ T


T
X
1
t−1
T
≥ lim sup
H(W1 ) +
I(Wt ; Xt |Y
) − H(WT |Y )
T →∞ T
t=2
" T
#
1 X
(a)
t−1
= lim supT →∞
I(Wt ; Xt |Y
)
T t=2
(b)

≥ min I(S − X; X) = J ∗
PS ∈PS

where (a) is because the entropy of any discrete random
variable is bounded and (b) follows from the fact that each
term in the summation satisfies:
I(Wt ; Xt |Y t−1 ) ≥ min I(S − X; X),
PS ∈PS

E. Information theoretic converse
Consider the following inequalities: for any admissible
policy q ∈ QB , we have
I(S1 , X T ; Y T ) =
(a)

≥

t=1
T
X

(56)

which can be justified as follows. First note that for any policy
q we have that:
I(Wt ; Xt |Y t−1 ) = I(St − Xt ; Xt |Y t−1 )
depends on the joint distribution PSqt ,Xt ,Y t−1 (st , xt , y t−1 )
which factors as:

I(St , Xt ; Yt |Y t−1 )
I(Wt ; Yt |Y t−1 )

(55)

t=2

(a)

T
X

(53)


− H(Wt |Y t−1 , Xt ) + H(Wt |Y t−1 )

− H(WT |Y T )
= H(W1 ) +

= H(W2 |Y1 ) − H(W1 + Y1 |Y1 )

=J

(52)



H(Wt |Y t−1 ) − H(Wt+1 |Y t , Xt+1 )

= H(W1 ) +

(48)

[B̃b v ](ξ) − v (ξ) = H(W2 |Y1 ) − H(W1 |Y1 )

θ2 ∈PS
∗

T
−1
X

+H(WT |Y T −1 ) − H(WT |Y T )

∗

= H(S2 − X2 |Y1 ) − H(S2 |Y1 )
(b)


≥ min H(S̃2 − X2 ) − H(S̃2 ) ,

I(Wt ; Yt |Y t−1 )

t=1

where the second equality is due to the definition of conditional entropy. Consequently,
∗

T
X
t=1

(w1 ,y1 )∈W×Y

= I(W1 ; Y1 ) + H(W2 |Y1 )

(51)

(50)

t=1

where (a) follows from the fact that Wt = Xt − St is a deterministic function of (Xt , St ) and that the mutual information
is non-negative.

PSqt ,Xt ,Y t−1 (st , xt , y t−1 ) = PX (xt )PSqt ,Y t−1 (st , y t−1 ) (57)
as Xt is sampled i.i.d. from the distribution PX (·) and from
the state update equation (1), we have that St is a function of
(X t−1 , Y t−1 ), and thus independent of Xt . Now note that:
I(Wt ; Xt |Y t−1 )

14

=

X

2

;X)
> 0.
I(W ; X) is strictly convex on PS we require d I(W
dα2
Due to independence of X and S, I(W ; X) = H(W )−H(S).
Therefore,

I(St − Xt ; Xt |Y t−1 = y t−1 )p(y t−1 )

y t−1 ∈Y t−1

≥
≥

min

y t−1 ∈Y t−1

I(St − Xt ; Xt |Y t−1 = y t−1 )

min

min

y t−1 ∈Y t−1 pS

t−1 (·|y
t ,Xt |Y

≥

min

y t−1 ∈Y t−1 ,pS

t

|Y t−1 (·|y

t−1 )

t−1 )

I(St − Xt ; Xt |Y t−1 = y t−1 )

I(St − Xt ; Xt |Y t−1 = y t−1 )
(58)

where (58) follows from (57) so that Xt is independent of
(St , Y t−1 ) and distributed according to PX (·) Since (58) is
simply equivalent to minimizing over the distribution PS (·),
the relation in (56) holds. This completes the proof. This shows
that J ∗ is a lower bound to the minimum (infinite horizon)
leakage rate.
V. C ONCLUSIONS AND D ISCUSSION
In this paper, we study a smart metering system that uses
a rechargeable battery to partially obscure the user’s power
demand. Through a series of reductions, we show that the
problem of finding the best battery charging policy can be
recast as a Markov decision process. Consequently, the optimal
charging policies and the minimum information leakage rate
are given by the solution of an appropriate dynamic program.
For the case of i.i.d. demand, we provide an explicit
characterization of the optimal battery policy and the leakage
rate. In this special case it suffices to choose a memoryless
policy where the distribution of Yt depends only on Wt . Our
achievability results rely on restricting attention to a class of
invariant policies. Under an invariant policy, the consumption
{Yt }t≥1 is i.i.d. and the leakage rate is characterized by a
single-letter mutual information expression. We then further
restrict attention to what we call structured policies under
which the marginal distribution of {Yt }t≥1 is PX . Thus, under
the structured policies, an eavesdropper cannot statistically
distinguish between {Xt }t≥1 and {Yt }t≥1 . We provide two
converses; one is based on the dynamic programming argument while the other is based on a purely information theoretic
argument.
Extending of our MDP formulation to incorporate an
additive cost, such as the price of consumption, is rather
immediate. However, the approach presented in this work
for explicitly characterizing the optimal leakage rate in the
i.i.d. case may not immediately extend to such general cost
functions. In another direction one can allow for a certain
controlled wastage of energy drawn from the grid to increase
privacy. It would be interesting to see how the leakage rate
decreases with the wasted energy. The study of such problems,
as well as finer implementation details of the proposed system,
remains an interesting future direction.

d [−H(S) + H(W )]
dI(W ; X)
=
dα
dαX
X
δ(s̃) ln θα (s̃) −
PX (s − w)δ(s) ln PW (w)
=
s̃

w∈W,s∈S

X
d I(W ; X) X δ(s)2
=
−
2
dα
θα (s)
s
2

P

s̃∈S

w∈W

2
PX (s̃ − w)δ(s̃)
.
PW (w)

q
p
Let aw (s) = δ(s) PXθα(s−w)
and bw (s) = θα(s) PX (s − w).
(s)
Using the Cauchy-Schwarz inequality, we can show that
2
P
X
d2 I(W ; X) X δ(s)2
s̃∈S aw (s̃)bw (s̃)
=
−
dα2
θα (s)
PW (w)
s
w∈W
 P

P
2
2
X δ(s)2
X
s̃∈S aw (s̃)
ŝ∈S bw (ŝ)
>
−
θα (s)
PW (w)
s
w∈W
!
X X
X δ(s)2
−
aw (s̃)2 = 0.
=
θα (s)
s
w∈W

s̃∈S

The strict inequality is because a and b cannot be linearly
δ(s)
dependent. To see this, observe that a(s)
b(s) = θ(s)+αδ(s) cannot
be equal to a constant for all s ∈ S since δ must contain
negative as well as positive elements.

A PPENDIX B
P ROOF OF P ROPOSITION 1
The proof of Proposition 1 relies on the following intermediate results (which are proved later):
Lemma B.1. For any q ∈ QA ,
q

T

T

I (S1 , X ; Y ) ≥

T
X

I q (Xt , St ; Yt |Y t−1 )

t=1

with equality if and only if q ∈ QB .
Lemma B.2. For any qa ∈ QA , there exists a qb ∈ QB , such
that
T
X
t=1

I qa (Xt , St ; Yt |Y t−1 ) =

T
X

I qb (Xt , St ; Yt |Y t−1 ).

t=1

Combining Lemmas B.1 and B.2, we get that for any qa ∈
QA , there exists a qb ∈ QB such that

A PPENDIX A
P ROOF OF P ROPERTY 1

I qa (S1 , X T ; Y T ) ≥ I qb (S1 , X T ; Y T ).

PFor any θ ∈ int(PS ) and δ(s) : S → R such that
s∈S δ(s) = 0. Let θα (s) := θ(s) + αδ(s). Then for small
enough α, θα ∈ PS . Given such a θα , let PW,X (w, x) =
PW |X (w|x)PX (x) = θα (w + x)PX (x). Then to show that

Therefore there is no loss of optimality in restricting attention
to charging policies in QB . Furthermore, Lemma B.1 shows
that for any q ∈ QB , LT (q) takes the additive form as given
in the statement of the proposition.

15

Proof of Lemma B.1. For any q ∈ QA , we have
(a)

n
X

(b)

t=1
n
X

I q (S1 , X n ; Y n ) =
=

(c)

≥

t=1
n
X

A PPENDIX C
P ROOF OF CONCAVITY OF THE VALUE FUNCTION

I q (S1 , X t ; Yt |Y t−1 )
q

t

t

I (X , S ; Yt |Y
q

I (Xt , St ; Yt |Y

t−1

t−1

To prove the result, we show the following:
Lemma C.1. For any action a ∈ A, if V : PX,S → R is
concave, then Ba V is concave on PX,S .

)

The concavity of the value functions follows from backward
induction. VT +1 is a constant and, therefore, also concave.
Lemma C.1 implies that VT , VT −1 , . . . , V1 are concave.

)

t=1

where (a) uses the chain rule of mutual information and the
fact that (S t−2 , Y t−1 ) → Xt−1 → Xt ;5 (b) uses the fact that
the battery process S t is a deterministic function of S1 , X t−1 ,
and Y t−1 given by (1); and (c) uses the fact that removing
terms does not reduce the mutual information.
Proof of Lemma B.2. For any qa = (q1a , q2a , . . . , qTa ) ∈ QA ,
construct a qb = (q1b , q2b , . . . , qTb ) ∈ QB as follows: for any t
and realization (xt , st , y t ) of (X t , S t , Y t ) let

Proof of Lemma C.1. The first term I(a; π) of [Ba V ](π) is
a concave function of π. We show the same for the second
term.
Note that if a function V is concave, then it’s perspective g(u, t) := tV (u/t) is concave in the domain
{(u, t) : u/t ∈ Dom(V ), t > 0}. The second term in the definition of the Bellman operator (10)

X X
a(y|x, s)π(x, s) V (ϕ(π, y, a))
y∈Y

qtb (yt |xt , st , y t−1 ) = PqYa|Xt ,St ,Y t−1 (yt |xt , st , y t−1 ).
t

(59)

To prove the Lemma, we show that for any t,
PqXat ,St ,Y t = PqXbt ,St ,Y t .

(60)

By definition of qb given by (59), to prove (60), it is sufficient
to show that
PqXat ,St ,Y t−1 = PqXbt ,St ,Y t−1 .

(xt ,st )∈X ×S

=

X

Q(xt+1 |xt )1st+1 {st − xt + yt }qa (yt |xt , st , y t−1 )

(xt ,st )∈X ×S
qa

× P (xt , st , y t−1 )
(a) X
=
Q(xt+1 |xt )1st+1 {st − xt + yt }qb (yt |xt , st , y t−1 )

(xt ,st )∈X ×S
qb

× P (xt , st , y t−1 )

qb

has this form because the
Pnumerator of ϕ(π, y, a) is linear in π
and the denominator is x,s a(y|x, s)π(x, s) (and corresponds
to t in the definition of perspective). Thus, for each y, the
summand is concave in π, and the sum of concave functions
is concave. Hence, the second term of the Bellman operator
is concave in π. Thus we conclude that concavity is preserved
under Ba .

(61)

We do so using induction.
For t = 1, PqXa1 ,S1 (x, s) = PX1 (x)PS1 (s) = PqXb1 ,S1 (x, s).
This forms the basis of induction. Now assume that (61) hold
for t.
In the rest of the proof, for ease of notation, we denote
PqXat+1 ,St+1 ,Y t (xt+1 , st+1 , y t ) simply by Pqa (xt+1 , st+1 , y t ).
For t + 1, we have
X
Pqa (xt+1 , st+1 , y t ) =
Pqa (xt+1 , xt , st+1 , st , y t )

A PPENDIX D
P ROOF OF L EMMA 9
The proof of the convergence of {ξt }t≥1 relies on a result
on the convergence of partially observed Markov chains due
to Kaijser [33] that we restate below.
Definition 4. A square matrix D is called subrectangular if for
every pair of indices (i1 , j1 ) and (i2 , j2 ) such that Di1 ,j1 6= 0
and Di2 ,j2 6= 0, we have that Di2 ,j1 6= 0 and Di1 ,j2 6= 0.
Theorem 5 (Kaijser [33]). Let {Ut }t≥1 , Ut ∈ U, be a finite
state Markov chain with transition matrix P u . The initial state
U1 is distributed according to probability mass function PU1 .
Given a finite set Z and an observation function g : U → Z,
define the following:
• The process {Zt }t≥1 , Zt ∈ Z, given by
Zt = g(Ut ).
•

t

= P (xt+1 , st+1 , y )
where (a) uses (59) and the induction hypothesis. Thus, (61)
holds for t + 1 and, by the principle of induction, holds for
all t. Hence (60) holds and, therefore, I qa (Xt , St ; Yt |Y t−1 ) =
I qb (Xt , St ; Yt |Y t−1 ). The statement in the Lemma follows by
adding over t.
5 The notation A → B → C is used to indicate that A is conditionally
independent of C given B.

(x,s)∈X ×S

The process {ψt }t≥1 , ψt ∈ PU , given by
ψt (u) = P(Ut = u | Z t ).

•

A square matrix M (z), z ∈ Z, given by
(
Piju if g(j) = z
[M (z)]i,j =
0
otherwise

i, j ∈ U.

Qm
If there exists a finite sequence z1m such that t=1 M (zt )
is subrectangular, then {ψt }t≥1 converges in distribution to a
limit that is independent of the initial distribution PU1 .

16

We will use the above theorem to prove that under policy
b , {ξt }t≥1 converges to a limit. For that matter, let U =
S × Y, Z = Y, Ut = (St , Yt−1 ) and g(St , Yt−1 ) = Yt−1 .
First, we show that {Ut }t≥1 is a Markov chain. In particular,
for any realization (st+1 , y t ) of (S t+1 , Y t ), we have that

Since the sequnce of demands xm has a positive probability,

◦

◦

Pb (Ut+1 = (st+1 , yt ) | U t = (st , y t−1 ))
X
=
P (Ut+1 = (st+1 , yt ), Xt = x̃t | U t = (st , y t−1 ))
=

Y ms −1 = (111 . . . 1)) > 0.
Therefore,
P(Sms = ms | U1 = (s, y), Y ms −1 = (111 . . . 1)) > 0
which completes the proof.

x̃t ∈X

X

P(Sms = ms , X ms = xms | U1 = (s, y),

∗

1st+1 {yt + st − x̃t }b (yt |st − x̃t )PX (x̃t )

x̃t ∈X
b◦

= P (Ut+1 = (st+1 , yt ) | Ut = (st , yt−1 )).
Next, let m = 2ms and consider
z m = |111{z
· · · 1} 000
· · · 0} .
| {z
ms times

ms times

We will show that this z m satisfies the subrectangularity
condition of Theorem 5. The basic idea is the following.
Consider any initial state u1 = (s, y) and any final state
um = (s0 , 0). We will show that
P(Sms = ms | U1 = (s, y), Z ms = (111 . . . 1)) > 0,
(62)
and
ms
P(S2ms = s0 | Ums = (sm , 1), Zm
= (000 . . . 0)) > 0.
s +1
(63)

Eqs. (62) and (63) show that given the observation sequence
z m , for any initial state (s, y) there is a positive probability of observing any final state (s0 , 0).6 Hence, the matrix
Q
m
t=1 M (z) is subrectangular. Consequently, by Theorem 5,
the process {ψt }t≥1 converges in distribution to a limit that
is independent of the initial distribution
PU1 .
P
Now observe that θt (s) =
ψ
y∈Y t (s, y) and (θt , ξt )
are related according to Lemma 3. Since {ψt }t≥1 converges
weakly independent of the initial condition, so do {θt }t≥1 and
{ξt }t≥1 .
Let θ̄ and ξ¯ denote the limit of {θt }t≥1 and {ξt }t≥1 .
Suppose the initial condition is (θ◦ , ξ ◦ ). Since b◦ is an
invariant policy, (θt , ξt ) = (θ◦ , ξ ◦ ) for all t. Therefore, the
¯ = (θ◦ , ξ ◦ ).
limits (θ̄, ξ)
Proof of Eq. (62). Given the initial state (s, y), define s̄ =
ms − s, and consider the sequence
· · · 1} .
xms = |000{z
· · · 0} |111{z
s̄ times

s times

Under this sequence of demands, consider the sequence of
consumption y ms −1 = (11 . . . 1), which is feasible because
the state of the battery increases by 1 for the first s̄ steps (at
which time it reaches ms ) and then remains constant for the
remaining s steps. Therefore,
P(Sms = ms | U1 = (s, y),
Y ms −1 = (111 . . . 1), X ms = xms ) > 0.
6 Note that given the observation sequence z m , the final state must be of
the form (s0 , 0).

Proof of Eq. (63). The proof is similar to the Proof of (62).
Given the final state (s0 , 0), define s̄0 = ms − s0 and consider
the sequence
s
x2m
111{z
· · · 1} 000
· · · 0} .
ms +1 = |
| {z

s̄0 times

s0 times

Under this sequnce of demains and the sequence of consump2ms −1
= (00 . . . 0), the state of the battery
tion given by ym
s
decreases by 1 for the first s̄0 steps (at which time it reaches
s0 ) and then remains constant for the remaining s0 steps. Since
s
x2m
ms +1 has positive probability, we can complete the proof by
following an argument similar to that in the proof of (62).
R EFERENCES
[1] A. Ipakchi and F. Albuyeh, “Grid of the future,” IEEE Power Energy
Mag., vol. 7, no. 2, pp. 52–62, 2009.
[2] A. Prudenzi, “A neuron nets based procedure for identifying domestic
appliances pattern-of-use from energy recordings at meter panel,” in
Proc. Power Engineering Society Winter Meeting, vol. 2. IEEE, 2002,
pp. 941–946.
[3] G. W. Hart, “Nonintrusive appliance load monitoring,” Proc. IEEE,
vol. 80, no. 12, pp. 1870–1891, 1992.
[4] H. Y. Lam, G. Fung, and W. Lee, “A novel method to construct taxonomy
electrical appliances based on load signatures,” IEEE Trans. Consum.
Electron., vol. 53, no. 2, 2007.
[5] C. Efthymiou and G. Kalogridis, “Smart grid privacy via anonymization
of smart metering data,” in Proc. Smart Grid Communications. IEEE,
2010, pp. 238–243.
[6] G. Kalogridis, C. Efthymiou, S. Z. Denic, T. A. Lewis, and R. Cepeda,
“Privacy for smart meters: Towards undetectable appliance load signatures,” in Proc. Smart Grid Communications. IEEE, 2010, pp. 232–237.
[7] I. Csiszar and J. Körner, Information theory: coding theorems for
discrete memoryless systems. Cambridge University Press, 2011.
[8] D. Varodayan and A. Khisti, “Smart meter privacy using a rechargeable
battery: Minimizing the rate of information leakage,” in Proc. Int. Conf.
on Acoustics, Speech and Signal Processing. IEEE, 2011, pp. 1932–
1935.
[9] O. Tan, D. Gunduz, and H. V. Poor, “Increasing smart meter privacy
through energy harvesting and storage devices,” IEEE J. Sel. Areas
Commun., vol. 31, no. 7, pp. 1331–1341, 2013.
[10] G. Giaconi, D. Gündüz, and H. V. Poor, “Smart meter privacy with an
energy harvesting device and instantaneous power constraints,” in IEEE
International Conference on Communications (ICC). IEEE, 2015, pp.
7216–7221.
[11] S. Han, U. Topcu, and G. J. Pappas, “Event-based information-theoretic
privacy: A case study of smart meters,” in Proc. American Control
Conference. IEEE, 2016, pp. 2074–2079.
[12] L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of
linear codes for minimizing symbol error rate,” IEEE Trans. Inf. Theory,
vol. 20, no. 2, pp. 284–287, 1974.
[13] L. Sankar, S. R. Rajagopalan, and H. V. Poor, “Utility-privacy tradeoffs
in databases: An information-theoretic approach,” IEEE Trans. Inf.
Theory, vol. 8, no. 6, pp. 838–852, 2013.
[14] L. Sankar, S. R. Rajagopalan, and S. Mohajer, “Smart meter privacy:
A theoretical framework,” IEEE Trans. Smart Grid, vol. 4, no. 2, pp.
837–846, 2013.
[15] O. Tan, D. Gunduz, and H. V. Poor, “Increasing smart meter privacy
through energy harvesting and storage devices,” IEEE J. Sel. Areas
Commun., vol. 31, no. 7, pp. 1331–1341, 2013.

17

[16] S. Tatikonda and S. Mitter, “The capacity of channels with feedback,”
IEEE Trans. Inf. Theory, vol. 55, no. 1, pp. 323–349, 2009.
[17] A. J. Goldsmith and P. P. Varaiya, “Capacity, mutual information,
and coding for finite-state Markov channels,” IEEE Trans. Inf. Theory,
vol. 42, no. 3, pp. 868–886, 1996.
[18] H. Permuter, P. Cuff, B. Van Roy, and T. Weissman, “Capacity of the
trapdoor channel with feedback,” IEEE Trans. Inf. Theory, vol. 54, no. 7,
pp. 3150–3165, 2008.
[19] J. Yao and P. Venkitasubramaniam, “The privacy analysis of battery
control mechanisms in demand response: Revealing state approach and
rate distortion bounds,” IEEE Trans. Smart Grid, vol. 6, no. 5, pp. 2417–
2425, 2015.
[20] S. Li, A. Khisti, and A. Mahajan, “Structure of optimal privacypreserving policies in smart-metered systems with a rechargeable battery,” in Proc. Int. Workshop on Signal Processing Advances in Wireless
Communications. IEEE, 2015, pp. 375–379.
[21] O. Hernández-Lerma and J. Lasserre, Discrete-Time Markov Control
Processes. Springer-Verlag, 1996.
[22] O. Hernández-Lerma, Adaptive Markov Control Processes. SpringerVerlag, 1989.
[23] ——, Further Topics on Discrete-Time Markov Control Processes.
Springer-Verlag, 1991.
[24] D. P. Bertsekas, Dynamic programming and optimal control. Athena
scientific Belmont, MA, 1995, vol. 1, no. 2.
[25] R. Blahut, “Computation of channel capacity and rate-distortion functions,” IEEE Trans. Inf. Theory, vol. 18, no. 4, pp. 460–473, 1972.
[26] S. Arimoto, “An algorithm for computing the capacity of arbitrary
discrete memoryless channels,” IEEE Trans. Inf. Theory, vol. 18, no. 1,
pp. 14–20, 1972.
[27] L. Wang and M. Madiman, “Beyond the entropy power inequality, via
rearrangements,” IEEE Trans. Inf. Theory, vol. 60, no. 9, pp. 5116–5137,
2014.
[28] S. Li, “Information theoretic privacy in smart metering systems using
rechargeable batteries,” Master’s thesis, University of Toronto (Canada),
2016.
[29] A. Dembo, T. M. Cover, and J. A. Thomas, “Information theoretic
inequalities,” IEEE Trans. Inf. Theory, vol. 37, no. 6, pp. 1501–1518,
1991.
[30] T. M. Cover and J. A. Thomas, Elements of information theory. John
Wiley & Sons, 2012.
[31] W. B. Powell, Approximate Dynamic Programming: Solving the curses
of dimensionality. John Wiley & Sons, 2007, vol. 703.
[32] G. Shani, J. Pineau, and R. Kaplow, “A survey of point-based pomdp
solvers,” Autonomous Agents and Multi-Agent Systems, pp. 1–51, 2013.
[33] T. Kaijser, “A limit theorem for partially observed Markov chains,” The
Annals of Probability, pp. 677–696, 1975.

