Skip to main content

Full text of "Discrete versions of the transport equation and the Shepp--Olkin conjecture"

See other formats


Discrete versions of the transport equation and the 

Shepp-Olkin conjecture 

Erwan Hillion Oliver Johnson* 

March 15, 2013 

Abstract 

We introduce a framework to consider transport problems for integer-valued random 
variables. We introduce weighting coefficients which allow us to characterise trans- 
port problems in a gradient flow setting, and form the basis of our introduction of a 
discrete version of the Benamou-Brenier formula. Further, we use these coefficients 
to state a new form of weighted log-concavity. These results are applied to prove the 
monotone case of the Shepp-Olkin entropy concavity conjecture. 

MSC2000: primary; 60E15, secondary; 94A17, 60D99 

Keywords: entropy, transportation of measures, Bernoulli sums, concavity 

1 Introduction 

In recent years, there has been intensive study of relationships between entropy and a 
range of probabilistic inequalities. Since the work of Monge in the eighteenth century, it 
has been understood how one probability measure on K can be transformed into another 
in a smooth fashion which minimises the cost in an appropriate sense. As described for 
example in [3EJ EH] , the use of the quadratic cost function induces the quadratic Wasserstein 
distance W^- Using relationships such as the Benamou-Brenier formula [HI [7], this distance 
can be understood in terms of velocity fields which arise in gradient models of the kind 
discussed in [21 EJ [21]. In such models, the concavity of entropy along the geodesic plays a 
central role, and led to proofs of inequalities such as HWI, log-Sobolev and transportation, 
as described for example in [9]. A key role is played by log-concavity of the underlying 
measures, and the Ricci curvature of the underlying metric space. For example Sturm, 
Lott and Villani [251 ESI [36] showed that concavity of the entropy functional along the 
geodesies is equivalent to Ricci curvature bounds on Riemannian manifolds. 



*The collaboration of Oliver Johnson and Erwan Hillion is supported by an EPSRC grant, Information 
Geometry of Graphs, reference EP/ 1009450/1. 



1 



However, this work has almost exclusively focused on continuous random variables, 
taking values in M d , or more generally on Riemannian manifolds satisfying a curvature 
condition. In this paper, we propose a framework for considering similar problems for 
integer-valued random variables. We show how many natural models of transportation of 
discrete random variables can be considered in the context of gradient models, and propose 
a version of the Benamou-Brenier formula which applies in this case. As an example of 
the insights gained by this approach, we give a proof of a significant new case of the 
Shepp-Olkin concavity conjecture [33], which has remained unresolved for over 30 years. 

Shepp and Olkin considered sums of n independent Bernoulli variables (referred to 
throughout this article as Bernoulli sums), with parameters p±, . . .p n respectively, where 
Pi G [0, 1], and n remains fixed. This sum has a a probability distribution (fk)k=o,i,~,ni an d 
Shepp and Olkin conjectured [33] that its entropy is a concave function of its parameters. 

Conjecture 1.1 ([33]). Consider the entropy of (/fc)fc=o,i,...,n; defined by 

n 

H(p u ...p n ) := -^/fclog(/ fc ), 

fc=0 

where by convention 01og(0) = 0. If pi, . . .p n : [0, 1] — > [0, 1] are affine functions, then the 
function 

H : [0,1] ->]R , t^ H( Pl (t),...,p n (t)) 

is concave in t. 

We emphasise that Conjecture [1J] refers to concavity of entropy in the parameter space. 
This should be contrasted with concavity in the space of mass functions themselves. For 
example, the result that the entropy of mixtures of mass functions fk(ot) := (1 — a)f^ + 
afl is convex in a is standard (see for example [HI Theorem 2.7.3]). Indeed duality 
between this parameter representation and the distribution space is exploited in the field 
of Information Geometry (see for example [I]), where the concavity of entropy also plays 
a central role. 

Although the Shepp-Olkin Conjecture 11.11 remains open, we briefly describe the main 
cases which had previously been resolved. First, in Shepp and Olkin's original paper [33] . 
they showed that the entropy is a Schur-concave function, stated that the conjecture holds 
in the cases n = 2 and n = 3, and proved it for interpolation between two binomials, when 
Pi(t) does not depend on i. 

Second, in Theorem 2 of Yu and Johnson [12] , the concavity of the entropy of H(T t X + 
Ti-fY) is proved, for X and Y satisfying the ultra log-concavity property (see Definition 
13. Ill below), where T t represents Renyi's thinning operation [31], see Equation fj40|) below. 
As remarked in [42, Corollary 1], this resolves the special case of Conjecture 11.11 where 
each parameter is either Pi(t) = pi(0)(l — t) or Pi{t) = Pi(l)t (that is, Pi(Q)pi(l) = for 
each i). In this paper we restrict our attention to cases where measures satisfy a stochastic 
ordering property, so as in Proposition 1 of [12] we might wish to consider H(T t X). 

Third, Theorem 1.1 of Hillion [TB] resolves the case where for each i, either Pi(t) = Pi(0) 
for all t or Pi(t) = t (the translation case of Example 13 . 1 01 below) . 



2 



In this article, given a family of affine functions Pi(t), . . .p n (t), we will consider the 
associated Bernoulli sum {fk{t))k=o,i,...,n as a function of the spatial variable k and the 
time variable t. We will often omit the explicit dependence of fk on t. Throughout this 
article we will restrict our attention to the special case that p\ > for every i G {1, . . . n}, 
so the random variables fk(t) satisfy a stochastic ordering property. We will write the 
left derivative V\fk — fk — fk~i, an d write V2 = (V1) 2 for the map taking V2//C = 

fk — 2/fc-l + fk-2- 

The paper is organised as follows. In Section [2] we review properties of continuous 
gradient flow models, and develop a framework to prove concavity of entropy. We introduce 
and discuss the Benamou-Brenier formula, Equation ( jTUl) . 

In Section [3] we introduce a formalism to describe interpolation of discrete probability 
mass functions fk-, motivated by properties of the binomial mass functions. In Definition 
13.21 we propose a discrete analogue of the Benamou-Brenier formula. A key role is played 
by our introduction of a family of functions ctk{t) which are used to generate mixtures of 
fk and fk+i- We write A for the set of a(t) = (a (t), . . . ,a n (t)), where a (£) = 
and a n (t) = 1, and < ak(t) < 1 for all k and t. 

Our formula of Benamou-Brenier type motivates the following definition: 

Definition 1.2. We say that a sequence of probability mass functions fk{t) is a constant 
speed path, if for some v and for some sequence of probability mass functions g^(t), it 
satisfies a modified transport equation 

?A(t) = -vV 1 (g { k a \t)) for k = 0, 1, ... , n, (1) 

where for some a(t) G A, 

g { k a) (t) = a k+ i(t)f k+ i(t) + (1 - a k (t))f k (t) for k = 0, 1, . . . , n - 1. (2) 

If fk(t) satisfies a modified transport equation, we write h for the function (not necessarily 
a probability mass function) satisfying a second-order modified transport equation 



d 2 f; 



Of 



k (t)=v 2 V 2 (h k ), for k = 0,1,..., n. (3) 



In Section 13731 we discuss this property - in Lemma [331 we show that any such represen- 
tation is unique, and we give some examples which lie within this framework. In Section HI 
by examining the properties of the optimal coefficients cx G A, we are able to give sufficient 
conditions for the concavity of entropy along the interpolation. To be specific, we introduce 
the following three conditions: 

Condition 1 (fc-MON). Given t, we say that the ctk{t) are k-monotone at t if 

Oikif) < a k+i(t) f or all k — 0, . . . ,n — 1. (4) 



3 



Condition 2 (t-MON). Given t, we say that the a k (t) are t-monotone at t if 



da k 



(t) > for allk = 0,...,n. 



(5) 



dt 



Condition 3 (GLC). We say that probability mass function f k supported on {0, 1, ... , n} 
is at- generalized log-concave at t, denoted by GLC(o:(t)), if 



GLC{cc) k {t) := a k+1 (t)(l - a k+l {t))f 2 k+l {t) - a k+2 (t)(l - a k (t))f k (t)f k+2 (t) > 0, (6) 



for k — 0, . . . , n — 2. 

In Section H] we prove the following theorem: 

Theorem 1.3. Consider a constant speed interpolation f k (t) of probability mass functions 
and associated optimal oc(t). If Conditions^ [H and [3] hold, then the entropy is concave. 
In fact, given t, if the a k (t) are k-monotone and t-monotone at t and f k (t) is GLC(a(t)) 
then the entropy H(f(t)) is concave at t. 

Theorem 11.31 gives a new perspective on Shepp and Olkin's proof [H3J that the entropy 
of Bin(n, t) random variables is convex in t: 

Example 1.4. In this case, Example \3.1\ shows that the optimal a k (t) = k/n, so that the 
k-monotone and t-monotone conditions, Conditions^ and\^ are clear. Further, this choice 
of ct k {t) means that the GLC Condition^ reduces to the ultra log-concavity of order n of 
Pemantle ISUtf and Liggett \2J$ (see Definition \3.11\) . which clearly holds with equality in 



In fact, similar arguments work in new cases as well. For example, in the 'symmetric 
case' where p\ does not depend on i, we find that a k (t) = k/n (see Remark \5.3\ below), and 
so a similar argument applies. 

Having set up this formalism, we then use it to consider the Shepp-Olkin theorem, in 
the 'monotone' setting p[ > for all i mentioned previously. In Section [51 we show that in 
the monotone case, the Shepp-Olkin interpolation can be seen as a constant speed path in 
the sense of Definition II. 21 In Proposition 15. 21 we show that the k- monotone Condition [1] is 
automatically satisfied in this case. Similarly Proposition 15.41 shows that GLC, Condition 
[3] also holds for all Shepp-Olkin interpolations in this context. 

Unfortunately t-monotonicity, Condition [21 does not hold for all (monotone) Shepp- 
Olkin interpolations. However, Proposition 14.21 shows that we can replace Condition [2] by 
Condition HI which is less restrictive, although less transparent in nature. 

We prove the monotone Shepp-Olkin conjecture by showing that Condition [4] is satisfied 
in this case. The proof uses properties of Bernoulli sum mass functions, including a 'cubic' 
inequality Theorem IA.2I In Section [HI we therefore prove the main result of this paper: 

Theorem 1.5 (Monotone Shepp-Olkin). Consider the entropy of (f k ) k =o,i,....n, defined by 



this case. 



■n 




k=0 



4 



If Pi, ■ ■ -p n '■ [0, 1] — > [0, 1] are affine functions with p\ > for all i, then the function 

H : [0,1] ^-E , t^H( Pl (t),...p n (t)) 

is concave in t. 

2 Geodesies for continuous random variables 
2.1 General framework for concavity of entropy 

Section [2] is devoted to the study of the entropy for several families of random variables on 
IR. For each of the standard examples we study, the concavity of entropy is a consequence 
of the following theorem: 

Theorem 2.1. Let {ft{x))te[o,i] be a smooth family of probabilty positive densities onM.. We 
consider the families of functions {gt{x))te{o,i} an d (h t (x)) te [o : i] such that for each t G [0, 1], 
g t and h t vanish at x = — oo, +oo and satisfy the differential equations (stated in a form 
which motivates Equations (T7|) and §B\)): 

dft(x) = dg t (x) d 2 f t (x) = d 2 h t (x) 
dt dx ' dt 2 dx 2 

Then the entropy H(t) of f t , defined by 

Hit) :=- [ f t (x) log( f t {x))dx 

JR 

satisfies 
Proof. 

H"(t) = - JJ^l log{ f,(x))dx 

= - SJ^ logiUx))ix 

After several integrations by parts, we find 

H " m = -JS h < (x) -jS)^ {,ogiMxmdx 

The second integral being non-negative, the theorem is proven. □ 



i 



f t (x) V dx 



dftjx) 
dt 

dg t (x) 



dx 



dx. 



5 



In some sense, an extreme example for which we can apply Theorem 12. II is the following: 
Example 2.2. Consider the translation of some probability density f , where we have 

ft(x) := f (x - vt) 

for some constant velocity v > 0. It is then easy to see that gt{x) = vft(x) and h t (x) = 
v 2 ft{x). Theorem \2. 1\ then confirms the fact that shift invariance of the entropy on trans- 
lation makes the entropy H(t) of ft constant, and hence a concave function oft. 

2.2 Benamou— Brenier formula 

The study of geodesies interpolating between continuous probability densities exploits prop- 
erties of the quadratic Wasserstein distance W%. In particular, recall from [HI [7] that W2 
has a variational characterisation involving velocity fields, given by the Benamou-Brenier 
formula (ITU]) below. 

Consider fixed smooth distribution functions F and -F\. Write V(M) for the set of 
probability densities ft{x), with corresponding distribution functions F t (x) = J_ ft(y)dy 
satisfying constraints F t (x)\t=o = Fq(x) and F t (x)\ t =i = Fi(x). Then given any sequence 
ft G we can define the velocity field v t by 

§- t ft(x) + ^ (vt(x)ft(x)) = 0, (8) 

or equivalently by 

^Ft(x) + (vt(x)ft(x)) = 0, (9) 
Benamou and Brenier prove the following theorem: 

Theorem 2.3 ([61 [7]). Using the notation above, the quadratic Wasserstein distance is 
given by 

Wi{F Q ,F 1 ) = inf / ( f f t (y)vt(y) 2 dy) dt. (10) 
fteVw Jo \J J 

In analogy with Example 12. 2\ we can show that the entropy is concave along any 
Benamou-Brenier geodesic (the path achieving the infimum in Equation (TTUT) ) . A change 
of variables x = F t (y) in Equation (fIU|) makes the inner integrand 

ft(y)v t (y) 2 dy] = ( ! v t {F t -\x)fdx 



Combining Equations (2.1) and (2.4) of [7], we see that the geodesic has a velocity field 
Vt(F t _1 (x)) which is constant in time, in the sense that f 4 (i^ _1 (x)) = (<& r (x) — x) for all t 
for a certain function <3>. Using the fact that the total derivative of f 4 (F 4 _1 (x)) with respect 
to t is leads to the formula: 

Me> = -^(,). (id 



6 



Taking a further time derivative of jS]), and using ( ITTj) . we deduce a second-order PDE for 
ft(x): 



d ( dvAx) , . . . . . d , ,,,,,,, 
v t [x) ft {x) + v t {x) — {v t (x) f t {x)) 



dx V cte <9x 
«9 2 



(vt(x) 2 f t (x)) . (12) 



<9x 

(assuming the t and x derivatives can be exchanged). 

In the notation of Theorem 12.11 we can rewrite equations (jHJ) and (TI2"]) in the form 
(?t(x) = v t (x)f t (x) and ^t(x) = v t (x) 2 f t (x) . This makes a clear analogy with the translation 
case, Example 12.21 By a straightforward application of Theorem I2.1[ we deduce that the 
entropy H(t) of f t is a concave function of t, which is equivalent, up to the regularity of 
/, to say that Ric(R) > in the sense of Sturm-Lott-Villani [23 ESI ES]- 

In Section [3] we describe how a similar formula can be established in the discrete case. 



2.3 Diffusions on R 

Let (/t)te[o,i] be a smooth curve in V(M) satisfying the diffusion equation 

dftjx) _ d 2 f t (x) 
dt dx 2 



(13) 



In this case, the families of functions (gt(x))te[o,i\ an d (^t( a; ))tG[o,i] defined by Equation 
(J7J) can be simply written 

gt{x) = JIM Hx) »■/.(*) 



dx ' dx 2 
and Theorem 12.11 implies: 

Theorem 2.4. The entropy Hit) of f t satisfies 

H"(t) = - J f t (x) ^ lDg(/ t (x))^ rfx < 0. (14) 

Another proof of Theorem 12.41 was given by Villani [37] who used it to prove, by a 
simple application of the Cauchy-Schwarz inequality, that H"(t) < —H'(t) 2 . From this he 
deduced Costa's restricted form of Shannon's entropy power inequality (see [10]), which 
implies the Gaussian logarithmic Sobolev inequality of Gross |15j . 



Example 2.5. In the information-theoretic community, one particular case of interest 
related to this kind of diffusion is interpolation between continuous X with variance a 2 and 



7 



Z , a Gaussian with the same variance and density <p 2 . We can write ft for the density of 
y/1 — tX + ytZ, and observe that 

>^M f <Mm))- (15) 

In the notation above, this means that g t (x) = — 2 ci-t) (ft( x )(Pt(x) + x/cr 2 )), where pt(x) 
is the score function with respect to location parameter. 

This particular interpolation is the basis of the de Bruijn identity, first stated by Stam 
[341, and given in the following reparameterised form by Barron /2l Lemma 1]. The de 
Bruijn identity shows that the derivative with respect to t of relative entropy of ft is a 
multiple of the standardized Fisher information: 

m°(fM) = ^ {'I'M (*<■*)+$)**<) 

This result was used in Stam's proof of Gross's log-Sobolev inequality JW$, and forms 
the basis of Barron's information-theoretic proof of the Central Limit Theorem f5\[. 

Another example for which similar calculations lead to interesting results about the 
concavity of entropy is the case of Schrodinger bridges, which have been recently studied 
by Leonard in [23] in the setting of Markov chains as a generalization of Wasserstein 
geodesies. 

Example 2.6. In the case of a simple diffusion on M, we consider a smooth family of 
positive densities (ft{x))te[o,i] an d we suppose that 



t ( r \ — v ( r \ v ( r \ 9 < x ) _ d^fo) fotjx) _ d 2 v t (x) 
ft(x) - u t {x)v t {x) , - , - (16) 



It is then easy to compute that in this case, using the notation of Theorem \2.1[ 

9tW = - (it) 

OX ox 



d 2 v t (x) du t (x)dv t (x) d 2 u t (x 
dx 2 dx dx dx 

Using these expressions we can show that 

ft(x)h t (x) - g t (x) 2 = /t(x)^tog(/ t (x)), (19) 

from which direct substitution in Theorem \2. 1\ shows that the entropy H(t) of ft is a concave 
function oft. 



8 



2.4 A Gaussian approximation to the Shepp— Olkin conjecture 

Sums of independent Bernoulli variables are often approximated by Gaussian distributions 
of same mean value and variance. We will thus consider in this section the family of 
probability densities 

f(x; Pl ,...p n ):= , 1 expf — ^f Pi ^ \ (20) 



where pi,...p n are n parameters in [0, 1]. This continuous approximation motivates the 
Shepp-Olkin conjecture, due to the following result: 

Theorem 2.7. Let pi, . . .p n : [0, 1] — > [0, 1] be affine functions and 

ft(x) := /(x;pi(t),. . .p»(t)). 

TTien i/ie entropy H(t) of ft is a concave function oft. 

Proof. Let //(£) := E" =1 Pi(£) and V(t) := Y^i=i Pi(^)(^ ~ Pi(t)) be the mean and variance 
functions. Since //'(t) = 0, we can use differential properties satisfied by Gaussian kernels 
to compute 

V'(t) df t (x) 
9t(x) = — + ti(t)f t {x) 

h t (x) = v(t)f t (x) + M)f t ( X ) - mv(t)^ + v 'f 2 d2f d ^ ] 

In this case, the key term in Theorem 12.11 simplifies to give 

h( \ 9t ^ V "^t( uWf/ \( d * 1 (ft W 

^ X) ~T(x) = —2~f*( x ) + —^f*( x ) [dx^ l0 ^ ft ^ 

Substituting in Theorem 12. II we obtain that H"(t) can be expressed in terms of two perfect 
squares, since H"(t) is less than or equal to 

V"(t) f ( d 2 \ V'(t) 2 f ( d 2 \ 2 

' ' f t (x) — hg(f t (x)) dx - -LL / f t (x) — bg(/ t (x)) dx 



2 Jr \dx 2 J 4 J R \dx 2 / 

V"(t)[.,.(d, ....A 2 , V'(t) 2 f . , . { & 



f t (x) ( — log(/ t (a;)) 1 dx- J f t (x) ( — log(/ f (a;)) 1 rfx. (21) 

Since V"(i) < 0, the result follows. Indeed, it is clear that for any Gaussian model of this 
kind where V"(t) < 0, a similar argument will apply. 

In the case where v = //(£) = YH=iV'iif) > 0, we can restate this argument in a way 
that motivates the proof of Theorem 11.31 If we write 

9 



in particular we have 

We can rewrite Equation (12"T1) in the form 

H"(t) < -v 2 (~$- Jjt(x) ^log(/ t (x))y + a(t) 2 £/,(x)^log(/ t (x))^) dx 



which is strongly reminiscent of the form obtained in the discrete case in Equation (1661) 
below. □ 



3 Discrete gradient field models 

3.1 Motivating example and discrete Benamou— Brenier formula 

We now show how natural choices of paths connecting probability mass functions on the 
integers can be viewed in the gradient field framework described previously. We give a new 
perspective on the time derivative using a series of functions a k (t), where k — 0, . . . , n and 
< t < 1. Recall that we use the left derivative map Vi defined by V\f k = fk — fk-i for 
any function /, and write V2 = ( Vi) 2 for the map taking V*2,/fc = fk — %fk-i + fk-2- Write 
V*, defined by V\f k = fk — fk+i, for its adjoint (with respect to counting measure). 

We first give a motivating example, which is a special case of the Shepp-Olkin inter- 
polation. We write Bm k (n,p) := (™)p fc (l — p) n ~ k for the probability mass function of a 
binomial with parameters n and p. 

Example 3.1. Consider interpolating between two binomial random variables. For fixed 
n and < p < q < 1, define p(t) = p(l — t) + qt, and write fk{t) = Binfc(n,p(t)) for the 
probability mass functions which interpolate in the natural way in the parameter space. A 
simple calculation (see for example p?7| / and I3$j ) shows that for any k = 0, 1, . . . , n: 

dfk 

_±(t) = n(q-p) (Bin fe _i(n- l,p(t)) - Bin fe (n - l,p(t))) 

= -V 1 (n(q-p)Bm k (n-l,p(t))). (24) 

Although Equation (24\ ) expresses the time derivative of f(t) as the spatial gradient of 
another function, we prefer to reformulate it using an insight of Yu 140 J, who defined an 
operation which he referred to as hypergeometric thinning. Lemma 2 of JJO^j observes that 
for any n, p: 

(k + 1) / k\ 

Bin k (n -l,p) = Bm k+l (n,p) +1 Bin fc (n,p). (25) 

n \ n I 



This suggests that we rewrite Equation (2~4\ ) in the form, modelled on 

m -(t) + Vi ((n(g - P)) g { k a \t)) for k = 0,1,..., n, (26) 



- dfk 



for g { k a \t) = a k+1 (t)f k+1 (t) + (l-a k (t))f k (t) for k = 0,1, ... ,n - 1, (27) 



10 



with ack(t) = k/n for all k and t. 

The form of Equations (I26I) and ff271) suggests a version of the Benamou-Brenier formula 
P, [7] for discrete random variables. 

Definition 3.2. Write A for the collection of functions cx.(t) = («o(t), ct\{t), • • • , at n (t)), 
where ao(t) = and a n (t) = 1, and < a k (t) < 1 /or a// and £. Given a k (t) e ^4, /or a 
sequence of mass functions f k (t), define probability mass function g£ (t) and velocity field 
V a ,k(t) b u 

g k a \t) = a k+1 (t)f k+l (t) + (l-a k (t))f k (t) for k = 0,1, ... ,n — 1, (28) 
df k , 







dt 



(t) + Vi (y^g^itfj . fork = 0,1,..., n. (29) 



Given f k (0) and f k {l), we write V(H) for the set of sequences of probability mass functions 
f k satisfying the end constraints f k (t)\ t= o = f k (0) and f k (t)\ t= i = f k (l), then define distance 



V n via 



V*(f(0), /(l)) = inf f r£gt\t)v a M ) dt. (30) 

Note that if we transpose the geodesic fit) in time and space f x (t) = f n -x{l ~ t), 
a simple symmetry argument gives that taking a x (t) = 1 — a n - x (l — t) gives 7j x a \i) = 
- t), and K 2 (/(0), /(l)) = K 2 (/(l), /(0)). 

3.2 Constant speed paths 

In the continuous Benamou-Brenier formula ( ITOl) . as mentioned above, the infimum is 
obtained when the velocity field is constant with respect to time, using arguments based 
on Cauchy-Schwarz. A similar argument applies here. 

Lemma 3.3. For any geodesic f(t) interpolating between f(0) and f(l), with means \(t) = 

K(/(0),/(l))> |A(0)-A(1)|, 
with equality if and only if v a)k = v for all k and t. 

Proof. We work with the distribution function Fi(t) : = Ylk=o ^ n this notation, in 

analogy with Equation ([9]) we can rewrite Equation ( 1291) as 



f)F 

^(t)+g { r\t)v a ,(t) = 0. (31) 
Since \(t) = ^L (l — F k (t)), summing Equation fl3"TT) over I gives that 

^(*) = £fc (a) (*Ki(*)- (32) 

1=0 

11 



Using Equation ( )29|) and Cauchy-Schwarz, we know that for any t: 



E^Ww 2 = E^(*k*(*) 2 

,fe=0 / \k=0 J \k=0 

2 



> (E^K^)) ( 33 ) 
'<9A 



fc=0 

2 



Observe that equality holds in Equation ( )33|) if and only if v at k(t) = ^if) for all A;. 
Substituting this in Equation (130]) . if fk{t) obtains equality in Equation ( 130]) then we 
obtain 

K 2 (/(o),/(i)) = £ &gt\t)vaAt) 2 ) dt 



2 



> ^ _ w *j P5) 

= (A(l)-A(O)) 2 

again using Cauchy-Schwarz. Note that from above equality holds in Equation (|34|) if and 
only if v a>k (t) = ^(t) for all k and equality holds in Equation ([35]) if = (A(l) - A(0)) 
for all t. □ 

Lemma 13.31 focuses attention on interpolations for which there exist a(t) e A giving 
rise to a v such that the velocity field Vk(t) = v for all k and t. Recall from Definition 11.21 
that we refer to such an interpolation as a 'constant speed path' with speed v, and say 
that f(t) satisfies a modified transport equation. 

Lemma 3.4. If a geodesic fk{t) can be expressed as a constant speed path for some choice 
of v and ex. E A, then this representation is unique (there is no other choice of v and ex. G A 
for which it is a constant speed path). 

Proof. Equation (13"2"1) shows that if there exists a constant speed path with speed v, then 
u = A(l)-A(0). 

Using a similar argument, we can always be explicit about the optimal value of ex. The 
key is to observe that for any choice of ex with a n = 1, the sum 

n— 1 n 

Eft (tt) (*) = E^*) ^6) 

l=k l=k 



12 



Hence, if there exists a constant speed geodesic, then taking v a> i(t) = v in Equation ( 13T|) . 
and taking a partial sum over /, we obtain 

n— 1 i—l n— 1 OTTi / n N 

z=fc z=fc z=fc \J=fc 

so we deduce that if is a constant speed path with speed v, then the corresponding 
a are given by 

afc(t) = • (37) 

An alternative expression is given in terms of fk(t) and g^\t), on rearranging Equation 
[361 to express 

a k (t) = (38) 

□ 

We now show that in certain circumstances our distance measure V n coincides with the 
Wasserstein distance W\, a metric which is known to have a natural relationship to discrete 
interpolations as described in Section 13.31 below. 

Lemma 3.5. If there exists a constant speed path between /(0) and f(l) with speed v then 
then the Wasserstein distance W\(F (0) , F (1)) and V n (f(0),f(l)) coincide, and are equal 
to A(l) - A(0). 

Proof. Recall from the proof of Lemma 13.41 that if there exists a constant speed path with 
speed v, then v = A(l) — A(0). In this case, V n = v = A(l) — A(0). 

Without loss of generality we may assume that v > 0. Using Equation (|3T|) . this means 
that F]f(t) is decreasing in t for all t and k. This means that F(0) stochastically dominates 
F(l) in the standard sense (see for example [32]). Writing F _1 (s;t) = inf{x : F x (t) > s}, 
this means that _F -1 (s; 0) < F _1 (s; 1) for all s, then 

W 1 (F(0),F(1)) = J F-\s;l)ds- J F-\s;0)ds = J ydF^y)- J ydF (y) = A(l) - A(0), 
and the argument is complete. □ 



3.3 Binomial interpolation 

Example 3.6. An interesting example comes from the natural binomial interpolation 
considered in Example \3.1\ By comparing Equations (EIJ) and ( TjS| ) we see that, tak- 
ing atk(t) = k/n, this interpolation has constant speed v a ^(t) = n(q — p) in this sense. 
This means that this interpolation achieves the lower bound in Lemma VJ.'J\ and that 
V n (Bm(n,p),Bin(n,q)) = n(q — p) in this sense, as we would hope. 



13 



Remark 3.7. 



1. We contrast Example \3.6\ with the approach given by Maas [26] and by Erbar and 
Maas fWj (see also Mielke W8I). Specializing their technique, based on Markov chains 
with a given stationary distribution, to the case of random variables on the two-point 
space, we obtain the following. Taking as a reference the stationary distribution 
(7r ,7Ti) = (q/(p+ q),p/(p + q)), J26] writes p 13 for a relative density equivalent to the 
probability mass function f 13 = (/ V/f ) = ((1 - £)/2, (1 + /3)/2). Example 2.6 of J2^ 
implies a distance of 

viv « an 1 [ P /arctanhr 

in this case, in contrast to the \(3 — a\/2 we obtain. 

2. Based on Equation ffflj). which implies the squared length of a (continuous) geodesic 
is 

I!L& (X) ) m dxdt - 

one might imagine that a more natural definition than Equation ( fffOJ) for random 
variables supported on {0, . . . , n} would be 




However, this has the disadvantage that ^(n) is always equal to zero, whereas ft(n) 
need not be. For example, in the two-point case described above, suppose we interpo- 
late between /(0) = (1 — p, p) and /(l) = (1 — q, q), with p < q. Writing 6{t) for a 
function with 6(0) = 1 —p and 6(1) = 1 — q, taking fo(t) = 6(t) and fi(t) = 1 — 6(t), 
Equation / fffgj) gives the length of the path as 6'{t) 2 /6{t)dt. Standard results in 
calculus of variations show that the optimal 8*(t) = (t\/l — q + (1 — t)y/l — p) 2 , with 
squared length 4(^/1 — q — y/l — p) 2 . We believe that such a value and optimal path 
are not as intuitive as the ones resulting from Definition \3.2\ 

Example I3.6l can be generalized considerably as follows. Recall the operation of thinning 
of a probability measure, introduced by Renyi [31]. That is, given a probability mass 
function we can describe the thinned probability mass function 

oo oo 

T t fi = J2hBin(k,l)t l (l-t) k - 1 = £/ fe Bin,(M)- (40) 

k=l k=l 

We can think of this as an interpolation between the original measure / = T\f and a point 
mass at zero T f. This operation was introduced in the context of entropy of random 
variables in [19], and was extended by Gozlan et al. [J4] and by Hillion |17j . 



14 



Definition 3.8. A coupling it of mass functions /(0) and /(l) (that is, a joint distribution 
function ir Xiy whose marginals satisfy f(0) x = J2 y 7l x,y and f(l) y = ^2 x ^x,y), induces a 
geodesic as follows. Consider /(0) and /(l) supported on Z ; then Section 2.2 of [Lflj 
defines a mass function 

f k {t) = vl{t) := Y,K x , y Bm k _ x (\y-x\,t). (41) 

Proposition 2.7 of [14J gives a partial differential equation showing how this mass func- 
tion evolves with t, using a mixture of left and right gradients in a form introduced in |18j . 
Proposition 2.5 of jH] shows that if 7r* is an optimal coupling (in the sense of Wasserstein 
distance W\) then v n (t) defines a (constant speed) geodesic between /(0) and /(l). We 
relate this to the discrete Benamou-Brenier framework above, where recall that Lemma 
13 .51 showed that the Wasserstein distance W\ is a natural one in the 'stochastically ordered' 
context. 

Lemma 3.9. The interpolation of Equation (f^iP can be understood as a constant speed 
path, in the case where x < y for all (x,y) in the support of it. Define v = ^2 xy ^x,y(y — x), 
and7T X)V = Tr Xj y(y — x)/v for another 'distance-biased' joint distribution function. Then we 
can verify that 

?J±(t)+V 1 (vg k (t)) = 0, 
where g k {t) = XL y ^x^^k-xiv — x — l,t). This gives an expression for a k : 

J2x,y^, y [tBm k ^ 1 (y-x,t) + ^-^Bm l _ x (y-x-l,t)(l-^)] 

ak(t) = m - (42) 

Proof. Since for any x, the convolution (1— t)Bm x (m— 1, t)+tBm x -i(m— 1, t) = Bin x (m, t), 
in Equation (T4T|) we can express 



//(*) = y]*** (C 1 ~ t)Bhn-. x (y - x - l,t) +tB'm l ^ l (y-x - l,t)) 



x,y 



and substituting in Equation we obtain the result. □ 

In general, the coefficients ot k defined in Equation (1421) need not lie between and 
1, though we mention one interesting case where they do. Theorem 1.1 of Hillion [16] 
considers a special case of the interpolation of Definition 13. 8[ that is where /(l) is an 
integer translation of /(0), and showed that if / is log-concave, the entropy is a concave 
function of t. 

Example 3.10 (Translation case). If f{l) k+m = f(0) k for some m, then we can interpolate 
by 7t~ x ,y supported only on {(x,y) : y — x — m}, so that n = n, and clearly v = m. 



15 



Substituting in ffllfy , this leaves 



fk(t) = ^/(0),Bin fc _,(m,0 (43) 
i 

9k(t) = ^/(0),Bin^(m-l,t) (44) 



i 



= "aw" 1 — aw (45) 

so i/iai clearly Hes between and 1 /or a// /c and £. 

The results of this paper generalize Hillion's result, in the sense that the form of 
Equation (143]) shows that GLC, Condition [31 holds with equality in this case. Further, 
Equations ( 1431) and ( 1441) show that /fc(t) = (1 — t)gk{t) + tgk-x(t). This means that the 
fc-monotonicity Condition [1] holds as a consequence of log-concavity of Ofc(t) (which follows 
from log-concavity of /). The t-monotonicity, Condition [2J is less straightforward, but can 
be verified using direct calculation, using the log-concavity of h. Since the conditions of 
Theorem II .31 are verified in this case, the concavity of entropy is reproved. 

The question of which interpolations in the form of Definition 13.81 induce coefficients 
< Oik{t) < 1 is an interesting one, which we hope to consider further in future work. 



3.4 Generalized log-concavity 

In the context of continuous densities, results such as logarithmic Sobolev inequalities can 
be viewed in the context of the Bakry-Emery condition [4] (see also for example [9j [3] for 
more details). The Bakry-Emery condition is known to hold if the relative density f/<f>i/ c 
is log-concave (in the continuous sense), where is a normal density. Indeed, Cordero- 
Erausquin [9, Corollary 1] uses arguments based on mass transportation to give a direct 
proof of a log-Sobolev inequality when f/<fii/ c is log-concave. 

In the study of properties of entropy of integer-valued random variables, a key role is 
played by the corresponding property of ultra log-concavity, introduced by Pemantle [30] 
and brought to prominence by work of Liggett [24], who made the following definition: 

Definition 3.11. For any n, a probability mass function supported on {0,1,..., n} is 
ultra log-concave of order n, denoted by ULC(n) ; if the ratio /fc/Binfc(n, t) is a log-concave 
function. Equivalently we require that 

— fl-— )f k+1 ~ — (l --)/*/**> /0 fork = 0,...,n-2. (46) 
n \ n J n \ n J 

We include the possibility that (formally speaking) n = oo, in which case we require that 
the ratio of and a Poisson mass function be log-concave, and write ULC(oo). 

These definitions were first applied in the context of controlling the entropy of random 
variables in the work of Johnson [19] , who showed that, fixing the mean, the entropy is 



16 



maximised in the class ULC(oo) by the Poisson mass function. A corresponding result was 
proved by Yu [41] , who showed that, fixing the mean, the binomial is maximum entropy 
in the class ULC(ra). In particular, it is well-known that by Newton's inequalities (see 
for example Niculescu [29]) that the sums of independent Bernoulli random variables are 
ULC(n). This means that Yu's work generalizes the result (see [27] and [33]) that the 
entropy of Bernoulli sums with a given mean is maximised by the binomial. 

Our generalized log-concavity Condition [3] generalizes Definition [3]TTJ Clearly, compar- 
ing Equations fj46|) and §6§, we see that ULC(n) corresponds to GLC(ck) for a k = k/n, as 
in Example 13.11 As remarked previously, the choice of a k (t) made in the translation case 
Example 13.101 ensures that GLC(ct)k = (i.e. GLC(ck) holds with equality in this case). 

Note that GLC, Condition [3J, and /c-monotonicity, Condition [TJ together imply that / 
is log- concave. 

4 Framework for concavity of discrete entropy 

Recall that in Section [2], the Benamou-Brenier formula led to proofs of concavity of entropy, 
using the property that gt(x) 2 = f t (x)h t (x). In this section, we give a proof of our entropy 
concavity result, Theorem 11.31 In fact, we prove the following more general result: 

Theorem 4.1. Consider a constant speed interpolation f k (t) of probability mass func- 
tions and associated optimal ct(t) and g k a \t), satisfying a modified transport equation (TJP 
^of(t) = — vV\ (j}j^\t)\ ■ If there exists h k such that for all k = 0, . . . n — 2: 

(dk+ij - hkfk+2 > 

h f „(«)>) -> 

hkfk+i - g k g k+ i > 

( (9 k a) ) 2 - Mb) ( OK) 2 - Ww) " (hf k+1 - gtogM) 2 > 

h k > 

where h satisfies ^dt{t) = f 2 V2 (h k ) (as in Equation (j3j)j, then H"(t) < 0. 

Proof. For simplicity, we write g k for g k . First note that Equations (1471) . ()48l) and (H9l) 
together imply that / is log-concave. 



0, (47) 

0, (48) 

0, (49) 

0, (50) 

h k , (51) 



17 



In a standard fashion, we can write the second derivative of entropy as 

«•(') - -E^WMAM)-i^(§ «)' 

fc=0 fc=0 J v 

ft 



-Xyv 2 (fc fc )i°g(A(*))-E 



(ViH fc )) S 



fc=0 
n 



fe=0 



./A; 



fc=0 



< -v' 



22 h k log 



A:=0 



h{t)f k+2 (t) 



k=0 

n 

E 

fc=0 



fk 

(ViQfr))' 

fk 



(52) 
(53) 
(54) 



where Equation ( 1521) follows using Equations (j3J) and ( 1691) respectively, and Equation ( 15B1 
uses the adjoint of V2. Finally Equation ( 1341 follows from Equation ( 1511 and the log- 
concavity of /. 

We will write Si and S2 for the first and second sums in the square bracket of Equation 
(151)1 . noting that the theorem will follow if Si + S2 > 0. Using the convention $ = 0, the 



sum S2 can be transformed in the following way: 



So 



9k 9k9k-i . 9k-i 



Ef- 2 



fk 



fk 



f, 

9 l-2^ 

/& /fe+l fk+2 



,9kgk+l . 9k+l 



We now transform Si using telescopic sums in a way similar to the proof of Theorem 1.1 
of p]: 



Si 



fcez 



fkhk 

~7k 



2h k _i log 



fe-i 



9k9k-\ 



h k -2 log 



jfc-2 



0fc-l 



k&Z JK 



hkfk 
If 



r> 9k9k+i jj ( hkfa+i \ 9k+i jj { hkfk+2 



f, 



fe+i 



9k9k+i 



fk+2 



9l+i 



where U(x) = xlog(x). It is possible to control the Taylor expansion of the function U as 
in [16] by using the inequalities 



2 2 
Vx > , U(1-x)>-x + y> ~ u i l + x ) > ~ x ~ y • 



(55) 



The assumptions ()47j)-(1l9l) each justify the fact that the x > in each of the following 
applications of the inequalities ( 1551) : 



18 



1. 



2. 



fk \ 9k J fk \ 9l 

> 9l ~ h k fk | 1 (gl - h k fkf 
fk 2 f k gl 



^ 9k9k+\ jj ( hkfk+i | 2 3k3k+1 jj ( i _l hkfk+i ~~ iMfc+i 

/fc+i \ 9k9k+i I fk+i 



> -2 



9k9k+i 

hkfk+i — gk9k+i _ (hkfk+i — 9k9k+i) 2 

fk+l fk+l9k9k+l 



3. 



9k±l u ( hkfk+A g|+i ^ r M ~ hk fk+2 

fk+2 \ 9k+l ) fk+2 \ gl+1 

> ^fc+i - hkfk+2 1 (g|+i - hkfk+2) 2 

fk+2 2 fk+29k+l 

We treat separately the first and second order terms arising from these expressions [TH3J 
First adding together the first-order terms of the expansion of S\ we obtain 

9k ~ hkfk _ r fikfk+i — 9k9k+i _ 9k+i ~ hkfk+2 

keZ fk fk+l fk+2 

2 2 

9k ^ 9k9k+\ 9k+\ 

k€Z fk fk+l fk+2 

so the result will be proved if the second-order terms are positive. Using Equation ( |50l) 
gives that the second-order terms satisfy 

1 (9k ~ hkfkf (hkfk+i ~ 9k9k+\f \(9k+\ ~ hkfk+2) 2 



2 fk9 k fk+\9kgk+i 2 fk+29 k +i 

> 1 (9l - hkfkf (j - {Sl+l ~ hkfk+2) | 1 { gl +1 - hkfk+2) 

2 fk9 2 fk+igkgk+i 2 fk+2gl+i 

Log-concavity of / means that the polynomial 

1 S 2 ST 1 T 2 

2 fkgl fk+igkgk+i 2 fk+2gl +i 

19 



has negative discriminant, and is therefore positive for any choice of S, T. In particular, as 
required, Equation (156]) is therefore always positive. 
Since the second-order terms are positive, we have 

H"(t) < -v 2 [St + S 2 ] <0, 

which proves Theorem 14.11 □ 

Note that Theorem 14.11 implies Theorem 11.31 In fact, we can replace t-monotonicity 
(Condition [2]) by a weaker condition, Condition HJ 

Condition 4. Consider a constant speed interpolation, satisfying a modified transport 
equation ^-(t) = — vVi (g^i^)) with some h satisfying ^g^(t) = v 2 V 2 (hk). If we define 



9 „(«)_(€») , fJ a )Yf fJ^Yf 
z 9k 9 k+ ih+i - [9k ) Jk+2 - yg k+1 j jk 

then we require that 

h k <h k for k = 0,1,..., n- 2. (58) 
Proposition 4.2. // Conditions^ and[7] hold then the entropy of H(f) is concave in t. 
Proof. For simplicity, we write 

D k := fl~ fk-ifk+i > (59) 

A k := (f k+ ig { k a) - fkgit) > o (60) 
B k :=(f k+l g { k %-h + 2g { k a) ) > 0, (61) 

The positivity of Ak and Bk follows from GLC and fc-monotonicity, since we can write 
(1 - a k +i)A k = GLC(a) k + [a k+ i - a^fkg^, and a similar expression for B k . 

This choice of h k makes the left hand sides of fT4T|) - fr4T?]) equal to A\j D k+ \, B\lD k +\ 
and AkBk/ Dk+i respectively, which are all positive. Further, Equation (150]) holds with 
equality. 

Since ConditionH]is a restatement of (|5T|) for this particular choice of h, if this Condition 
is satisfied, all the conditions of Theorem 14. II have been verified, and the entropy is therefore 
concave. □ 

We now show that t-monotonicity, Condition |2l implies Condition HI The key is to 
observe that the same coefficients (ctk)k=o,...,n introduced in Equation flTTl) can be used to 
state a second-order modified transport equation: 

Proposition 4.3. If there exist coefficients a giving rise to an interpolation with constant 
speed v then 

^ = v 2 V 2 (h k ) , (62) 



h k ■= 72 Tl ' ( 5? ) 

J fc+1 — Ik Jk+2 



20 



where for k = 0, . . . , n — 2, 



X dot 

h k = (1 - a k ){l - a k+1 )f k + 2a fe+ i(l - a k+1 )f k+1 + a k+1 a k+2 f k+2 ~ fk+i sr^{>63) 



v dt 



Proof. Recall that we write 

g { k a) = a k+l {t)f k+l {t) + (1 - a k {t))f k {t) for k = 0, 1, . . . , n - 1. 
Differentiating Equation (I64p we have 



(64) 



ldg 



(a) 
fe 



- x^/fc , <9a fc . , da k+1 df k+ i 
1 - a k )— - / fc — + /w-^- + "W-gp 



/i 



fc+i" 



at 



,(«) 



,(«) 



vg k _ x - a k vg k 



(<*) 



= Vi [v/ifc] , 

using the expression from (IBUj) . and the proposition follows easily. 



□ 



Lemma 4.4. Consider h k and h k defined in Equations §5T ) and [63^1 . If Conditions^, [H 
and{3\hold, then Condition^ holds. 

Proof. The key is to observe that (in the notation above) 

fl'fc+i^fc + g k o k 



D 



k+l 



and 



i («) , /-i \ («) r 1 a^fc+l 



(65) 



Direct calculation gives 



g^Dk+i 
g k+1 D k+ i 



fk+iA k + f k B k , 

fk+2^-k + fk+\B k . 



Considering the coefficients of A k and B k , we can substitute these expressions in Equation 
fl65|) to obtain: 



r , fk+2(a k+ 2 - a k+ i)A k + f k (a k+1 - a k )B k 1 da k+1 
Hk — n k — — h jfc+i — — > U, 



fc+i 



f dt 



(66) 



where the positivity of A k and follows as in Proposition 14.21 an d the positivity of 

is assumed in Condition [5J □ 

Note that we can regard Equation fl6"B"|) as weaker than Condition [2], since we add a 
term which Condition [1] tells us is positive. 



21 



5 Shepp— Olkin interpolation as a geodesic 

Recall that in Conjecture 11.11 we are given n > 1 affine functions pj : [0,1] — > [0,1] and 
we denote by (f k )k=a,i,...,n the distribution of the sum of independent Bernoulli random 
variables of parameters pi(t), . . .p n (t), where for each i, pi(t) = pj(0)(l — t) + p^. Further 
we write (f k ) k =o,...,n-i f° r the mass function of the ith 'leave one out' sum - that is, the 
distribution of a Bernoulli sum with parameters pi(t), . . . , Pi-iit) , Pi + i(t) , . . . ,p n (t), and 
jrgj) f or flie 'leave two out' sum, involving all parameters except Pi(t) and Pj(t). Further, 
we write 

Df = (/ff - (67) 
ES> = /i°&-/iV£i, (68) 

with corresponding notation for D k , D^'^ and so on. 

We now show how the Shepp-Olkin problem can be viewed in the framework we intro- 
duced above. To be specific, if each derivative p[ is positive it is possible to express the 
Shepp-Olkin interpolation as a constant speed path with speed v in the sense of Definition 
PI That is: 

Proposition 5.1. The probability mass function defined by the Shepp-Olkin interpolation 
satisfies a modified transport equation: 

^(t) + V 1 (vg k ) = 0. (69) 

Here we set v := Y^7=iPi> an d write the probability mass function 

g k (t) : = (1 - a k (t))f k (t) + a k+l {t)f k+l (t), (70) 

where 

„, A E? = iPfo(*)/ffi(*) 1 EILi^(i-^))/f(*) (7U 

vfkit) vf k [t) 

Further, observe that a (t) = and a n (t) = 1, and that if all p\ > then < a k (t) < 1 
for all k and t. 

Proof. Observe that by definition, the f k have probability generating function 

n n 
k=0 i=l 

which has derivative given by 

n a, n 

e = zy<(« - !) ri( i - + 

k=0 i=l 

22 



so comparing coefficients, we see that + Vi (vgk(t)) = 0, where <?fc(t) := ^ SILiK/fc 
Substituting Equation ( J7TT) in Equation ( I7U1) . we obtain that = <7&(i), and so Equation 
follows. 



The values of «o(t) and a n (t) follow from the fact that /_] = fn' = 0. The positivity 
of a k (t) and 1 — a k (t) follow from the assumption that p\ > 0, meaning that all the terms 
in both the fractions in Equation (ITTi) are positive. □ 

For clarity, we now suppress the explicit dependence of a k on t. Observe that the 
/c-monotonicity Condition [1] is automatic for Shepp-Olkin interpolations with p\ > 0. 

Proposition 5.2. For the Shepp-Olkin interpolation described above, ij p\ > for all i 

then the coefficients {oi k ) ke % satisfy the inequality 

Oik < aifc+i, 

that is k-monotonicity (Condition^) holds. 
Proof. If k is such that f k >0 and fk+i > 0, then 

Em / 
i=l PiP 



Moreover, for i G {1, 
f W f _ f W f 

Jk Jk Jk-lJkA 



ttfc+1 - OC k = - 

. m}, we have 



f (*) f 
jfc_iJfc+i 



fk 
a 



fc-1 



_ f« 

Jk-l 



(1 - Pi) fit + Pi ft 



Pi 



'k+1 



> 



/ f (i)\2 _ n(i) Ai) 
\Jk ) Jk-lJk 

by the log-concavity property for the Bernoulli sum (f k )i,-,- 
non- negative finally proves that a k < a k+ ±. 



The fact that each p\ is 

□ 



Remark 5.3. Observe that in this Shepp-Olkin case, these a k can be expressed as a con- 
ditional expectation of a weighted sum, in a similar fashion to the 'scaled score function 7 of 
JHy . This follows since writing Bi for a Bernoulli random variable with parameter pi(t) , 
we obtain P(-Bj = l\Bi + . . . + B n = k) = pi(t) f k \{t) / fk(t) , so that the a k of Equation 
( I7TT) satisfy 



a k (t) = E ( J2 X * B * 



i=l 



k 



(72) 



where weights Aj = p\j (Ylp'i)- Note that in particular, in the 'symmetric' case where p^ = p' 
for all i, then A- = 1/n and a k {t) = k/n. 

This conditional expectation characterization allows us to give an alternative proof of the 
k-monotonicitu Proposition ^ '.B, A result of Efron [7^/ (see also f2Q Equation (3.1)]) shows 
that if <f)(ui, . . . , u n ) is an increasing function and X 1; . . . , X n are independent log-concave 
random variables, then := E [<p(Xi, . . . , X n )\Xi + . . . + X n = k] is an increasing func- 
tion of k. Applying this to <p(Bi, . . . , B n ) = XiBi, the result follows. 



23 



We now prove that the Bernoulli sum mass function is GLC(ck), for the natural choice 
of ex., and hence Condition [3] is automatic in the Shepp-Olkin case. 

Proposition 5.4. In the Shepp-Olkin interpolation case, taking ol as defined in Equation 
(7W , if all thepl are positive then the Bernoulli sum mass function (fk)k=o,i,...,n is GLC(a) ; 
and Condition^ holds. 

Proof. Formula (ITT!) shows that GLC(cx)k can be written as 1/v 2 times 

E^ } ) • (e^ 1 - - (e^ 1 - riff) ■ (e*w&) • ( 73 ) 

Expanding this expression as a quadratic form in p[, . . . ,p' n , the coefficients of pf vanish, 
leaving an expression which simplifies to 

E^-^f^O 2 -^^ 

i<j 

The positivity of this expression, and hence the GLC(ck) property, follow from the log- 
concavity of iff? )k=o,...,n-2 and positivitiy of p\. □ 

6 Concavity of entropy in the Shepp-Olkin regime 

We will now show that entropy is concave in the monotone Shepp-Olkin regime. Having 
already verified Conditions [1] and |3] in Propositions 15.21 and 15.41 Proposition 14.21 shows that 
concavity of entropy will follow if Condition H] holds. 

Proposition 6.1. For monotone Shepp-Olkin interpolations, Condition^ holds if 

E {pfPji 1 ~~ Po)ho + PfPii 1 ~ Pi) h i,i + 2 P'iP'jPi( l - Pi)Pj{ 1 - Pj) C i,j) > °) ( 74 ) 

i<j 



where b i} j and c i: j are defined in Equations (Tyg| ) and below. 
Proof In the Shepp-Olkin case, we know that 

Tli^j PiP'jfk J ' 



h k 



v 2 



We use the fact that (in the notation of Equations (1601) and ( 16T1) the numerator of hk can 
be written as gk+iAk + gkBk, where 

A k := {fk+igk ~ fk9k+i) = -^P'tPiDf > 0, 

i 

B k ■= (fk+igk+i - fk+2gk) = - E^ 1 ~ P^ D k%i > °- 

i 

24 



This means that Condition H] is equivalent to the positivity of 
v 2 (g k+1 A k + g k B k ) - D^J^P^fk'^ 

i+j' 



(75) 



We expand the two bracketed terms in Equation (!75l) in terms of using Lemma [A. II 
below, which implies (using the notation of Equations (157)1 and (168]) ) that 



f (<) f W 



ifc ifc-2 



First observe that 



/^>^r+/r(i-Pi)<! 

Ai) \ f (i)Ai) ] _„./•(*) [fW fW 1 n _ n u(«) [fWfW 1 _ /i _ T) wW 

~~ ^*ifc ifc ifc+1 Pt-Jk+l Jk-lJk+1 v 1 Pt/Jk+1 -Ik Jk+l y 1 Pi/Jk 



- Pi )i ( 2pi jf I)f > -nf&EM + 2(1 - ft )/jSW - (i 



3& 



where each term in square brackets is expanded using Lemma IA.ll Further by writing 



= (1 —Pj)fk' 3> +Pjf k -i we can rearrange the expression for bij as 



Sd) 



->PiPj 



( f(i,j)\ Aid) _ o ( Ai,o)\ Ahi) _|_ f (m) /-(ij) f 
^•/fe J Jk-1 *yk-lj Jk+l ' Jk-2 Jk Jk+l 



1 



(id) Aid) Aid) 



Sd) 



f(id) 
*k+2 



+- Pi (l- Pj )(2[f k 



(id) 



q f f f (id) I / f VMj I f 
°Jk-lJk Jk+l \Jk+l ) J i 



Sd) 



did) 
*k-2 



(76) 



Similarly, using simplifications such as the fact that 

D k = {l- Pi fDf_ 1+P lDf + Pi (l - Pi )Ef. 



25 



the second bracket of Equation (I75j) can be written as pi(l — pi)pj(l — Pj)cij, where 

„ ( f(i,j) ipihj) _ Ahj) p,(iJ) _ AiJ) n^.iA 

c hj ■— yk+l-^k Jk ^k Jk+2 1J k-l J 

— _ ( fdJ)\ 3 i of(»iJ') AiJ) f(»J') _ /" ffeOV f(»>j) 
~~ V / Jk ~ lJk Jk + 1 yk+i J Jk-1 

- ( f (*>i) i Ahj) Ahj) Ahj) 

yk-lj Jk+2'Jk~2Jk J k+2 ' V'J 

□ 

We now verify that Condition 0] holds in the Shepp-Olkin case. 

Lemma 6.2. For the Shepp-Olkin interpolation described above, for each i ^ j, the b^j > 
and 

h ^ Pt(l +Pj( 1 ~Pi) 

°y — 2 Ci ' J ' 

and hence Condition zs satisfied, and so the entropy is concave. 

Proof. To verify the positivity of we simply observe that each of the brackets in Equa- 
tion (176"]) is positive, by an application of the Equations (150]) . (1ST]) . (|84|) and (!85|) proved in 
Appendix [A] below. 

To verify that fry + | (pi(l — p?) + p?(l — Pi)) c%,j is positive, we consider adding the 
final two terms of Equation (1761) to the expression given in (1771) . to obtain 

+ P i(i-p j ) ((./;'•' ) :l - ftli^sti - (/£?) 2 /fiS + stlft j) 01) . 

where the positivity of the two final terms is guaranteed by Equations (1521 and (|83|) below. 

Condition H] is verified by considering the bracketed term in Equation (!74|) . which has 
negative discriminant (under this assumption) since 

4pi(l - PijPjil - PiJcjj - \l>, jl>,.i < cfj (4pi(l - Pi)pj(l - Pj) - (pi(l - Pj) + Pj(l - Pi)) 2 ) 

= -^(Pi- Pi ) 2 <0. 

□ 

Since Condition H] has been verified, the proof of the monotone Shepp-Olkin theorem, 
Theorem 11.51 is complete. 



26 



A Technical results regarding Bernoulli sums 



In this section, we prove some technical results regarding the mass functions of Bernoulli 
sum random variables, required to prove the monotone Shepp-Olkin Theorem 11.51 

Lemma A.l. Let (fk)kez be the Bernoulli sum of parameters pi, ... p m . Then for every 
fcGZ and q > 1 we have the identity 

rn 

qfkfk- q = ^p j {i-Pj) 

Proof. We prove this lemma by induction on the number m of parameters, the case where 
m — 1 being obvious. If {fk)k& is the Bernoulli sum of parameters pi, ■ ■ - p m we set for 

pe[o,l) 

f k : = (1 -p)f k +pfk-i 
and we want to prove, given k G Z and q > 1, that 



f U) Aj) _ f CO f (i) 

Jk-lJk-q Jk Jk-q-1 



(7f 



+7^(1 -P) - ■ (79) 



Expanding each side with the respect to the basis (1 — p) 2 , 2p(l — p),p 2 , it is easy to 
show that Equation f J79|) is satisfied for some k G Z and g > 1 if (ITS"]) holds true for the 
pairs (k, q),(k, q + 1) and (A; — 1, q). □ 

Next we prove the following technical inequality, which may be of independent interest: 

Theorem A. 2. Property (m) holds: that is, for every (g k m ^)kez which is the probability 
mass function of a sum of m independent Bernoulli variables 

Ci{k) := <?& (g k m] ) 2 - 2 (g k m \) 2 g k t + g [ k m] > 0, for all k e Z. (80) 

We first show that Property(m) implies a number of related inequalities, which are 
of use elsewhere in the paper: 

Corollary A. 3. If Property (m) holds, then for any g^ m \ the probability mass function 



27 



for the sum of m independent Bernoulli random variables, for all k e Z: 

2 r , / r , \ 2 , , 



C 2 (A;) 
C 2 (k) 



Ci(k) : ^. 

/ r A 3 



[m] [m] [m] 



9 k 



m m m 



m m m 



Cs(A:) := 2 

2 



[m] [m] [m] 



> 


0. 


(81) 


> 


0. 


(82) 


> 


0. 


(83) 


> 


0. 


(84) 


> 


0. 


(85) 


> 


0. 


(86) 



Proof. First note that these inequalities can be paired up by a duality argument. That is, if 
Property (m) holds for every Bernoulli sum g^ m \ it is true for ~g k := g^_ k with parameters 
1 — pi, 1 — p 2 , . . . , 1 — p m , which implies Equation (|8"Tj) . Similarly (I8"2"j) implies (I8"3"j) and 
implies fl85|) . We will write 



9 k 



[m] [m] 

9k-\9k+v 



In this notation, Equations fl82|) . fl84l) and fl86|) are a consequence of flHUj) . since simple 
calculations show that 

= 2(^H^H - g[ m }J k t)D k ^ + gW Cl (k) > 0, 
g [ k m] C 3 (k) = 2(D k m] )\gt\C 1 (k)>0, 
g^D^k) = 2g k m \C 1 (k)+g™C 1 (k-l)>0. 



□ 



In a similar way, we can argue that: 



Proposition A. 4. If Property(m) is satisfied, then for every sum of m independent 
Bernoulli variables we have 



g M D M + g M D M > 25 H fl H for eyery k G z _ 
Proof. We can restate Property(m) as being equivalent to the inequality, 



If) 



DP > 



9k+2_jj[m 
[ml 

9i-i 



iteration of which gives 



[m] [m] 

m 



ml [ml fe— 1' 

9 k 9 k -i 



28 



so Equation (!H7|) holds if we have 



[m] [m] [m] [rn] 

9k 9k+i , gfc-gfffc+i _ 2 > o 

[m] [m] [m] [m] — ' 

9k-i9k+2 9k 9k-i 



which can be rewritten as 



+ 2- + > 



which is positive by assumption, which proves the proposition. □ 

Proof of Theorem \A.2i We prove Property (m) by induction on the number of parameters 
m. It is clear that Property(l) is true. Let us suppose Property(m) holds for some 
m > 1. In order to prove Property(m + 1) it suffices to show that, for every fceZ, 

f [m+l]\ 2 9 ( n [m+l\\ 2 Jm+1] , [m+1] [m+1] [m+1] „ , 88 ^ 

^fc-i [9k ) ~ 1 [9k-i ) 9 k+ i + 9 k -2 9 k 9 k +i > u ' \P^) 

where 

g [m+l] Jg 

the distribution of a sum of m + 1 Bernoulli variables. For p = p m+ i G [0, 1], 
we can write 5 , [ m+1 ' := (1 — p)g^ + pgt^i- To prove that (ISSjl is positive, we expand it as 
a polynomial in p, of order 3, in the basis (1 — p) 3 ,p(l — p) 2 ,p 2 (l — p),p 3 , and show that 
the coefficients of each of these terms are positive. 

1. The coefficient of (1 — p) 3 is Ci(k) which is clearly positive, by Property(m). 

2. The coefficient of p 3 is Ci(k — 1) which is also positive, by Property (m). 

3. The coefficient of p(l — p) 2 is Di(k) which is positive, since Property(m) implies 
Equation fl86|) . 



4. The coefficient of p 2 (l — p) can be written 

[m] n [m] M n [m] _ 9 M n M 

Uk-l^k-l "r 9k-3 LJ k z i/fc+l- Ly fc-2> 

which is positive by Proposition IA.4I 

Since each coefficient is positive, we deduce that Equation (1881) is satisfied, which shows 
that Property(m + 1) holds. □ 



29 



References 

[1] S.-i. Amari and H. Nagaoka. Methods of information geometry, volume 191 of Transla- 
tions of Mathematical Monographs. American Mathematical Society, Providence, RI, 
2000. 

[2] L. Ambrosio, N. Gigli, and G. Savare. Gradient flows in metric spaces and in the space 
of probability measures. Lectures in Mathematics ETH Zurich. Birkhauser Verlag, 
Basel, second edition, 2008. 

[3] C. Ane, S. Blachere, D. Chafai, P. Fougeres, I. Gentil, F. Malrieu, C. Roberto, and 
G. Scheffer. Sur les inegalites de Sobolev logarithmiques. Panoramas et Syntheses, 
10:217, 2000. 

[4] D. Bakry and M. Emery. Diffusions hypercontractives. In Seminaire de probabilites, 
XIX, 1983/84, volume 1123 of Lecture Notes in Math., pages 177-206. Springer, Berlin, 
1985. 

[5] A. R. Barron. Entropy and the Central Limit Theorem. Ann. Probab., 14(l):336-342, 
1986. 

[6] J.-D. Benamou and Y. Brenier. A numerical method for the optimal time-continuous 
mass transport problem and related problems. In Monge Ampere equation: appli- 
cations to geometry and optimization (Deerfield Beach, FL, 1997), volume 226 of 
Contemp. Math., pages 1-11. Amer. Math. Soc, Providence, RI, 1999. 

[7] J.-D. Benamou and Y. Brenier. A computational fluid mechanics solution to the 
Monge-Kantorovich mass transfer problem. Numer. Math., 84(3):375-393, 2000. 

[8] E. A. Carlen and W. Gangbo. Constrained steepest descent in the 2-Wasserstein 
metric. Ann. of Math. (2), 157(3):807-846, 2003. 

[9] D. Cordero-Erausquin. Some applications of mass transport to Gaussian-type inequal- 
ities. Arch. Ration. Mech. Anal, 161(3):257-269, 2002. 

[10] M. H. M. Costa. A new entropy power inequality. IEEE Trans. Inform. Theory, 
31(6):751-760, 1985. 

[11] T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley, New 
York, 1991. 

[12] B. Efron. Increasing properties of Polya frequency functions. Ann. Math. Statist., 
33:272-279, 1965. 

[13] M. Erbar and J. Maas. Ricci curvature of finite Markov chains via convexity of the 
entropy. Archive for Rational Mechanics and Analysis, 206:997-1038, 2012. 



30 



[14] N. Gozlan, C. Roberto, P.-M. Samson, and P. Tetali. Displacement convexity of 
entropy and related inequalities on graphs. See arXiv: 1207 .51161 2012. 

[15] L. Gross. Logarithmic Sobolev inequalities. Amer. J. Math., 97(4):1061-1083, 1975. 

[16] E. Bullion. Concavity of entropy along binomial convolutions. Electron. Commun. 
Probab., 17:no. 4, 1-9, 2012. 

[17] E. Hillion. Contraction of measures on graphs. In submission: see 
|http : / / www . maths . br is . ac . uk/ ~m axeh/MCPGraph . pdf [ 2012. 

[18] E. Hillion, O. T. Johnson, and Y. Yu. A natural derivative on [0, n] and a binomial 
Poincare inequality. In submission, see larXiv: 1107.01271 2011. 

[19] O. T. Johnson. Log-concavity and the maximum entropy property of the Poisson 
distribution. Stock Proc. Appl, 117(6):791-802, 2007. 

[20] O. T. Johnson and Y. M. Suhov. The von Neumann entropy and information rate 
for integrable quantum Gibbs ensembles 2. Quantum Computers and Computing, 
4(1):128-143, 2003. 

[21] R. Jordan, D. Kinderlehrer, and F. Otto. The variational formulation of the Fokker- 
Planck equation. SI AM J. Math. Anal, 29(1):1-17, 1998. 

[22] I. Kontoyiannis, P. Harremoes, and O. T. Johnson. Entropy and the law of small 
numbers. IEEE Trans. Inform. Theory, 51(2):466-472, 2005. 

[23] C. Leonard. Private communication. 2013. 

[24] T. M. Liggett. Ultra logconcave sequences and negative dependence. J. Combin. 
Theory Ser. A, 79(2):315-325, 1997. 

[25] J. Lott and C. Villani. Ricci curvature for metric-measure spaces via optimal transport. 
Ann. of Math. (2), 169(3) :903-991, 2009. 

[26] J. Maas. Gradient flows of the entropy for finite Markov chains. J. Fund. Anal., 
261(8):2250-2292, 2011. 

[27] P. Mateev. The entropy of the multinomial distribution. Teor. Verojatnost. i Prime- 
nen., 23(1):196-198, 1978. 

[28] A. Mielke. Geodesic convexity of the relative entropy in reversible Markov chains. 
Calculus of Variations and Partial Differential Equations, pages 1-31, 2012. Online 
First article, doi : 10 . 1007/s00526-012-0538-8. 

[29] C. P. Niculescu. A new look at Newton's inequalities. JIPAM. J. Inequal. Pure Appl. 
Math., 1, 2000. Issue 2, Article 17; see also |http : // j ipam . vu . edu . au/ 1 



31 



[30] R. Pemantle. Towards a theory of negative dependence. J. Math. Phys., 41 (3): 1371- 
1390, 2000. 

[31] A. Renyi. A characterization of Poisson processes. Magyar Tud. Akad. Mat. Kutato 
Int. Kdzl, 1:519-527, 1956. 

[32] M. Shaked and J. G. Shanthikumar. Stochastic orders. Springer Series in Statistics. 
Springer, New York, 2007. 

[33] L. A. Shepp and I. Olkin. Entropy of the sum of independent Bernoulli random 
variables and of the multinomial distribution. In Contributions to probability, pages 
201-206. Academic Press, New York, 1981. 

[34] A. J. Stam. Some inequalities satisfied by the quantities of information of Fisher and 
Shannon. Information and Control, 2:101-112, 1959. 

[35] K.-T. Sturm. On the geometry of metric measure spaces. I. Acta Math., 196(1):65-131, 
2006. 

[36] K.-T. Sturm. On the geometry of metric measure spaces. II. Acta Math., 196(1):133- 
177, 2006. 

[37] C. Villani. A short proof of the concavity of entropy power. IEEE Trans. Inform. 
Theory, 46(4):1695-1696, 2000. 

[38] C. Villani. Topics in optimal transportation, volume 58 of Graduate Studies in Math- 
ematics. American Mathematical Society, Providence, RI, 2003. 

[39] C. Villani. Optimal transport: Old and New, volume 338 of Grundlehren der Mathe- 
matischen Wissenschaften. Springer- Verlag, Berlin, 2009. 

[40] Y. Yu. On the maximum entropy properties of the binomial distribution. IEEE Trans. 
Inform. Theory, 54(7):3351-3353, July 2008. 

[41] Y. Yu. Monotonic convergence in an information-theoretic law of small numbers. 
IEEE Trans. Inform. Theory, 55(12):5412-5422, 2009. 

[42] Y. Yu and O. T. Johnson. Concavity of entropy under thinning. In Proceedings of 
ISIT 2009, 28th June - 3rd July 2009, Seoul, pages 144-148, 2009. 

Erwan Hillion: School of Mathematics, University of Bristol, University Walk, Bristol, 
BS8 1TW, UK. Email: Erwan.Hillion@bristol.ac.uk 

Oliver Johnson: School of Mathematics, University of Bristol, University Walk, Bristol 
BS8 1TW. UK. Email: o.johnson@bristol.ac.uk 



32