Guesswork Subject to a Total Entropy Budget
Arman Rezaee Ahmad Beirami Ali Makhdoumi Muriel Medard Ken Duffy
cs.IT cs.CR math.IT









 
Guesswork Subject to a Total Entropy Budget

    Arman Rezaee, Ahmad Beirami, Ali Makhdoumi, Muriel Médard, and Ken Duffy


A. Rezaee, A. Beirami, A. Makhdoumi, and M. Médard are with the Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MA, USA. Emails: {armanr, beirami, makhdoum, medard}@mit.edu.

K. Duffy is with the National University of Ireland Maynooth, Ireland. Email: ken.duffy@nuim.ie.

    December 30, 2023
=====================================================================================================================================================================================================================================================================================================================================================================================================






We consider an abstraction of computational security in password protected systems where a user draws a secret string of given length with i.i.d. characters from a finite alphabet, and an adversary would like to identify the secret string by querying, or guessing, the identity of the string. The concept of a “total entropy budget” on the chosen word by the user is natural, otherwise the chosen password would have arbitrary length and complexity. One intuitively expects that a password chosen from the uniform distribution is more secure. This is not the case, however, if we are considering only the average guesswork of the adversary when the user is subject to a total entropy budget. The optimality of the uniform distribution for the user's secret string holds when we have also a budget on the guessing adversary. We suppose that the user is subject to a “total entropy budget” for choosing the secret string, whereas the computational capability of the adversary is determined by his “total guesswork budget.” We study the regime where the adversary's chances are exponentially small in guessing the secret string chosen subject to a total entropy budget. We introduce a certain notion of uniformity and show that a more uniform source will provide better protection against the adversary in terms of his chances of success in guessing the secret string.
In contrast, the average number of queries that it takes the adversary to identify the secret string is smaller for the more uniform secret string subject to the same total entropy budget.








§ INTRODUCTION
 

We consider the problem of identifying the realization of a discrete random variable X by repeatedly asking questions of the form: “Is x the identity of X?". This problem has been extensively studied by cryptanalysts who try to identify a secret key by exhaustively trying out all possible keys, where it is usually assumed that the secret key is drawn uniformly at random. We consider an n-tuple X^n := X_1,…, X_n drawn from an i.i.d. source, μ_θ(·) on a finite alphabet 𝒳, where θ represents the corresponding categorical distribution, which is not necessarily uniform. 
We measure security against a brute-force attacker who knows the source statistics completely, and who would query all the secret strings one by one until he is successful. 

Denoting the number of guesses by G_θ^n(X^n), the optimal strategy of the attacker that minimizes the expected number of queries 𝔼[G_θ^n(X^n)] is to guess the possible realizations of X^n in order of decreasing probability under μ_θ^n(·). Massey <cit.> proved that the Shannon entropy of X^n, H(X^n), is a lower bound on the rate of growth of the expected guesswork, yet there is no upper bound on 𝔼[G_θ^n(X^n)] in terms of H(X^n). Arıkan <cit.> proved that when we consider a string of growing length whose characters are drawn i.i.d, the positive moments of guesswork associated with the optimal strategy grow exponentially, and the exponents  are related to the Rényi entropies of the single letter distribution:[In this paper, log(·) denotes the natural logarithm.]

    lim_n→∞1/nlog𝔼_θ[ ( G_θ^n(X^n))^ρ] = H_1/(1+ρ)(X),

where the Rényi entropy of order ρ is 

    H_ρ (X) = 1/1-ρlog( ∑_x ∈𝒳 P(X = x)^ρ).

Note that lim_ρ→ 0 H_ρ(X) = H(X) recovers the Shannon entropy. We also use the notations H_ρ(θ) and H_ρ(X) interchangeably to refer to the Rényi entropy of a string drawn from a source with parameter vector θ. Although these connections have been extended to more general stochastic processes <cit.>, in this paper, we focus on i.i.d. processes for the sake of clarity of presentation.

Christiansen and Duffy <cit.> showed that the sequence {n^-1log G_θ^n(X^n)} satisfies a Large Deviations Principle (LDP) and characterized its rate function, Λ^*_θ. 
Beirami et al. <cit.> showed that Λ_θ^* can be expressed as a parametric function of the value of a “tilt” in a family of tilted distributions. 



We remark that when the metric of difficulty is the growth rate
in the expected number of guesses as a function of string length,
the challenge for the adversary remains the same even if the adversary
does not know the source statistics <cit.>.

In this paper, we first show a counter intuitive result that the average guesswork increases when the source becomes “less uniform” if the user is subject  to a total entropy budget on the secret string. Next, we introduce a natural notion of total guesswork budget on the attacker and show that the probability of success of an  adversary subject to a total guesswork budget increases when the source becomes “less uniform,” which is consistent with our intuition of choosing uniform passwords. We will formalize these notions in the rest of this paper.





§ PROBLEM SETUP



Given a finite alphabet X,
a memoryless (i.i.d) source on X is defined by the set of probabilities θ_i = P[X = x_i] for all i ∈ [|X|], where [n]:= {1, …, n} and ∑_i ∈ [|X|]θ_i =1.  Hence, θ is an element of the (|𝒳|-1)-dimensional probability simplex. We define Θ_|X| as the open set of all probability vectors θ such that θ_i > 0 for all i ∈{1,…,|𝒳|}, which also excludes the uniform source u_|X| = (1/|X|, …, 1/|X|).


The tilt operation plays a central role in the analysis, and is the basis for many of our derivations:

For any α∈ℝ, define τ(θ, α) as the “tilted θ of order α”, where 
τ(θ,α) = (τ_1(θ,α), …, τ_|X| (θ,α)), where τ_i: Θ_|X|×ℝ→Θ_|X| for all i ∈ [|X|] is given by

    τ_i(θ,α) := θ_i^α/∑_ı=1^|X|θ_i^α.




Let Γ_θ^+ ∈Θ_|X| denote the “tilted family of θ” and be given by

    Γ_θ^+:= {τ(θ,α) :α∈ℝ_>0}.


Observe that Γ^+_θ∈Θ_|X| is a continuum of stochastic vectors in the probability simplex.
Thus, the tilted family of a memoryless string-source with parameter vector θ is comprised of a set of memoryless string-sources whose parameter vectors belong to the tilted family of the vector θ, i.e., Γ^+_θ.


Let Γ_θ^+ and Γ_θ^+ denote the sets of high-entropy and low-entropy members of the tilted family of θ, respectively, and be given by:

    Γ_θ^+ = {τ(θ,α) }_0≤α < 1, Γ_θ^+ = {τ(θ,α) }_α > 1.

Hence,
Γ_θ^+ = Γ_θ^+ ∪Γ_θ^+ ∪θ .

Figure <ref> depicts the probability simplex of all possible ternary parameter vectors, |𝒳| = 3. The yellow star represents the distribution θ = (0.1,0.2,0.7).  Note that the tilted family of θ is parametrized by α. At α=0, we get the uniform distribution τ(θ,0) = u_3 = (1/3,1/3,1/3) and as α→∞, we get to the degenerate case of (0,0,1). The high-entropy and low-entropy members of the tilted family of θ are represented by blue and red, respectively. Note that all distributions in the high-entropy set, Γ_θ^+, have Shannon entropies higher than that of θ and are closer to the uniform distribution in the KL divergence sense <cit.>. Hence, the higher entropy members of the tilted family are “more uniform” than the lower entropy members of the tilted family.






Let h ∈ (0,log |X|] denote the entropy budget per source character such that the user is required to choose a secret string from an i.i.d. process with parameter vector θ with H(θ) = h.

The concept of  a total entropy budget on the entire secret string is a natural one or the user would choose an arbitrarily complex secret string. We use the entropy budget per source character defined above to ensure that the user is subject to the same total entropy budget by adjusting the length of the secret string for a fair comparison between string sources that have different entropy rates.





§ POSITIVE MOMENTS OF GUESSWORK

We first consider choosing strings with the same total (Shannon) entropy budget and measure security in terms of the positive moments of guesswork. If two sources have different entropy rates, we adjust the comparison by drawing a longer string from the lower entropy source. 
Formally, let us consider two sources with parameter vectors θ_1 and θ_2 on alphabet X. 
Further, let H(θ_1) and H(θ_2) be the entropy rates of the two sources.
Let the entropy ratio be

    η := H(θ_2)/H(θ_1).

Without loss of generality, throughout this paper we assume that H(θ_2)<H(θ_1), and hence 0<η<1. The user is given the option to choose a secret string from either of the two sources. For a fair comparison, we assume that the entropy of the two strings is the same, n_1 H(θ_1) = n_2 H(θ_2).
That is

    n_2    = 1/η n_1.

To compare the growth rates of the positive moments of guesswork, in light of (<ref>), we compare H_1/(1+ρ)(θ_1) and 1/η H_1/(1+ρ)(θ_2). This will in turn impose the same total entropy budget on the strings drawn from the sources with parameter vectors θ_1 and θ_2.

For a parameter vector θ, let an information random variable be defined as one that it takes the value log1/θ_i with probability θ_i for all i ∈ [|X|]. 
We need one more definition before we can state the result of this section:

A source with parameter vector θ∈Θ_|X| is said to satisfy the skewentropy condition (SEC) if

    V(θ)^2 + 2H(θ) V(θ) - H(θ) S(θ) >0,

where V(θ) is the varentropy defined as the variance of an information random variable corresponding to θ:

    V(θ) := ∑_i ∈ [|X|]θ_i (log1/θ_i - H(θ) )^2.

and S(θ) is the skewentropy, which is the skewness of an information random variable corresponding to θ:

    S(θ) := ∑_i ∈ [|X|]θ_i (log1/θ_i - H(θ) )^3.




Note that varentropy has been studied extensively and naturally arises in the finite block length information theory <cit.>, and more recently in the study of polar codes <cit.>. To the best of our knowledge, skewentropy has not been studied before, and we provide some properties of the SEC in Section <ref>. 


Equipped with this definition, we provide an ordering of the sources that belong to the same tilted family.


Let θ_1 ∈Θ_|X|. For any θ_2 ∈Γ^+_θ_1,

    H_1/(1+ρ)(θ_1) < 1/η H_1/(1+ρ)(θ_2)   ∀ρ>0,

if and only if θ_1 satisfies the SEC in Definition <ref>.
Note that  η is the entropy ratio defined in (<ref>).


The proof is provided in the appendix.
Theorem <ref> provides a natural ordering of sources that belong to the same tilted family. The “less uniform” low per-character entropy members of the tilted family take exponentially more number of queries, on the average, to breach compared to their more uniform higher per character entropy counterparts. 

Let u_|X| denote the uniform source. Then for any θ∈Θ_|X|, and any ρ>0,

    log |X| = H_1/(1+ρ)(u_|X|) < 1/η H_1/(1+ ρ)(θ),

where η= H(θ)/ log |X|.


Corollary <ref> suggests that, of all sources whose parameter vectors are in the (interior of the) probability simplex, the uniform source is the easiest to breach in terms of the positive moments of guesswork when the user is subject to a total entropy budget.
This is in contrast to our intuition that more uniformity provides better security.





§ PROBABILITY OF SUCCESS SUBJECT TO
A GUESSWORK BUDGET

In this section, we put forth a natural notion of total guesswork budget, leading to a security metric consistent with our intuition. Similar to the case of an entropy budget, we need to define guesswork budget per source character for our analysis.

Let g ∈ (0,log |X|] denote the guesswork budget per source character, such that e^gn is the total number of queries that the inquisitor can make in order to identify a secret string of length n. 

Note that by this definition, the inquisitor is supposed to possess the resources for querying an exponentially growing number of strings (with the sequence length). In particular,  g = log|X| corresponds to an adversary who is capable of querying all of the possible |X|^n outcomes of the source to successfully identify the secret string with probability 1.



If g<H(θ), then 

    lim_n →∞ℙ_θ[G_θ(X^n) ≤ e^gn] = 0,

and if g>H(θ), then

    lim_n →∞ℙ_θ[G_θ(X^n) ≤ e^gn] = 1.



Recall that Arıkan <cit.> showed that the growth rate of the moments of guesswork is governed by atypical sequences resulting in the appearance of the Rényi entropies in the expression. On the other hand, Lemma <ref> states that the cutoff for the adversary to be successful with high probability is still governed by the Shannon entropy (as intuitively expected).

In the regime where g<H(θ), we would like to study  the behavior of correct guessing. The next lemma relates the exponent of an exponentially large number of possible guesses  to the LDP rate function.

If g<H(θ), then

    lim_n →∞1/nlog1/ℙ_θ[G_θ(X^n) ≤ e^gn] = Λ^*_θ(g).


Hence, ℙ_θ[G_θ(X^n) ≤ e^gn] ≈ e^-n Λ^*_θ(g), and a larger Λ^*_θ(g) directly implies a more secure source against a brute-force attacker who is subject to a guesswork budget g for a fixed n. We use the above rate function as the metric for comparing two string-sources given a total guesswork budget, naturally defined as g × n. 


Using the notion of the tilt, we can represent the rate function Λ_θ^*(g) as a parametric function of α for a family of tilted distributions.
The rate function, Λ_θ^*(g), associated with θ∈Θ_|X| can be directly computed as <cit.>:

    Λ^*_θ(g) = D( τ(θ,α(g)) ‖θ),

for α(g) = _α∈ℝ^+{ H(τ(θ,α)) = g }. This characterization plays a central role in our derivations.

 
Recall that we adjust the string lengths in order to make sure that the secret string chosen by the user is subject to a given total entropy budget. 
As the idea of the total guesswork budget is that the adversary can make a fixed number of queries regardless of the source from which the user is choosing the password, we compare the sources in terms of the probability of success subject to an adjusted guesswork budget per source character (see (<ref>)). To keep the total guessing budget of the adversary the same, i.e., e^n_1 g_1 = e^n_2 g_2,  we must adjust the guesswork budget per source character as follows:

    g_2 = η g_1.

In light of (<ref>), we compare Λ^*_θ_1(g_1) with 1/ηΛ^*_θ_2(g_2) = 1/ηΛ^*_θ_2(η g_1) for sources with parameter vectors θ_1 and θ_2.




We are now ready to  provide our results on the adversary's probability of success.

Let θ_1 ∈Θ_|X|. For any θ_2 ∈Γ^+_θ_1, 

    Λ_θ_1^*(g_1) > 1/ηΛ_θ_2^*(g_2),   ∀ g_1<H(θ_1),
 
if and only if θ_1 satisfies the SEC (see Definition <ref>). 


We remark that the same SEC appears to be the crucial quantity for the statement of Theorem <ref> to hold. 
This theorem implies that when the adversary is subject to a guesswork budget g_1 (i.e., he can only submit e^n_1g_1 queries to identify a secret string of length n) for some g_1∈(0, H(θ_1)), then the chances of correctly identifying the random string produced by a “more uniform” high per-character entropy member of the tilted family is exponentially smaller than that of the less uniform low per-character entropy source belonging to the same tilted family so long as the source satisfies the SEC when the user is subject to the same total entropy budget and the adversary is subject to the same total guesswork budget.
In particular, the uniform source is the most secure against such an adversary subject to a guesswork budget:


Let u_|X| denote the uniform information source. Then, for any θ∈Θ_|X| and g < log |X|, we have

    log |X| - g = Λ_u_|X|^*(g) > 1/ηΛ_θ^*(η g)  ,
 
where η= H(θ)/ log |X|.


We remark that these security guarantees are against an adversary that is not powerful enough to be able to explore the entire typical set rendering his chances of success exponentially small. The “more uniform” sources provide an exponentially smaller chance to such an adversary to be successful.


We emphasize that the implications of Theorems <ref> and <ref> are in stark contrast to each other. On the one hand, more uniformity results in an exponential decrease in the  number of queries expected of an adversary to correctly identify a secret string when the user is subject to a total entropy budget (Theorem <ref>). On the other hand, more uniformity decreases the chances of an adversary in identifying the secret string when the adversary's power is limited by a total guesswork budget  as well (Theorem <ref>).










§ PROPERTIES OF THE SEC


Noting that SEC introduced in Definition <ref> is a new concept, we study this condition in more detail in this section.
Let us start with the binary memoryless sources. 

Let θ∈Θ_2. Further,  let ϕ = min{θ_1, θ_2}< 1/2. Then,

    H(θ)    =  ϕlog(1/ϕ) + (1-ϕ) log(1/1-ϕ),
    
    V(θ)     = ϕ (1-ϕ) log^2 (1-ϕ/ϕ),
    
    S(θ)     = ϕ(1-ϕ)(1-2ϕ) log^3 (1-ϕ/ϕ).
 

The next theorem is our main result for binary memoryless sources:

Any θ∈Θ_2 satisfies the SEC.


While Theorem <ref> shows that all binary memoryless sources satisfy the SEC, the same argument does not extend to larger alphabets. 

For any |X|>2, there exists θ∈Θ_|X|, such that θ does not satisfy the SEC.







Despite the negative result in Theorem <ref>, we show that sources that are approximately uniform satisfy the SEC for any alphabet size. 
Here is the key result for such sources:

Suppose that θ∈Θ_|X| is such that 

    |log1/θ_i - H(θ)| < 2,   ∀ i ∈ [|X|].

Then θ satisfies the SEC.


As a corollary, we state the condition more explicitly in terms of θ_i's.

Suppose that θ∈Θ_|X| is such that 

    e^-1/|X|<θ_i < e/|X|,   ∀ i ∈ [|X|].

Then, θ satisfies the SEC. 




Figure <ref> depicts the set of ternary distributions that do not satisfy the SEC. As can be seen, source close to uniform satisfy the SEC while sources that are close to uniform on a two-dimensional alphabet while almost missing the third character in the alphabet do not satisfy the SEC.







§ NUMERICAL EXPERIMENTS







In this section, we provide some numerical experiments. We compare several binary sources, where θ = (θ_1, θ_2) is the source parameter vector.  
The parameter vectors used for the experiments are listed in Table <ref>. The length and the parameter vector are chosen such that n H(θ) = 9 log2 nats for all of the pairs.
Although the theorems proved in this paper are of asymptotic nature, we have chosen to run experiments on finite-length sequences instead to emphasize the applicability of the results even in very short lengths. 
As can be seen in Fig. <ref>, as the entropy rate of the source decreases, the moments of guesswork increase exponentially subject to the same entropy budget. On the other hand, as shown in Fig. <ref>, as the entropy rate of the source decreases, the chances of an adversary subject to a fixed total guesswork budget increases, which is consistent with our intuition. 












§ CONCLUSION

In this paper, we studied guesswork  subject to a total entropy budget. We showed that the conclusions about security deduced from the analysis of the average guesswork could be counter-intuitive in that they suggest that the uniform source is not the strongest source against brute-force attacks. To remedy the problem, we introduced the concept of total guesswork budget, and showed that if the adversary is subject to a total guesswork budget, the uniform source provides the strongest security guarantees against the brute-force attacker, which is consistent with our intuition.


[Proofs]







[Proof of Theorem <ref>]
This is equivalent to showing that for all ρ>0,

    H_1/(1+ρ) (θ_2)/H(θ_2) > H_1/(1+ρ) (θ_1)/H(θ_1)

for all θ_2 ∈Γ^+_θ. Let β := 1/(1+ρ), and hence β<1.
The statement above is in turn equivalent to showing:

    ∂/∂α[ H_β (τ(θ_1, α))/H(τ(θ_1, α))]_α = 1 > 0,   ∀β<1.

It is straightforward to show that (<ref>) is equivalent to 

    ∂/∂α[ H_β (τ(θ_1, α))]_α = 1/H_β(θ_1)> ∂/∂α[ H (τ(θ_1, α))]_α = 1/H(θ_1),   ∀β<1.

Finally, we prove the following statement that is equivalent to (<ref>):

    ∂/∂β[∂/∂α[ H_β (τ(θ_1, α))]_α = 1/H_β(θ_1)]_β=1<0.

This is equivalent to showing:

    ∂^2/∂α∂β[H_β (τ(θ_1, α)) ]_α = β=1   H (θ_1) 
    
    <
       ∂/∂β[H_β (θ_1) ]_β = 1  ∂/∂α[H (τ(θ_1, α)) ]_α =1.

The above statement is shown to hold if and only if θ_1 satisfies the SEC (Definition <ref>) invoking Lemmas <ref>, <ref>, and <ref>, which completes the proof of the theorem.


For all θ∈Θ_|X|, we have

    ∂/∂α[H (τ(θ, α)) ]_α = 1 = - V(θ).



See <cit.> for the proof.

For all θ∈Θ_|X|, we have

    ∂/∂β[H_β (θ) ]_β =1  = -1/2 V(θ).



See <cit.> for the proof.

For all θ∈Θ_|X|, we have

    ∂^2/∂α∂β[H_β (τ(θ, α)) ]_α = β =1 = - V(θ) +1/2 S(θ).




It is proved in <cit.> that

    ∂/∂α[H_β (τ(θ, α)) ]_α = 1 = β/1-β( H(θ) - H(τ(θ, β)||θ)  ).

Hence, we differentiate with respect to β to get:

    ∂^2/∂α∂β[H_β (τ(θ, α)) ]_α = 1    = 1/(1-β)^2( H(θ) - H(τ(θ, β)||θ)  ) 
        +β/1-βV(τ(θ, β)||θ) .

Next, we take the limit as β→ 1, and by applying  L'Hospital's rule we arrive at:

    ∂^2/∂α∂β[H_β (τ(θ, α)) ]_α = β =1 = - V(θ) -1/2∂/∂β [V(τ(θ, β)||θ)]_β=1.

Finally, the proof is completed by invoking Lemma <ref>.



For any θ∈Θ_|X|, 

    ∂/∂α [V(τ(θ, α)||θ)]_α=1 = - S(θ),

where S(θ) is defined in (<ref>).



By definition

    .∂/∂αV(τ( θ, α)||θ)|_α = 1
    
       = ∑_i ∈ [|X|].∂/∂ατ_i( θ, α) |_α=1(H(τ(θ,α)||θ) - log1/θ_i)^2
       = ∑_i ∈ [|X|]θ_i (H(τ(θ,α)||θ) - log1/θ_i)^3
        = -S(θ),

where (<ref>) follows by invoking Lemma 8 of <cit.>.




[Proof of Theorem <ref>]
Let us recall that θ_2 = τ(θ_1,α) for some α>1. We can find t_1 and t_2 in the domain of each rate function such that the derivatives of the rate function are both equal to a constant ρ>-1. It follows from <cit.> that:

    t_1 =  _t{∂/∂ tΛ_θ_1^*(t) = ρ}   ⇒  t_1 =  H(τ(θ_1, β)), 
    
    t_2  =  _t{1/η∂/∂ tΛ_θ_2^*(η t)  = ρ}   ⇒  t_2 = 1/η H(τ(θ_2, β)) ,

where β = 1/(1+ρ). We focus on ρ<0, and hence β∈ (1,∞). Note that β = 1, (equivalently ρ=0) corresponds to the coinciding zeros of both rate functions. Once again recalling that the rate functions are convex, proving (1/η) Λ_θ_2^*(η t) > Λ_θ_1^*(t) is equivalent to showing that t_2 < t_1 (as defined in (<ref>)) for all β >1. This is in turn equivalent to showing:

    H(τ(θ_2,  β))/H(θ_2)  < H(τ(θ_1,β))/H(θ_1) , ∀α,β > 1.

This is equivalent to:

    ∂/∂α[H(τ(θ_1, αβ))/H(τ(θ_1,α))]_α=1 <0,   ∀β>1.

It is straightforward to show that (<ref>) is equivalent to 

    ∂/∂α[ H (τ(θ_1, αβ))]_α = 1/H(τ(θ_1,β))> ∂/∂α[ H (τ(θ_1, α))]_α = 1/H(θ_1),   ∀β>1.

Finally, we prove the following statement that is equivalent to (<ref>):

    ∂/∂β[∂/∂α[ H (τ(θ_1, αβ))]_α = 1/H(τ(θ_1,β))]_β=1<0.

This is equivalent to showing:

    ∂^2/∂α∂β[H (τ(θ_1, αβ)) ]_α = β=1   H (θ_1)
    
    <
       ∂/∂β[H (τ(θ_1,β)) ]_β = 1  ∂/∂α[H (τ(θ_1, α)) ]_α =1.

The above statement is shown to hold if and only if θ_1 satisfies the SEC (Definition <ref>) invoking Lemmas <ref> and <ref>, which completes the proof of the theorem.



For all θ∈Θ_|X|, we have

    ∂^2/∂α∂β[H (τ(θ, αβ)) ]_α = β =1 = - 2V(θ) + S(θ).




Noting that τ(θ, αβ) = τ(τ(θ, β),α) and invoking Lemma <ref>, we have

    ∂/∂α[H (τ(θ, αβ)) ]_α = 1   = - V(τ(θ,β))
        = - β^2 V(τ(θ,β)||θ),

where (<ref>) follows from Lemma 5 of <cit.>.
Hence, by differentiating the above with respect to β at β=1 and invoking Lemma <ref>, we arrive at the claim.


[Proof of Theorem <ref>]
The theorem is proved by invoking Lemmas <ref> and <ref>, as follows:

    H(θ) S(θ)    <  V^2(θ) + ϕ^2(1-ϕ) (1-2ϕ) log^3(1-ϕ/ϕ)
       < V^2(θ) + V(θ) H(θ)
        <V^2(θ) + 2V(θ) H(θ),

and hence θ satisfies the SEC.





For any θ∈Θ_2, we have

    H(θ) S(θ) <  V^2(θ) + ϕ^2(1-ϕ) (1-2ϕ) log^3(1-ϕ/ϕ),

where ϕ := min{θ_1, θ_2}.



Let ϕ = min{θ_1, θ_2}.
First note that by Lemma <ref>, we have

    H(θ)<ϕlog1/ϕ  + ϕ.

Hence,

    H(θ ) S(θ)    <ϕ^2(1-ϕ)(1-2ϕ) log^3 (1-ϕ/ϕ)
       + ϕ^2(1-ϕ)(1-2ϕ) log^3 (1-ϕ/θ) log(1/ϕ)
       <ϕ^2(1-ϕ)(1-2ϕ) log^3 (1-ϕ/ϕ)
       + ϕ^2(1-ϕ)^2 log^4 (1-ϕ/ϕ),

where (<ref>) follows from Lemma <ref>, completing the proof.



For any θ∈Θ_2, we have 

    H(θ)V(θ)>ϕ^2(1-ϕ) (1-2ϕ) log^3(1-ϕ/ϕ),

where ϕ: = min{θ_1, θ_2}.



For ϕ = min{θ_1, θ_2}, note that 

    H(θ) > ϕlog1/ϕ,

and hence

    H(θ) V(θ)    > ϕ^2 (1-ϕ) log^2(1-ϕ/ϕ) log(1/ϕ)
        >ϕ^2(1-ϕ) (1-2ϕ) log^3(1-ϕ/ϕ),

where (<ref>) follows from Lemma <ref>, completing the proof.



For any 0<x<1, we have

    (1-x) log1/1-x <x.




Note that as x→ 0 both sides are equal and the limit of their derivatives are equal as well, while the second derivative of the left hand side is equal to - 1/1-x <0 completing the proof.




For any 0<x<1/2, we have

    (1-2x) log1/x <(1-x) log1-x/x .




The proof is similar to that of Lemma <ref>.



[Proof of Theorem <ref>]
We proceed with the proof by construction.
Let θ be such that 

    θ_i = {[   (1-ϵ)/(|X|-1) 1 ≤ i ≤ |X| - 1;               ϵ         i = |X| ]..

Then, invoking Lemma <ref>, we can see that as ϵ→ 0, for sufficiently small ϵ and |X|>2, we have

    1/2log (|X|-1) <    H(θ) <2 log (|X|-1),
    1/2ϵ(log1/ϵ)^2 <   V(θ) <ϵ(log1/ϵ)^2,
    1/2ϵ(log1/ϵ)^3 <   S(θ) <ϵ(log1/ϵ)^3.

Hence, 

    S(θ)H(θ)   > 1/4ϵ(log1/ϵ)^3  log (|X|-1) 
        >ϵ^2 (log1/ϵ)^4+ 4ϵ(log1/ϵ)^2log (|X|-1) 
       > V^2(θ) + 2H(θ) V(θ).

where (<ref>) holds for sufficiently small ϵ as long as |X|>2. Thus, θ does not satisfy the SEC, and the proof is complete.




Let θ∈Θ_|X| be such that 

    θ_i = {[   (1-ϵ)/(|X|-1) 1 ≤ i ≤ |X| - 1;               ϵ         i = |X| ]..

Then,

    H(θ)    =  (1-ϵ) log (|X|-1) + h(ϵ),
    
    V(θ)     = ϵ (1-ϵ) (log( 1-ϵ/ϵ)  - log (|X|-1))^2,
    
    S(θ)     = ϵ(1-ϵ)(1-2ϵ) (log( 1-ϵ/ϵ)  - log (|X|-1) )^3,

where h(ϵ) is the binary entropy function given by

    h(ϵ): = H(ϵ, 1-ϵ) = ϵlog1/ϵ + (1-ϵ) log1/1-ϵ.



The calculation of H(θ) is straightforward by noting that this is a mixture of two uniform sources on alphabets of size (|X|-1) and 1. To calculate V(θ), we have

    V(θ)    =(1-ϵ) ( log|X|-1/1-ϵ  - (1-ϵ)log (|X|-1) -  h(ϵ))^2
       + ϵ( log1/ϵ -  (1-ϵ)log (|X|-1) -  h(ϵ) )^2
       =(1-ϵ) ( ϵlog (|X|-1) + ϵlogϵ/1-ϵ)^2
       + ϵ( -(1-ϵ)  log (|X|-1) +(1- ϵ) log1-ϵ/ϵ)^2
        = ϵ (1-ϵ) (  log1-ϵ/ϵ - log (|X|-1) )^2.

Finally, to calculate S(θ), similarly to the calculations for V(θ), we get

    S(θ)     =(1-ϵ) ( ϵlog (|X|-1) + ϵlogϵ/1-ϵ)^3
       + ϵ( -(1-ϵ)  log (|X|-1) +(1- ϵ) log1-ϵ/ϵ)^3
        = ϵ (1-ϵ)(1-2ϵ) (  log1-ϵ/ϵ - log (|X|-1) )^3,

establishing the claim.


[Proof of Theorem <ref>]
Let X be drawn from θ. Further, let  
    Y = log1/P(X) - H(X).
 Hence, by definition, E[Y^3] = S(θ) and E[Y^2] = V(θ).
Then, the condition in (<ref>) would ensure that Y ∈ [-2,2]. Noting that the uniform distribution is excluded in Θ_|X|, and hence the varentropy is nonzero, we apply Lemma <ref> (with a =2) to obtain that

    S(θ)<2V(θ).

This is a sufficient condition for the SEC to hold, completing the proof.


Let Y be a random variable supported on [-a,a] for some a >0 Further, let E[Y] = 0 and E[ Y^2]> 0. Then, 

    E [Y^3]/E [Y^2]≤ a.




It is straightforward to show that E [Y^3]/E [Y^2] is maximized if 

    p_y(y) = {[  ρ/ 2, y = -a;   1-ρ,  y = 0;   ρ/2,  y = a ].,

for some ρ>0, which in turn leads to E [Y^3]/E [Y^2] = a.



[Proof of Corollary <ref>]
First we show that the condition in (<ref>) leads to the condition in (<ref>), which follows from the following set of inequalities:

    max_i ∈ [|X|]|log1/θ_i - H(θ)|    ≤max_i ∈ [|X|]|log1/θ_i - log |X|| 
        + |log|X|- H(θ)| 
       ≤ 2max_i ∈ [|X|]|log1/θ_i - log |X||
        = 2,

where (<ref>) follows Jensen's inequality and the convexity of the |·| operator, and (<ref>) is a direct result of (<ref>). Hence, the claim of Lemma <ref> holds, which results in the claim of the theorem.
















IEEEtran




