A Characterization of Guesswork on Swiftly Tilting Curves
Ahmad Beirami Robert Calderbank Mark Christiansen Ken Duffy Muriel Médard
cs.IT math.IT

empty









A Characterization of Guesswork on
Swiftly Tilting Curves
    
	Ahmad Beirami,
	Robert Calderbank,
	Mark Christiansen,
	Ken Duffy,
	and Muriel Médard 
	
	

This work was presented in part in the 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton 2015) <cit.>.


This work was supported in part by the Air Force Office of Scientific Reseah (AFOSR) under awards FA 9550-14-1-043 and FA 9550-13-1-0076;  the work of K. Duffy and M. Médard  was also supported in part by Netapp through a Faculty Fellowship. 

A. Beirami was with the Department of Electrical and Computer Engineering, Duke University, Durham, NC, USA, and also with the Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MA, USA. He is currently with EA Digital Platform – Data & AI, Electronic Arts, Redwood City, CA, USA (email: ahmad.beirami@gmail.com).

R. Calderbank is with the Department of Electrical and Computer Engineering, Duke University, Durham, NC, USA (email: robert.calderbank@duke.edu).

M. Christiansen was with the Hamilton Institute, Maynooth University, Ireland. He is currently with Grand Thornton (email: markchristiansen4224@gmail.com).

K. Duffy is with the Hamilton Institute, Maynooth University, Ireland (email: ken.duffy@mu.ie).

M. Médard is with the Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MA, USA (email: medard@mit.edu).



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





Given a collection of strings, each with an associated probability of occurrence, the guesswork of each of them is their position in a list ordered from most likely to least likely, breaking ties arbitrarily.
Guesswork is central to several applications in information theory:
Average guesswork provides a lower bound on the expected computational cost of a sequential decoder to  decode successfully the transmitted message; the complementary cumulative distribution function of guesswork gives the error probability in list decoding; the logarithm of guesswork is the number of bits needed in optimal lossless one-to-one source coding; and guesswork is the number of trials required of an adversary to breach a password protected system in a brute-force attack.
In this paper, we consider memoryless string-sources 
that generate strings consisting of i.i.d. characters drawn from a finite alphabet,
and characterize their corresponding guesswork. Our main tool is the tilt operation on a memoryless string-source. We show that the tilt operation on a memoryless string-source parametrizes an exponential family of memoryless string-sources, which we refer to as the tilted family of the string-source.
We provide an operational meaning to the tilted families by proving that 
two memoryless string-sources result in the same guesswork on all strings of all lengths if and only if  their respective categorical distributions belong to the same tilted family.
Establishing some general properties of the tilt operation, we generalize the notions of weakly typical set and asymptotic equipartition property to tilted weakly typical sets of different orders. We use this new definition to characterize the large deviations for all atypical strings and characterize the volume of weakly typical sets of different orders. We subsequently build on this characterization to prove large deviation bounds on guesswork and provide an accurate approximation of its probability mass function. 



Tilting; Ordering; Guesswork; One-to-One Codes; Rényi Entropy; Information Geometry; Weakly Typical Set.





§ INTRODUCTION




 §.§ Motivation



An early motivation for the study of guesswork is to provide lower bounds on the computational complexity of sequential decoding <cit.> where the decoder sequentially examines several paths until it finds the correct coded sequence.
Guesswork was first studied by Massey <cit.>, who showed that average guesswork is lower bounded in terms of the Shannon entropy of the source.  Arıkan <cit.> considered guesswork on memoryless sources and proved that the moments of guesswork are related to the Rényi entropy rates of the source in the  limit as the strings become long.
 This has been generalized to ergodic Markov chains <cit.>  and a wide range of stationary sources <cit.>. 
 
 Recently, tighter non-asymptotic bounds on the moments of guesswork were reported in <cit.>.
Guesswork has also been studied subject to an allowable distortion <cit.>, and subject to constrained Shannon entropy <cit.>. 
Hanawal and Sundaresan <cit.> rederived the moments of guesswork assuming that the logarithm of guesswork satisfies a large deviations principle (LDP). 
Christiansen and Duffy <cit.> established that guesswork satisfies a LDP and characterized the rate function. They also provided an approximation to the distribution of guesswork using the rate function associated with the LDP.
That LDP for guesswork was subsequently leveraged to provide a new proof of the classical Channel Coding Theorem and to 
analyze the performance of a novel, universal maximum likelihood decoding algorithm <cit.>.


In list decoding, rather than declaring one codeword message, the decoder returns a list of size L of possible codewords <cit.>. The error event in list decoding is the event where the message codeword is not returned in the list of the L returned codewords. For  strings of fixed length, as the size of the list grows larger, the probability of error decreases.
The list decoder can be used as an inner code for an outer code that eventually decides the intended message from the returned list of messages by the inner list decoder. The optimal list decoder returns the L most likely messages given the received codeword. Therefore, the probability of the error event in the optimal list decoder is characterized by the complementary cumulative distribution function of guesswork conditioned on the received codeword (see <cit.>). 


Guesswork can also be used to quantify computational security against brute-force attack <cit.>.
Suppose that a secret string is drawn from a given process on a finite alphabet, and is used to secure a password-protected system. Further suppose that the system only grants access if the correct secret string is provided exactly, and does not reveal any information otherwise. If a brute-force attacker adversary decides to guess the secret string by query, the best strategy at an adversary's disposal  is to query the possible secret strings from the most likely to the least likely (in terms of minimizing the average number of queries or maximizing the probability of success using a finite number of queries). In this case, guesswork gives the number of queries that it would take an attacker to find the secret string using the best strategy.
Christiansen et al. <cit.> studied guesswork over the weakly typical set and proved that the exponent is strictly smaller than that of a uniform set with the same support size; they showed that the average guesswork of a password over an erasure channel does not relate to the average noise in general <cit.>; Christiansen et al.  also considered the setting where an attacker wants to guess one or more out of many secret strings drawn independently from not necessarily identical string-sources <cit.>. Finally, the idea of guesswork has been extended to the setup where the probability distribution is unknown <cit.>. 


In the context of source coding, it is known that the length of the optimal one-to-one source code  (that need not satisfy Kraft's inequality) is within one bit of the logarithm of guesswork. The average length of a one-to-one code is related to the normalized zeroth moment of guesswork or alternatively the expected logarithm of guesswork (see <cit.>). The source coding problem without prefix constraint dates back to Wyner <cit.>, who showed that the average codeword length of one-to-one codes is upper bounded by the entropy. Alon and Orlistky derived a lower bound on the average codeword length in terms of the Shannon entropy <cit.>, which was recently revisited for other moments of  guesswork <cit.>. Szpankowski <cit.> derived the asymptotic average codeword length of one-to-one codes on binary memoryless sources, which was subsequently generalized to finite-alphabet independent and identically distributed (i.i.d.) processes <cit.>, and later studied under a universal setup <cit.>.



 §.§ Problem setup, definitions, and notation

Let  X := (a_1, …, a_|X|) be an ordered set that denotes a finite alphabet of size |X|. We will subsequently use the ordering on X to break ties for equally likely strings in guesswork (and reverse guesswork). Denote an n-string over X by x_k^n+k-1 = x_kx_k+1… x_n+k-1∈X^n. Further, let x^n = x_1^n and for i>n, x_i^n = ∅, where ∅ denotes the null string.
Let μ^n denote a multinomial probability distribution on the sample space X^n, where μ^1 is the corresponding categorical distribution on X, i.e., μ^n(x^n) = ∏_i=1^n μ^1(x_i).

We refer to := {μ^n : n ∈ℕ} as a (memoryless) string-source, also called source.


Let θ= (θ_1, …, θ_|X|) be the parameter vector corresponding to the categorical distribution μ^1. That is 
θ_i : = μ^1(a_i) = P[X = a_i] for all i ∈ [|X|]. 

By definition, θ is an element of the (|X|-1) dimensional simplex of all stochastic vectors of size |X|. Denote Θ_|X| as the |X|-ary probability simplex, i.e.,
Θ_|X| : = {θ∈ℝ_+*^|X| : ∑_i ∈ [|X|]θ_i = 1}.
We typically reserve upper case letters for random variables while  lower case letters correspond to their realizations. For example, X^n denotes an n-string randomly drawn from  while x^n ∈X^n is a realization of the random n-string.

Note that as string lengths become large, the logarithm of the guesswork normalized by string length has been shown
 to satisfy a LDP for a more general set of sources <cit.>. 
 While existing results on guesswork consider the ordering of strings from most likely to least likely, either unconditionally or conditionally (starting at <cit.>), or universal guessing orders <cit.>, the more restrictive assumptions used here enable us to treat, for the first time, the reverse guesswork process. In reverse guessing, strings are ordered from least likely to most likely, breaking ties arbitrarily. At first glance, consideration of the worst possible strategy seems to be of limited value, but we will show that is not the case. 

Forward guesswork provides good estimates of the likelihood of quickly discovered strings, but we shall demonstrate reverse guesswork provides better estimates on the likelihood that large numbers of guesses occur. We also establish an inherent geometrical correspondence between string-sources whose orders are reversed.  Amongst other results, we prove that logarithm of reverse guesswork scaled by string length satisfies a LDP with a concave rate function.  The concavity captures the fact that as one moves along the reverse order the rate of acquisition of probability increases initially.  Due
 to that fact, 
the approach employed in <cit.>, which leveraged earlier results on the scaling behavior of moments of guesswork, has no hope of success and we instead use distinct means.



Let information _^n: X^n →ℝ_+* be defined as:[ℝ_+*:= { x∈ℝ | x>0}.]

    _^n(x^n) := log1/μ^n(x^n).


Note that throughout this paper we use log(·) to denote the natural logarithm and hence  information is measured in nats as defined above.


Let H^n() denote the entropy, which is defined as the expected information of a random n-string, and quantifies the average uncertainty that is revealed when a random n-string drawn from  is observed:


    H^n() := E_{_^n(X^n)}  =∑_x^n∈X^nμ^n(x^n)^n_(x^n),

where E_{·} denotes the expectation operator with respect to the measure . 
The entropy rate, is denoted by H() and is given by
H()  :=  lim_n→∞1/n H^n() = H^1().




For any n∈ℕ, we define [n] := {1,…,n}.




In what follows we put forth two assumptions on the string-source that enable us to prove that the logarithm of reverse guesswork satisfies a LDP. We will also later characterize the set of string-sources that satisfy the assumptions. 

We assume that μ^1(x)>0 for all x ∈X, i.e., θ_i>0 for all i ∈ [|X|].




Define

    ε: = min_x ∈Xμ^1(x) ,
    ε: = max_x ∈Xμ^1(x) .

Assumption <ref> excludes the boundaries of the probability simplex and ensures that the likelihood of the least likely n-string scales exponentially with n. In other words, for all n ∈ℕ, and all x^n ∈X^n

    1/nlog1/μ^n(x^n)≤log1/ε < ∞.


 
We assume that min_x ∈Xμ^1(x) and max_x ∈Xμ^1(x) are unique.


Assumption <ref> ensures that the most likely and the least likely words are unambiguously determined. 

 The probability simplex for a ternary alphabet, Θ_3, is depicted in Fig. <ref>, where the green dashed and green solid lines represent the set of string-sources in Θ_3 that do not satisfy Assumption <ref>. Note that in this case, (|X|-2) = 1 and |X|2  =3 resulting in three 1-dimensional hyperplanes.



We denote by M_X, the set of all memoryless string-sources on alphabet X that satisfy Assumptions <ref> and <ref>.

In this paper, we focus our attention to string-sources in M_X. 



A one-to-one function G^n_:  X^n → [|X|^n] is said to be the optimal ordering for  (on n-strings) if

    μ^n(x^n) > μ^n(y^n) ⇒ G_^n(x^n) < G_^n(y^n),

and further if μ^n(x^n) = μ^n(y^n), then G_^n(x^n)<G_^n(y^n) if and only if x^n appears prior to y^n in lexicographic ordering. 




We define R_^n(x^n) as the reverse guesswork, given by

    R_^n(x^n) := |X|^n - G^n_(x^n)



Note that as defined above, given , guesswork and reverse guesswork are unique functions.
While guesswork corresponds to the best guessing strategy for recovering the string x^n, reverse guesswork corresponds to the worst guessing strategy for the string-source  as it proceeds from the least likely string all the way to the most likely. Hence, the statistical performance of any other guessing strategy (ordering on n-strings) lies somewhere between that of guesswork and reverse guesswork. As will become clear later in the paper, our interest in reverse guesswork is mainly due to its usefulness in characterizing the PMF of guesswork.










We define the logarithm of (forward) guesswork g_^n: X^n → [|X|^n] and the logarithm of reverse guesswork r_^n: X^n → [|X|^n] as

    g_^n(x^n)    := log G^n_(x^n),
    
    r_^n(x^n)    := log R^n_(x^n),

where G^n_ and R^n_ are guesswork and the reverse guesswork defined in (<ref>) and (<ref>), respectively. 




Let the varentropy, denoted by V^n(), be defined as

    V^n()    = _{_^n(X^n)}

where _{·} denotes the variance operator with respect to the measure .
The varentropy rate is denoted by V() and is given by

    V() := lim_n →∞1/n V^n() = V^1().






Denote D^n(||) as the relative entropy, also referred to as the Kullback-Leibler (KL) divergence, between the measures μ^n and ρ^n, given by

    D^n(||) := ∑_x^n∈X^nμ^n(x^n) log(μ^n(x^n)/ρ^n(x^n)) = nD^1(||).




Let the cross entropy, denoted by H^n(||), be defined as

    H^n(||) :=    E_{log(1/ρ^n(X^n))}
    
     =    ∑_x^n∈X^nμ^n(x^n) log(1/ρ^n(x^n)).
    
    
    =      H^n() + D^n(||) 
    
    =     nH^1() + n D^1(||).

Observe that H^n(|| )= H^n() recovers the Shannon entropy.


As a natural generalization of  varentropy and cross entropy, we define cross varentropy in the following definition.

Let the cross varentropy, denoted by V^n(||), be defined as

    V^n(||) :=    _{log(1/ρ^n(X^n))}
    
     =    ∑_x^n∈X^nμ^n(x^n) [log(1/ρ^n(x^n)) - H^n(||) ]^2.

Note that V^n(|| )= V^n() simplifies to the varentropy. Further note that  V^n(||)=  n V^1(||) because of our restriction to i.i.d. string-sources.



An operational interpretation of the cross entropy H^n( || ) arises in prefix-free source coding, where it is known that, ignoring the integer constraints on the codeword length, the length of the codeword for the string x^n that minimizes the average codeword length equals ^n_(x^n) = - logμ^n(x^n). In this case, the resulting average codeword length is given by

    E_{^n_(X^n)} =  E_{log1/μ^n(X^n)} = H^n().

Therefore, if a source code is designed for the mismatched string-source , the length of the codeword for x^n would be chosen to be _^n(x^n). Hence, the average codeword length of the optimal prefix-free source code that is designed to minimize the average codeword length under the (mismatched) distribution  is equal to the cross entropy:

    E_{^n_(X^n)} = E_{log1/ρ^n(X^n)} = H^n(||).



For any distribution μ^n, let the Rényi entropy of order α, denoted by H^n_α(·), be defined as <cit.>

    H^n_α() := 1/1-αlog(∑_x^n ∈X^n [μ^n(x^n)]^α).

Further, define the Rényi entropy rate of order α (if it exists) as

    H_α() := lim_n →∞1/nH^n_α() = H^1_α().

Note that lim_α→ 1H_α() = H(), which recovers the Shannon entropy.








 §.§ The tilt


The primary objective of this paper is to develop a tool, called the tilt, for the characterization of guesswork, its moments, and its large deviations behavior.
The tilt operation T on any string-source  is formally defined below.

Let the map T operate on a string-source  and a real-valued parameter α∈ℝ and output a string-source called “tilted  of order α”, which is denoted by T(, α) and is defined as

    T(, α ) := { T(μ^n, α) : n ∈ℕ},

where T(μ^n, α) with overloading the notation
for all n ∈ℕ and all x^n∈X^n is defined as

    T(μ^n, α) (x^n) : = [μ^n(x^n)]^α/∑_y^n ∈X^n [μ^n(y^n)]^α.


Note that the tilt is a real analytic function of α in ℝ for all ∈M_X and all n ∈ℕ, formally stated in Lemma <ref>.
Tilted  of order 1 is the string-source  itself, i.e., T(,1) =. Further, for any ∈M_X, T(, 0) = u_X, where u_X is defined as the uniform string-source on alphabet X such that for all x^n ∈X^n

    u_X^n(x^n) := 1/|X|^n.

Notice that by definition u_X∉M_X.




Observe that  for all n ∈ℕ, T(μ^n, α) is a multinomial distribution with the corresponding categorical distribution given by τ(θ,α) = (τ_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

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

Observe that Γ^+_θ∈Θ_|X| is a set 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., Γ^+_θ.


We define the reverse of the string-source  (also called -reverse), denoted by T ( , -1).

Note that the guesswork corresponding to -reverse is exactly the reverse guesswork. 
As an example, the reverse of a binary memoryless string-source with parameter vector θ = (p, 1-p) is a binary memoryless string-source with τ(θ, -1) = (1-p, p). Observe that R_^n is the optimal ordering (guesswork) for the reverse string source T ( , -1). Further, G_^n is the reverse ordering for T ( , -1).



Let the set T^+ _ denote the tilted family of the string-source , and be given by

    T^+ _:= {  T(,α) : α∈ℝ_+*}.

Further, define the reverse family of the string-source as

    T_^-:={ T( , α): α∈ℝ_-*}.




The first notable property of the tilted family of  is that it parametrizes a standard exponential family of string-sources with α. In other words, for any n ∈ℕ, the family of distributions {T( μ^n, α): α∈ℝ} parametrized by α characterizes an exponential family of distributions on X^n.







As a working example throughout the paper, we consider a memoryless string-source on a ternary alphabet (|X| = 3) with the parameter vector θ = (0.2, 0.3, 0.5). The ternary alphabet is general enough to encompass the difficulties of the problem while simple enough for us to demonstrate the geometric techniques developed in this paper.
The ternary probability simplex is depicted in Fig. <ref>, where the tilted family 
Γ^+_θ is plotted for θ = (0.2, 0.3, 0.5). As can be seen, the tilted family of θ is a parametric curve that is contained within the 2-dimensional simplex of stochastic vectors. 
The curve starts arbitrarily close to the maximum entropy uniform parameter vector θ^0 (for α = 0^+) and then moves towards one of the zero-entropy corner points of the simplex corresponding to the most likely symbol as α→∞.
We shall show that these properties hold generally for all string-sources in M_X.

As a final note, the tilt is intimately related to the  concept of information geometry (see <cit.>), where several geometric properties of the Kullback-Leibler divergence (relative entropy) have been studied and their relevance to problems in information theory have been investigated. In particular, Borade and Zheng applied concepts from information geometry to the analysis of error exponents <cit.>; and Huang et al. performed a geometric study of hypothesis testing <cit.>.
This work also builds upon the insights on the geometry of the probability simplex in the context of information theory and statistics pioneered by Barron, Clarke, and Cover <cit.>. 
The preliminary version of this work relied on the method of types (see <cit.>) while in this paper we build on a  generalized notion of the weakly typical set, called the tilted weakly typical sets. We believe that the current treatment may be generalized to a  class of stationary ergodic string-sources as discussed in the concluding remarks.
 












 §.§ Organization and contribution


In Section <ref>, we provide the main properties of the tilt operation. In particular, we characterize the entropy H^n(T(, α)), the cross entropy H^n(T(, α)||), the relative entropy D^n(T(, α)||) of the tilited string-source as well as the Rényi entropy H_α^n(). These quantities are used in Section <ref> to implicitly characterize the large deviations rate function of the logarithm of reverse guesswork, the logarithm of (forward) guesswork, and information. We further show that the derivatives (with respect to the parameter α) of these quantities can be expressed in terms of the varentropy V^n(T(, α)) and the  cross varentropy V^n(T(, α)||) of the tilted string-source.

 In Section <ref>, we define the equivalent order class of a string-source as the set of all string-sources that result in the same guesswork for all n, and denote this set of string-sources by C_. In Theorem <ref>, we show that
the equivalent order class of  is equal to the tilted family, i.e.,  C_ = T^+_, providing an operational meaning to the tilted family.
Further, the set of all string-sources whose optimal orderings are inverse for  is equal to T^-_, i.e., C_T ( , -1) = T^-_.
This result draws an important distinction between information and guesswork. The string-source  is uniquely determined if information ^n_(x^n) is provided for all x^n ∈X^n. On the other hand, it is not possible to  recover uniquely the string-source  if one is provided with the guesswork G_^n(x^n) for all strings x^n ∈X^n. Our result shows that one can only determine the string-source up to equivalence within the tilted family that the source belongs to given the guesswork for all x^n ∈X^n leading to one less degree of freedom. This result has implications in terms of universal source coding <cit.> and universal guesswork <cit.>, where the degree of freedom in the model class determines the penalty of universality, which is called redundancy in source coding.
  


In Section <ref>, we generalize the notion of the weakly typical set. The weakly typical set comprises of all strings x^n ∈X^n such that e^-H^n() - n ϵ<μ^n(x^n) < e^-H^n() + n ϵ. An important implication of the weakly typical set (known as the asymptotic equipartition property) is that the typical set roughly contains ≈ e^H^n() strings each of probability  ≈ e^-H^n(). 
For sufficiently large n, the probability of the typical set is close to one, i.e., if a string is randomly drawn from the source it is in the weakly typical set with high probability. The weakly typical set is used to prove key results in information theory that are dominated by the typical events, such as the source coding theorem, and the channel coding theorem. Despite the great intuition that typicality provides on such quantities, the arguments based on typicality fall short in providing intuition on other key quantities that are dominated by atypical events, such as the error exponents in decoding, and the cut-off rate in sequential decoding. 
In Section <ref>, we consider all strings x^n ∈X^n such that e^-H^n(T(, α)||) - n ϵ<μ^n(x^n) < e^-H^n(T(, α)||) + n ϵ for α∈ℝ, which we define as the tilted weakly typical set of order α and denote by A^n_,α,ϵ (see Definition <ref>). We show that for a fixed ϵ, for any string x^n ∈X^n, there exists an α such that x^n is contained in the tilted weakly typical set of order α. Hence, this notion could be used to cluster/partition all of the strings x^n ∈X^n based on their likelihoods.
In Theorem <ref>, we derive tight bounds on the probability, size, guesswork, and reverse guesswork for all elements of the tilted weakly typical set of any order α.
Roughly speaking, for any α∈ℝ_+*, we show that A^n_,α,ϵ contains ≈ e^H^n(T(, α)) strings where the likelihood of each string is ≈ e^-H^n(T(, α)||), and the probability of the entire set is ≈ e^-D^n(T(, α)||), and the guesswork for each element in the set is ≈ e^H^n(T(, α)).
For any α∈ℝ_-*, we show that A^n_,α,ϵ contains ≈ e^H^n(T(, α)) strings where the likelihood of each string is ≈ e^-H^n(T(, α)||), and the probability of the entire set is ≈ e^-D^n(T(, α)||), and the “reverse” guesswork for each element in the set is ≈ e^H^n(T(, α)).
 Note that α =1 recovers the weakly typical set as H^n(T(, 1)||) = H^n(T(, 1)) = H^n(), and for α≠ 1, this provides a generalization of the well-known  weakly typical set.
This generalization could be used to provide new insights on understanding and proving results on information theoretic quantities that are dominated by atypical events.


In Section <ref>, we prove that the logarithm of reverse guesswork r_^n(x^n), the logarithm of (forward) guesswork  g_^n(x^n), and information _^n(x^n) satisfy a LDP and provide an implicit formula for the rate function in each case based on entropy, cross entropy, and relative entropy. Although some of the results in this section have been previously proved in more generality, we believe that the machinery built upon the tilt operation in this paper as well as the information theoretic characterization of the rate functions provide useful intuition in characterizing the large deviations behavior of these quantities. In particular, the LDP for the logarithm of reverse guesswork could not have been established using the previous methods by Christiansen and Duffy <cit.>, as the resulting rate function here is concave. 
The most common way to prove a LDP is the Gärtner-Ellis Theorem <cit.>. There, one first determines the scaled cumulant generating function of the process of interest, which identifies how moments scale, and then leverages properties of it to establish the LDP. This approach can only work if the resulting rate function is convex. Here, that is not the case.



In Section <ref>, we provide an approximation on the distribution of guesswork that captures the behavior even for small string lengths. The approximation is built based on the tilt operation, guesswork, and reverse guesswork. We empirically show that the approximation can be applied to a variety of string-sources to characterize the PMF of guesswork.

Finally, the conclusion is provided in Section <ref>, where we also present ideas on how to generalize these results beyond the setting considered in this paper.












§ PROPERTIES OF THE TILTED STRING-SOURCES


In this section, we provide the main properties of the tilt operation that shall be used in proving our results on the characterization of guesswork. This section may be skipped by the reader and only referred to whenever a particular lemma is needed.



For any α, β∈ℝ,

    T(T(, α), β) =  T(T(, β), α) = T(, αβ).




This is obtained from the definition using algebraic manipulation.




The optimal ordering for  is the reverse ordering for T ( , -1) and the reverse ordering for  is the optimal ordering for T ( , -1).



The statement is a consequence of the definition.



For any ∈M_X,

    lim_α→∞ H(T( , α)) = 0,
        lim_α→ -∞ H(T( , α)) = 0.



The Lemma is a direct consequence of Assumption <ref>.


Next, we provide a lemma that relates Rényi entropy, Shannon entropy, relative entropy, and cross entropy.

For any ∈M_X, and any α∈ℝ, the following relations hold:

    H^n(T(, α)||)  - H^n_α()   = 1/1-α D^n(T(, α)||),


    H^n(T(, α)) - H^n_α() = α/1-α D^n(T(, α)||),

where . 1/1-α D^n(T(, α)||)|_α = 1:= 0.




To establish (<ref>), 

    H^n(T(, α)||)  - H^n_α() -1/1-α D^n(T(, α)||) 
    
    =    ∑_x^n ∈X^n T(μ^n, α)(x^n) log1/μ^n(x^n)
       - 1/1-α∑_x^n ∈X^n [μ^n(x^n)]^α
        - 1/1-α∑_x^n ∈X^n T(μ^n, α)(x^n) log([μ^n(x^n)]^α / ∑_y^n ∈X^n [μ^n(y^n)]^α/μ^n(x^n))
       = 0,

where (<ref>) follows from the definition, and (<ref>) holds because the term ∑_y^n ∈X^n [μ^n(y^n)]^α  in (<ref>) is a constant, and hence (<ref>) could be decomposed into two terms one of which cancels the right hand side of (<ref>), and the other cancels (<ref>). Finally, (<ref>) is established by putting together (<ref>) and (<ref>).




For any ∈M_X, and any α∈ℝ, the following holds:

    log1/T(μ^n, α)(x^n) -H^n(T(,α)) 
       =α(
    log1/μ^n(x^n) - H^n(T(,α)||) ).




The lemma is proved by considering the following chain of equations:

    log1/T(μ^n, α)(x^n) -H^n(T(,α))
        = αlog1/μ^n(x^n)  + log(∑_x^n ∈X^n [μ^n(x^n)]^α)
       - ∑_x^n ∈X^n T(μ^n,α)(x^n) ( αlog1/μ^n(x^n)  + log(∑_x^n ∈X^n [μ^n(x^n)]^α) )
        = α(log1/μ^n(x^n) - H^n(T(,α)||)).





For any ∈M_X, and any α∈ℝ, the following holds:

    α ^2 V^n(T(, α) || ) =    V^n(T(, α)).




We have

    α^2 V^n(T(, α) || ) 
        = ∑_x^n∈X^nT(μ^n, α)(x^n) [α(log(1/μ^n(x^n)) - H^n(T(, α)||) )]^2
        = ∑_x^n∈X^nT(μ^n, α)(x^n) [log1/T(μ^n, α)(x^n) -H^n(T(,α)) ]^2
        = V^n(T(, α)),

where (<ref>) follows from Lemma <ref>.





For any string-source ∈M_X, for any n∈ℕ, T( μ^n, α) is a real analytic function of α∈ℝ. In particular, d/dα T( μ^n, α) exists; and  
lim_α→ 0 T( μ^n, α) = u_X^n,
where u_X^n is the uniform distribution on X^n.




The statement follows from the facts that the exponential function is real analytic in its argument and that the denominator in (<ref>) in the definition of the tilt is non-zero for all α∈ℝ.
The limit as α→ 0 holds since μ^n(x^n)>0 for all x^n ∈X^n by Assumption <ref>. 





For any string-source ∈M_X, for any n∈ℕ, H^n(T( , α)), D^n(T( , α)||),  H^n(T( , α)||),  V^n(T( , α)), and V^n(T( , α)||) are continuous and differentiable functions of α∈ℝ.



Note that H^n(), D^n(||), H^n(||), V^n(), and V^n(||) are continuously differentiable with respect to ∈M_X, and by Lemma <ref>, T(, α) is also continuous and differentiable with respect to α∈ℝ , and hence the overall composition by considering = T(, α) is continuous and differentiable with respect to α∈ℝ.




For any ∈M_X, and any n ∈ℕ, and any α∈ℝ:

    d/dα T(μ^n, α)(x^n)
       = T(μ^n, α)(x^n) ( H^n(T(, α)||) -  log1/μ^n(x^n)).




Let 

    T'(μ^n , α_0)(x^n) := . d/dαT(μ^n, α)(x^n)|_α = α_0.

Note that by Lemma <ref>, we know that for any β >0:

    T(μ^n, α)(x^n) = T(T(μ^n, β), α/β)(x^n).

Differentiating both sides with respect to α, for all α_0, β>0 we  have

    . d/dαT(μ^n, α)(x^n)|_α = α_0   = T'(μ^n , α_0)(x^n)
       = . d/dαT(T(μ^n, β), α/β)(x^n)|_α = α_0
       = 1/β T'(T(μ^n, β), α_0/β)(x^n)
        =1/α_0 T'(T(μ^n, α_0), 1)(x^n)  ,

where (<ref>) follows by setting β = α_0. In other words, (<ref>) implies that the derivative of a tilt with respect to α can be derived by taking the derivative at α =1 and rescaling the derivative evaluated at the tilted distribution.
Consequently, to prove the lemma it suffices to prove that

    . d/dα T(μ^n, α)(x^n)|_α = 1 = μ^n(x^n) (  H^n() - log1/μ^n(x^n)),

and then it follows from (<ref>) that for any α≠ 0, we will arrive at the following:

    d/dα T(μ^n, α)(x^n)
       =  1/αT(μ^n, α)(x^n) ( H^n(T(, α)) -  log1/T(μ^n, α)(x^n)).

On the other hand, the desired result is obtained by considering Lemma <ref>, and noting the continuity and differentiability of T(μ^n, α) at 0 from Lemma <ref> and that of H(T(μ^n, α)) at 0 from Lemma <ref>.

To establish (<ref>), note the definition of the tilt in (<ref>) and the fact that the derivative of the numerator with respect to α is [μ^n(x^n)]^αlogμ^n(x^n) and the derivative of the denominator with respect to α is -H^n().



For any ∈M_X, we have

    lim_α→ 01/α^2 V^n(T(, α))=  V^n( u_X|| ).




Observe that

    lim_α→ 01/α^2 V^n(T(, α))    = lim_α→ 0 V^n(T(, α)||) 
        = V^n(u_X || ),

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








For any ∈M_X, and any α∈ℝ,

    d /d αH^n(T( , α)) = -α V^n(T( , α)||).




First, owing to Lemma <ref>, the derivative of H^n(T( μ^n, α)) with respect to α exists.

To prove the result for all α≠ 0, it suffices to show that 

    .d /d αH^n(T( , α))|_α=1 = - V^n()

for any given ∈M_X. Then, by Lemma <ref>, T(·, α +dα) = T(T(·, 1+ dα/α), α) which for α≠ 0 leads to (see (<ref>) in the proof of Lemma <ref> for a more formal statement of this part of the claim):

    d /d αH^n(T( , α)) = -1/α V^n(T( , α)).

This, in conjunction with Lemma <ref> and continuity and differentiability of H^n(T( , α)) with respect to all α∈ℝ from Lemma <ref> leads to the desired result.



To show that (<ref>) holds, we have

    .d /d αH^n(T( , α))|_α = 1
    
       = ∑_x^n∈X^n.d/dα  T( μ^n, α)(x^n) |_α=1log1/μ^n(x^n)
             + ∑_x^n∈X^nμ^n(x^n)  .d/dαlog1/ T( μ^n, α)(x^n)|_α=1
        = ∑_x^n ∈X^nμ^n(x^n)(H^n() - log1/μ^n(x^n)) log1/μ^n(x^n)
            + ∑_x^n ∈X^nμ^n(x^n) (log1/μ^n(x^n)  - H^n() ) 
        = E_{(H^n() -log1/μ^n(X^n)) log1/μ^n(X^n)}
        = -_{_^n(X^n)}= - V^n(),

where (<ref>) follows from Lemma <ref>, and (<ref>) follows from the definition of the varentropy in (<ref>). The limit as α→ 0 also follow from Lemma <ref>.



For any ∈M_X and  any α∈ℝ,

    d /d αH^n(T( , α)|| ) = - V^n(T(, α)||).




We have

    .d /d αH^n(T( , α)||).
       = ∑_x^n∈X^n.d/dα  T( μ^n, α)(x^n) . log1/μ^n(x^n)
        = ∑_x^n ∈X^nT(μ^n, α)(x^n) (H^n(T(, α)||) -log1/μ^n(x^n)) log1/μ^n(x^n)
        =  E_T(, α){(H^n(T(, α)||) -log1/μ^n(X^n)) log1/μ^n(X^n)}
        = - _T( , α){_^n(X^n)}
       = -V^n(T(, α)||),

where (<ref>) follows from Lemma <ref>, and (<ref>) follows from the definition of information in (<ref>) and cross entropy in (<ref>) leading to the fact that

    E_T(, α){log1/μ^n(X^n)}  = H^n(T(, α)||).









For any ∈M_X and  any α∈ℝ,

    d /d αD^n(T( , α)|| ) = (α-1)V^n(T( , α)||).




Note that  from (<ref>),

    D^n(T( , α)|| ) = H^n(T( , α)|| ) - H^n(T( , α)).

The lemma then follows by differentiating both sides with respect to α and applying Lemmas <ref> and <ref> on the right hand side.




For any ∈M_X and  any α≠1,

    d /d αH_α^n() = - 1/(1-α)^2D^n(T(, α)|| ),

and 

    . d /d αH_α^n() |_α = 1 = - 1/2 V^n().




To establish (<ref>), consider:

    d/dαH^n_α()    = d/dαH^n(T(, α)|| ) - d/dα(1/1-α D^n(T(, α)|| ))
        = - 1/α^2V^n(T(, α)) + 1/α^2V^n(T(, α))
        -  1/(1-α)^2D^n(T(, α)|| )
        =- 1/(1-α)^2D^n(T(, α)|| ),

where (<ref>) follows by invoking (<ref>) in Lemma <ref>, and (<ref>) follows from the chain rule of derivatives.

To establish (<ref>), we have

    . d /d αH_α^n() |_α = 1   = lim_α→ 1d /d αH_α^n() 
        = lim_α→ 1-D^n(T(, α)|| )/(1-α)^2
        =  lim_α→ 1 - α -1/α^2 V^n(T( , α))/2 (α - 1)
        = - 1/2 V^n(),

where (<ref>) follows from the continuity of the derivative of H_α^n() with respect to α, (<ref>) follows from (<ref>), and (<ref>) follows from L'Hôpital's rule and Lemma <ref>.
This result recovers the fact that Rényi entropies are monotonically decreasing with respect to the order, and further characterizes their rate of change with respect to the parameterization.




For any ∈M_X,

    lim_n →∞1/n V^n(T(, α)||)     = V(T(, α)||). 
    lim_n →∞1/n H^n(T(, α))    =  H(T(, α)),
    lim_n →∞1/nH^n(T(, α)||)    =  H(T(,α)||) ,
    lim_n →∞1/n D^n(T(, α)||)    =  D(T(,α)||) ,
    lim_n →∞1/n H_α^n()    =  H_α() ,

Further, for all α∈ℝ,

    d/dα H(T(, α))    = -α V(T(, α)||),
    d/dα  H(T(,α)||)      = - V(T(, α)||),
    d/dαD(T(,α)||)     = (α-1)V(T(, α)||).
    d/dαH_α()     = - 1/(1-α)^2D(T(, α)|| ),

where D(T(, α)|| ) is differentiable with respect to α, and .1/(1-α)^2D(T(, α)|| )|_α = 1: = 1/2 V().



The first part of the claim is straightforward as the equalities hold for all n and hence also hold in the limit as n →∞.

The claim in (<ref>) hence follows   
by invoking Lemma <ref>. 
Equations (<ref>) and (<ref>) and (<ref>) are established similarly considering Lemmas <ref>, <ref>, and <ref>, respectively. 





If ∈M_X, then, for all α≠ 0, we have T(,α) ∈M_X.  In other words, M_X is closed under all non-zero tilts, and hence T^+_, T^-_⊆M_X.



We need to show that T(, α) satisfies Assumptions <ref> and <ref>. 

To check Assumption <ref>, for α∈ℝ_+*, we have:

    1/nlog1/T( μ^n, α)(x^n)   = 1/nlog∑_y^n ∈X^n [μ^n(y^n)]^α/[μ^n(x^n)]^α
        =1/n[log∑_y^n ∈X^n [μ^n(y^n)]^α +log1/[μ^n(x^n)]^α].

Further, considering α≥ 1,

    - αlog |X| ≤ (1- α) log |X| ≤1/nlog∑_y^n ∈X^n [μ^n(y^n)]^α≤ 0,

and for all 0<α≤ 1, 

    0 ≤1/nlog∑_y^n ∈X^n [μ^n(y^n)]^α≤ (1-α)  log |X| ≤log |X|.

Thus, for all α∈ℝ_+*, by taking the maximum of the upper bounds and the minimum of the lower bounds in (<ref>) and (<ref>), and applying them to (<ref>), we have

    - αlog |X| + αlog1/ε≤1/nlog1/T(μ^n, α)(x^n)≤log |X|  + αlog1/ε,

where ε and ε are defined in (<ref>) and (<ref>), respectively.
On the other hand, for all α∈ℝ_-*, we have

    1/nlog1/T( μ^n, α)(x^n)    =1/n[log∑_y^n ∈X^n [μ^n(y^n)]^α +log1/[μ^n(x^n)]^α]
       ≤1/nlog∑_y^n ∈X^nε^nα
        = log |X| - αlog1/ε.

Thus, for all α∈ℝ, we have

    1/nlog1/T(μ^n, α)(x^n)≤log |X| + |α|log1/ε < ∞.


Next, we need to show that for all α≠ 0,

    H(T (, α))>0.

Due to Lemma <ref>, H(T (, α)) is differentiable with respect to α and its derivative is given by α V(T(, α)||). On the other hand, for α > 0, the derivative is strictly positive implying that H(T(, α)) is strictly decreasing with respect to α, and hence it is non-zero for all α>0.
This together with (<ref>) demonstrate that for all α∈ℝ, T(, α) satisfies Assumption <ref>.

To show that Assumption <ref> holds for the tilted source, we note that for any α > 0, we have

    min_x ∈X T(μ^1, α) (x)     = min_x ∈X{(μ^1(x))^α/∑_y ∈X (μ^1(y))^α}
       = min_x ∈X (μ^1(x))^α
       = min_x ∈Xμ^1(x) ,

which is unique by the fact that  satisfies Assumption <ref>. Similarly, we can argue that max_x ∈X T(μ^1, α) (x)  is also unique.
On the other hand, for α<0, we have

    min_x ∈X T(μ^1, α) (x)     = min_x ∈X{(μ^1(x))^α/∑_y ∈X (μ^1(y))^α}
       = min_x ∈X (μ^1(x))^α
       = max_x ∈Xμ^1(x),

which is again unique by the fact that  satisfies Assumption <ref>. Finally, max_x ∈X T(μ^1, α) (x) is unique by the fact that min_x∈Xμ^1(x) is unique completing the proof.








§ EQUIVALENT ORDER CLASS




In this section, we characterize the set of all string-sources  that induce the same optimal ordering of the strings (from the most likely to the least likely) on all strings of all lengths. 


We say two string-sources , ∈M_X are order equivalent and denote by ≡, if for all n ∈ℕ, G_^n = G^n_, i.e., the optimal ordering for  is also the optimal ordering for . 



Note that two string-sources may be order equivalent while they are not necessarily indistinguishable sources. By contrast, if for all n ∈ℕ, μ^n = ρ^n, then the two are indistinguishable, and we write =.



The equivalent order class of a string-source ∈M_X is denoted by C_ and is given by
C_ = {∈M_X:  ≡}.





We also need another definition that generalizes the weakly typical set. 

For any α∈ℝ, denote by A^n_,α,ϵ the tilted weakly typical set of order α with respect to , which is the set of all x^n such that for an ϵ∈ℝ_+*:

    e^-H^n(T(, α)|| ) - n ϵ  < μ^n(x^n) <  e^-H^n(T(, α)|| ) + n ϵ,

where H(·|| ·) is the cross entropy defined in (<ref>).


Note that in the case of α =1, A^n_,1,ϵ is the familiar weakly typical set (see (3.6) in <cit.>); and Definition <ref> generalizes the weakly typical set for α≠ 1.
We shall establish some useful properties of the tilted weakly typical sets in the next section.


Our interest in finding the equivalent order class of a string-source  lies in the fact that such string-sources are subject to the same optimal guessing procedure, which renders them equivalent in terms of many problems, such as brute-force password guessing, list decoding, sequential decoding, and one-to-one source coding.







For any string-source ∈M_X, if ∈C_, then there exists a unique α∈ℝ_+* such that 
= T( , α). Consequently, 
the equivalent order class of  is equal to the tilted family, i.e.,  C_ = T^+_.
Further, the set of all string-sources whose optimal orderings are inverse for  is equal to T^-_, i.e., C_T ( , -1) = T^-_.



Theorem <ref> characterizes the set of all string-sources that would result in the same ordering of strings for any length. As discussed above, these string-sources are called order  equivalent as their optimal guesswork procedure is exactly the same. Theorem <ref> establishes that any such order equivalent string-source is necessarily the result of a tilt providing an operational meaning to the tilted family.





To prove the theorem, we state two intermediate lemmas and a definition.



For any  string-source , the equivalent order class of  contains T^+_, i.e., T^+_⊆C_.



To prove the lemma, we need to show that for any α∈ℝ_+*, we have T (, α) ≡, i.e., T (, α)  ∈C_. To this end, we show that  G^n_ = G^n_T(, α), i.e., G^n_  is also the optimal ordering on n-strings for T(, α).  Thus, we need to show that

    T (μ^n, α)(x^n) < T(μ^n, α )(y^n) ⇒ G^n_(x^n) > G^n_(y^n).

Considering (<ref>), this establishes that G^n_ is the optimal ordering for T(μ^n, α), and hence G^n_ = G^n_T(, α).
It suffices to show that for any α∈ℝ_+*, we have

    μ^n(x^n) > μ^n(y^n) ⇔ T( μ^n, α) (x^n) > T( μ^n, α) (y^n).

We show here that 

    μ^n(x^n) > μ^n(y^n)
       ⇔  [μ^n(x^n)]^α > [μ^n(y^n)]^α
       ⇔[μ^n(x^n)]^α/∑_z^n ∈X^n [μ^n(z^n)]^α > [μ^n(y^n)]^α/∑_z^n ∈X^n [μ^n(z^n)]^α
       ⇔ T( μ^n, α) (x^n) > T( μ^n, α) (y^n),

where (<ref>) holds because α >0, and (<ref>) follows from the definition of the tilt in (<ref>).






Next, we state a simple lemma about the weakly typical set (which is a special case of the tilted weakly typical sets).

For any ∈M_X,

    ℙ_{X^n ∈A^n_,1,ϵ}   ≥ 1 - V^n()/n^2 ϵ^2,
    
    
    |A^n_,1,ϵ |      > e^H^n() - n ϵ(1 - V^n()/n^2 ϵ^2),
    
    |A^n_,1,ϵ |     <  e^H^n() + n ϵ.





    ℙ_{X^n ∈A^n_,1,ϵ}   = ℙ_{|_(X^n)  -H^n()| ≤ n ϵ}
       ≥ 1 - V^n()/n^2 ϵ^2,

where (<ref>) follows from Chebyshev's inequality. Note that Chernoff bounds could be used to establish an exponential decay in (<ref>) but the weaker bound above is sufficient for our purposes.
To derive the lower bound in (<ref>) on the size of the set A_, 1, ϵ, observe that

    |A_, 1, ϵ|    ≥ℙ_{X^n ∈A_, 1, ϵ}/max_x^n ∈A_, 1, ϵ{μ^n(x^n)}
       > 1 - V^n()/n^2 ϵ^2/e^-H^n() +n ϵ
       = (1 - V^n()/n^2 ϵ^2) e^H^n() -n ϵ.

The bound in (<ref>) is established similarly.





Let S_h ⊂M_X denote the Shannon entropy contour h, which is the set of all string-sources in M_X whose entropy rate equals h  ∈ (0,log |X|), i.e., 

    S_h := {∈M_X: H() = h}.






 
Next, we provide the proof of the main result of this section on the equivalent order class of a string-source.
[Proof of Theorem <ref>]
To prove the theorem, we take two steps. 
We first show that one element of the tilted family T_^+ is also contained in the intersection of the Shannon entropy contour and the equivalent order class, i.e., T^+_∩C_∩S_h  ∈M_X is not empty.
We also show that for any  string-source ∈M_X and any h ∈ (0,log |X|), if _1, _2 ∈M_X are in the intersection of S_h (see Definition <ref>) and C_ denoted by 
C_∩S_h,
then _1 and _2 are indistinguishable sources, i.e., _1 = _2.  Putting these two steps together ensures that the intersection C_∩S_h
contains one and only one element, which is a member of the tilted family by Lemma <ref>, and completes the proof. The second part of the  theorem is proved by invoking Lemma <ref> and the first part of the theorem.



We first show that C_∩S_h is not empty and contains one element from T^+_. 
This is carried out by noting the continuity and monotonicity of H(T(, α)) in the parameter α proved in Lemma <ref> and noting that H(u_X) = log |X| and lim_α→∞ H^n(T( , α)) = 0.


Next, we proceed the proof of uniqueness by contradiction.
Let _1, _2 ∈C_∩S_h be two string-sources that are contained in the intersection of S_h and C_. Note that by Definition <ref>, _1, _2 ∈M_X.
Therefore, by definition as _1, _2 ∈S_h, we have 

    H(_1) = H(_2) =h,

where h ∈ (0, log |X|) by Definition <ref>.
The claim is negated to assume that _1 and _2 are not equal, i.e., there exists δ∈ℝ_+* such that for all n ∈ℕ:

    D^n(_2||_1) = E__2{log( ρ_2^n(X^n)/ρ_1^n(X^n))} >2n δ.


Then, we can decompose the expectation over the weakly typical set and the rest of the strings as follows:

    E__2{log( ρ_2^n(X^n)/ρ_1^n(X^n))}    = ∑_x^n ∈A^n__2, 1, ϵρ_2^n(x^n) log( ρ_2^n(x^n)/ρ_1^n(x^n))
       + ∑_x^n ∉A^n__2, 1, ϵρ_2^n(x^n) log( ρ_2^n(x^n)/ρ_1^n(x^n)).

By Assumption <ref> for the string-source _1 ∈M_X, there exists ε such that

    max_x^n ∈X^nlog1/ρ_1^n(x^n)<nlog1/ε.
 
On the other hand, by (<ref>) in Lemma <ref>,

    ∑_x^n ∉A^n__2, 1, ϵρ_2^n(x^n)  ≤V^n(_2)/n^2 ϵ^2,

Putting together (<ref>) and (<ref>), we have

    ∑_x^n ∉A^n__2, 1, ϵρ_2^n(x^n) log( ρ_2^n(x^n)/ρ_1^n(x^n)) 
    ≤∑_x^n ∉A^n__2, 1, ϵρ_2^n(x^n) log( 1/ρ_1^n(x^n))
    ≤V^n(_2)/n ϵ^2log1/ε = V^1(_2)/ϵ^2log1/ε,

leading to the fact that the term in (<ref>) is O_n(1).
Using the above in conjunction with the fact that P_{X^n ∈A^n__2, 1, ϵ}≥ 1 - V^n()/n^2 ϵ^2, 
we conclude that
for sufficiently large n: 

    E__2{.log( ρ_2^n(X^n)/ρ_1^n(X^n))| X^n ∈A^n__2, 1, ϵ}> n δ.

Consequently, there exists y^n ∈A^n__2, 1, ϵ such that 

    log1/ρ_1^n(y^n) > log1/ρ_2^n(y^n) + nδ.

Since  y^n ∈A^n__2, 1, ϵ, by definition, we have

    nh - nϵ≤log1/ρ_2^n(y^n)≤ nh + nϵ,

which in conjunction with (<ref>) leads to

    log1/ρ_1^n(y^n) > log1/ρ_2^n(y^n) + nδ≥ nh-nϵ + nδ.

By swapping _1 and _2 and noting that

    D(_2||_1) = 0 ⇔ D(_1||_2) = 0,

and repeating similar arguments, we could pick a different sequence ŷ^n ∈X^n such that

    log1/ρ_2^n(ŷ^n) >  nh-nϵ+ nδ.

and 

    log1/ρ_1^n(ŷ^n)≤ nh + nϵ.

 Note that the above holds for any ϵ∈ℝ_+*. By choosing ϵ to be small enough (smaller than δ/2) we then ensure that for n sufficiently large, ρ_2^n(y^n)> ρ_2^n(ŷ^n) and hence G^n__2(y^n) < G^n__2(ŷ^n). Similarly,
 we can show that for sufficiently large n, we have ρ_1^n(y^n)< ρ_1^n(ŷ^n), which leads to G__1^n(y^n) > G__1^n(ŷ^n). Therefore, _1 and _2 cannot be order equivalent, which is a contradiction. Hence, 
 it must be true that for any δ∈ℝ_+*, for sufficiently large n:
 
    E__2{log( ρ_2^n(X^n)/ρ_1^n(X^n))} <n δ,

 which directly implies that
D(_1||_2) = D(_2||_1) = 0, and _1 = _2,
i.e., any two string-sources in the intersection of C_ and S_h must be equal, which completes the proof of the uniqueness.






§ TILTED WEAKLY TYPICAL SET



The main result in this section is a generalization of the asymptotic equipartition property on the weakly typical set concerning information and guesswork. We call this generalized notion the tilted weakly typical set and define it in Definition <ref> in the previous section. Although these results resemble the asymptotic equipartition property on the weakly typical set, they are concerned with the large deviations, i.e., atyptical behavior, rather than the typical behavior. We will consequently use these results in establishing the large deviation properties of guesswork and information in the next section.

We need two more definitions before we can provide the statement of the main result in this section.

For any ∈M_X, let B^n_,α ,ϵ⊂A^n_,α,ϵ be a subset such that |B^n_,α,ϵ| = ⌊1/2|A^n_,α,ϵ|⌋ and for any x^n ∈B^n_,α,ϵ and y^n ∈A^n_,α,ϵ∩B^n_,α,ϵ we have T(μ^n, α)(x^n) < T(μ^n, α)(y^n).




For any ∈M_X, let D^n_,α,ϵ⊇A^n_,α,ϵ be defined as follows:

    D^n_, α, ϵ := { x^n ∈X^n : T(μ^n, α)(x^n) >  e^- H^n(T(, α)) - n |α |ϵ}.








For any ∈M_X, let E^n_,α,ϵ⊇A^n_,α,ϵ be defined as follows:

    E^n_, α, ϵ := { x^n ∈X^n : T(μ^n, α) (x^n) <  e^- H^n(T(, α) ) + n |α| ϵ}.









For any ∈M_X, any ϵ∈ℝ_+*, and any α≠ 0, 
 

(a) For any x^n ∈A^n_,α,ϵ, 

    μ^n(x^n)    >e^-H^n(T( , α)|| )-n ϵ,
    μ^n(x^n)    < e^-H^n(T( , α)|| )+n ϵ;




(b) For any n ∈ℕ,

    | A^n_,α,ϵ|   >(1 - V^n(T(, α)||)/n^2 ϵ^2)  e^H^n(T( , α)) - |α|n ϵ ,
    
    | A^n_,α,ϵ|    < e^H^n(T( , α)) + |α|n ϵ;



(c) For any n ∈ℕ, and α∈ (-∞, 0) ∪ [1,∞),

    ℙ_{X^n ∈D^n_,α,ϵ}   ≥ℙ_{X^n ∈A^n_,α,ϵ}
    
     >  (1 - V^n(T(, α)||)/n^2 ϵ^2)    e^-D^n(T(, α)||) - |1-α| n ϵ ,
    ℙ_{X^n ∈A^n_,α,ϵ}   ≤ℙ_{X^n ∈D^n_,α,ϵ}
       ≤ e^-D^n(T(, α)||) + |1-α| n ϵ ,
    
    ℙ_{X^n  ∈E^n_,α,ϵ}   ≥  1- e^-D^n(T(, α)||) + |1-α| n ϵ ;


(d) For any n ∈ℕ, and α∈ (0,1],

    ℙ_{X^n ∈E^n_,α,ϵ}   ≥ℙ_{X^n ∈A^n_,α,ϵ}
    
     >  (1 - V^n(T(, α)||)/n^2 ϵ^2)   e^-D^n(T(, α)||) - |1-α| n ϵ ,
    ℙ_{X^n ∈A^n_,α,ϵ}   ≤ℙ_{X^n ∈E^n_,α,ϵ}
       ≤ e^-D^n(T(, α)||) + |1-α| n ϵ,
    
    ℙ_{X^n  ∈D^n_,α,ϵ}   ≥  1-e^-D^n(T(, α)||) + |1-α| n ϵ ;




(e) For any n ∈ℕ and any α>0:

    x^n ∈B^n_,α,ϵ     ⇒
    
     G_^n(x^n)    > 1/2(1 - V^n(T(, α)||)/n^2 ϵ^2) e^H^n(T(, α)) -α n ϵ,
    
    x^n ∈D^n_,α,ϵ     ⇒   G_^n(x^n) ≤  e^H^n(T(, α)) + α nϵ,
    
    x^n ∈D^n_,α,ϵ     ⇐
    
    G_^n(x^n)    ≤(1 - V^n(T(, α)||)/n^2 ϵ^2) e^H^n(T(, α)) -α n ϵ,
    
    x^n ∈E^n_,α,ϵ     ⇐   G_^n(x^n) > e^H^n(T(, α)) +α n ϵ.


(f) For any n ∈ℕ and any α<0:

    x^n ∈B^n_,α,ϵ     ⇒
    
     R_^n(x^n)     > 1/2(1 - V^n(T(, α)||)/n^2 ϵ^2) e^H^n(T(, α)) -|α| n ϵ,
    
    x^n ∈D^n_,α,ϵ     ⇒   R_^n(x^n) ≤  e^H^n(T(, α)) + |α| nϵ,
    
    x^n ∈D^n_,α,ϵ     ⇐
    
     R_^n(x^n)    ≤(1 - V^n(T(, α)||)/n^2 ϵ^2) e^H^n(T(, α)) -|α| n ϵ,
    
    x^n ∈E^n_,α,ϵ     ⇐   R_^n(x^n) > e^H^n(T(, α)) +|α| n ϵ.






Recall that Shannon entropy, cross entropy, and relative entropy are measured in nats throughout this paper.
We first provide a few lemmas that specialize to the typical set, which we use to prove the theorem.

For any ∈M_X, let x^n ∈B^n_,1,ϵ (see Definition <ref>). Then, 

    G_^n(x^n)    > 1/2(1 - V^n()/n^2 ϵ^2) e^H^n() -n ϵ.




Note that by definition for all x^n ∈B^n_, 1, ϵ, we have G_^n(x^n) > |B^n_, 1, ϵ|≥1/2  |A^n_,1,ϵ|. The proof is completed noticing the bound in (<ref>).




For any ∈M_X, let x^n ∈D^n_, 1, ϵ (see Definition <ref>). Then, 

    G_^n(x^n)    ≤  e^H^n() + nϵ.




We have

    G_^n(x^n)    ≤ |D^n_, 1, ϵ|
       ≤1/min_x^n ∈D^n_, 1, ϵ{μ^n(x^n)}
       = e^H^n( ) + n ϵ,

where (<ref>) follows from the definition in (<ref>), (<ref>) follows from the fact that the probability of the set D^n_, 1, ϵ is upper bounded by 1, and (<ref>) again follows from the definition in (<ref>).



Suppose the following holds:

    G_^n(x^n) ≤(1 - V^n()/n^2 ϵ^2) e^H^n() -n ϵ.

Then, x^n ∈D^n_, 1, ϵ.



We proceed the proof with contradiction. Suppose that x^n ∉D^n_, 1, ϵ. Hence, μ^n(x^n) ≤ e^-n H() -nϵ. Thus, μ^n(x^n)<μ^n(y^n) for all  y^n ∈A^n_, 1, ϵ. Consequently, 

    G_^n(x^n) > | A^n_, 1, ϵ| >   (1 - V^n()/n^2 ϵ^2) e^H^n() -n ϵ,

which contradicts the supposition of the lemma in (<ref>).




Suppose the following holds:

    G_^n(x^n) > e^H^n() +n ϵ.

Then, x^n ∈E^n_, 1, ϵ.



We proceed the proof with contradiction. Suppose that x^n ∉E^n_, 1, ϵ. Hence, μ^n(x^n) ≥ e^-n H() + nϵ. Thus, μ^n(x^n)>μ^n(y^n) for all  y^n ∈A^n_, 1, ϵ. Consequently, 

    G_^n(x^n) < G_^n(y^n)≤  e^H^n() +n ϵ,

which contradicts the supposition of the lemma in (<ref>).



Next, we provide a lemma of equivalence between tilted weakly typical sets and weakly typical sets of a tilted source, which we will rely on in proving the main theorem of this section.

Let ∈M_X. Then, for all α≠ 0, the following equivalences hold: 

    A^n_, α, ϵ   = A^n_T(,α),1, |α| ϵ,
    B^n_, α, ϵ   = B^n_T(,α),1, |α| ϵ,
    D^n_, α, ϵ   = D^n_T(,α),1, |α| ϵ, 
    E^n_, α, ϵ   = E^n_T(,α),1, |α| ϵ.




We have

    A^n_T(,α),1, |α| ϵ   = { x^n ∈X^n:  |log1/T(μ^n, α)(x^n) - H^n(T(T(,α),1)||T(,α))| <|α|n ϵ}
        = { x^n ∈X^n:  | 1/αlog1/T(μ^n, α)(x^n) - 1/αH^n(T(,α))| <n ϵ}
        = { x^n ∈X^n:  | log1/μ^n(x^n) - H^n(T(,α)||)| < n ϵ}
        = A^n_, α, ϵ,

where (<ref>) follows from Definition <ref>, (<ref>) follows by noting that T(, 1) = and H^n(||) = H^n() and the fact that α≠ 0, and (<ref>) follows from Lemma <ref>.

Next, note that (<ref>) follows directly from (<ref>) and Definition <ref>.

To establish (<ref>) note that:

    D^n_T(,α),1, |α| ϵ   = { x^n ∈X^n:  log1/T(μ^n, α)(x^n) - H^n(T(T(,α),1)||T(,α)) <|α| n ϵ}
        = { x^n ∈X^n: log1/T(μ^n, α)(x^n) - H^n(T(,α)) <|α|n ϵ}
        = D^n_, α, ϵ,

where (<ref>) follows from Definition <ref>, (<ref>) follows by noting that T(, 1) = and H^n(||) = H^n() and the fact that α≠ 0.
Finally, the proof for (<ref>) is very similar to that of (<ref>) with all the inequalities reversed, and is omitted for brevity.

Next, we proceed to the proof of Theorem <ref>.
[Proof of Theorem <ref>]
Part (a) is simply a reiteration of Definition <ref>, which is presented here for the completeness of the characterization.

To establish Part (b), 
notice that by Lemma <ref>, for all α≠ 0, we have A^n_T(,α),1, |α| ϵ  = A^n_, α, ϵ.
Part (b) is established by applying the bounds in (<ref>) and (<ref>) in Lemma <ref> to A^n_T(,α),1, |α| ϵ, and noting that α^2 V(T(, α)||) = V(T(, α)) from Lemma <ref>.


In Parts (c) and (d), first notice that by definition A^n_, α, ϵ⊆D^n_, α, ϵ and A^n_, α, ϵ⊆E^n_, α, ϵ and hence 
ℙ_{X^n ∈A^n_,α,ϵ}≤ℙ_{X^n ∈D^n_,α,ϵ} and ℙ_{X^n ∈A^n_,α,ϵ}≤ℙ_{X^n ∈E^n_,α,ϵ}. Hence, we only need to prove the right hand side inequalities in the claims.

To prove (<ref>) in Part (c), consider (<ref>) in Lemma <ref> applied to A^n_T(,α),1, |α| ϵ, in conjunction with (<ref>) in Lemma <ref>: 

    ℙ_T(, α){X^n ∈A^n_,α,ϵ}   = ℙ_T(, α){A^n_T(,α),1, |α| ϵ}
       ≥  1 - V^n(T(, α)||)/n^2 ϵ^2.

On the other hand, we have 

    ℙ_T(, α){X^n ∈A^n_,α,ϵ}   = ∑_x^n ∈A^n_,α,ϵ T(μ^n, α) (x^n)
        = ∑_x^n ∈A^n_,α,ϵ [ μ^n(x^n)]^α/∑_x^n ∈X^n [ μ^n(x^n)]^α
        = ∑_x^n ∈A^n_,α,ϵμ^n(x^n) [ μ^n(x^n)]^α-1/e^(1-α) H_α^n()
        < e^(1-α)(H^n(T(, α)|| ) -H_α^n())+ |α-1|n ϵ∑_x^n ∈A^n_,α,ϵμ^n(x^n) 
        = e^D^n(T(, α)|| )+ |α-1|n ϵℙ_{X^n ∈A^n_,α,ϵ},

where (<ref>) follow from the definition of the tilt in (<ref>), (<ref>) follows from the definition of the Rényi entropy in (<ref>), (<ref>) follows from (<ref>) or (<ref>) applied to [μ^n(x^n)]^α-1 depending on the sign of (α-1), and (<ref>) follows from (<ref>) in Lemma <ref>.  
Putting (<ref>) and (<ref>) together we arrive at the right hand side inequality in (<ref>).  Note that all the steps are applicable for α≠ 0, and hence are also applicable to the case where α∈ (0,1]. This also establishes the right hand side inequality in (<ref>) for Part (d).

In Part (c), the upper bound in (<ref>) would be established as follows. We first note:

    ℙ_T(, α){X^n ∈D^n_,α,ϵ}  = ℙ_T(, α){D^n_T(,α),1, |α| ϵ}≤  1 .

We also note that (<ref>) in conjunction with Lemma <ref> imply that for α>0:

    D^n_, α, ϵ = { x^n ∈X^n : μ^n(x^n) >  e^- H^n(T(, α)||) - n ϵ}.

and for α<0:

    D^n_, α, ϵ = { x^n ∈X^n :μ^n(x^n) <  e^- H^n(T(, α)||) + n ϵ}.

Thus,

    ℙ_T(, α){X^n ∈D^n_,α,ϵ}    = ∑_x^n ∈D^n_,α,ϵμ^n(x^n) [ μ^n(x^n)]^α-1/e^(1-α) H_α^n()
        > e^(1-α)(H^n(T(, α)|| ) -H_α^n())- |α-1|n ϵ∑_x^n ∈D^n_,α,ϵμ^n(x^n) 
        = e^D^n(T(, α)|| )- |α-1|n ϵℙ_{X^n ∈D^n_,α,ϵ},

where (<ref>) follows from (<ref>) (for α>1) and (<ref>) (for α<0) applied to [μ^n(x^n)]^α-1, and (<ref>) follows from (<ref>) in Lemma <ref>.  
Putting (<ref>) and (<ref>) together we arrive at the desired upper bound in (<ref>). 
The upper bound in (<ref>) is achieved by repeating (<ref>)–(<ref>) for E^n_,α,ϵ in the case of α∈ (0,1] and applying (<ref>).



To establish Parts (e) and (f), we first apply Lemmas <ref>–<ref>, to the sets B^n_T(,α),1, |α| ϵ, D^n_T(,α),1, |α| ϵ, and E^n_T(,α),1, |α| ϵ and notice the equivalences in Lemma <ref> to get:

    x^n ∈B^n_,α,ϵ     ⇒   G_T(, α)^n(x^n) ≥1/2(1 - V^n(T(, α))/n^2 α^2ϵ^2) e^H^n(T(, α)) -|α| n ϵ,
    
    x^n ∈D^n_,α,ϵ     ⇒   G_T(, α)^n(x^n) <   e^H^n(T(, α)) + |α| nϵ,
    
    x^n ∈D^n_,α,ϵ     ⇐   G_T(, α)^n(x^n) <  (1 - V^n(T(, α))/n^2 α^2ϵ^2) e^H^n(T(, α)) +|α| n ϵ,
    
    x^n ∈E^n_,α,ϵ     ⇐   G_T(, α)^n(x^n) > e^H^n(T(, α)) + |α| n ϵ.

Parts (e) and (f) then follow by invoking Theorem <ref> to notice that for all x^n ∈X^n, G_T(, α)^n(x^n) = G_^n(x^n) for α>0 and G_T(, α)^n(x^n) = R_^n(x^n) for α<0, and noting that α^2 V(T(, α)||) = V(T(, α)) from Lemma <ref>.






Theorem <ref> (a)-(d), for α = 1, reduces to the properties of the weakly typical set for finite-alphabet memoryless sources (see <cit.>).
Part (e) for α = 1 provides a characterization of guesswork for weakly typical strings.
For values of α≠ 1, the theorem further provides an asymptotic equipartition property for atypical strings generated by memoryless sources.
It is well known that several information theoretic quantities, such as the average length of the optimal source coding, and the channel capacity, could be analyzed through the typical or jointly typical sequences, and the entropy rate of the process appears as the fundamental performance limit. On the other hand, several other important notions, such as the error exponents are governed by the rare events comprising of atypical behavior. 
For different values of α, Theorem <ref> describes the large deviation performance of information and the logarithm of (forward) guesswork, which generalizes the notion of the typical set. In particular, it also recovers the large deviations performance of the optimal length function for prefix-free source coding as well. We remark that Theorem <ref> could also be used to recover known results that are concerned with rare events in a more intuitive way.
Finally, we expect Theorem <ref> to be generalizable to a winder class of stationary ergodic sources in light of the generalized version of the asymptotic equipartition property proved by Bobkov and Madiman <cit.>.


Note that the tighter non-asymptotic bounds on the moments of guesswork derived in <cit.> could not be used to fully characterize the distribution of guesswork as in Theorem <ref>. In particular, for the unlikely half of the sequences, the characterization involves reverse guesswork which is first studied in this paper.






§ LARGE DEVIATIONS


Thus far, we provided an operational meaning of the tilted family of the string-source in Theorem <ref>, and generalized the notion of the weakly typical set to the tilted weakly typical sets that characterize all strings in Theorem <ref>.
Before we use these tools to provide results on large deviations, we need one more definition.





A sequence of random variables {Y_n:n∈ℕ} taking values in ℝ satisfies the Large Deviation Principle with rate function J:ℝ→[0,∞] if J is lower semi-continuous and has compact level-sets, and for all Borel sets B

    -inf_t∈ B^∘ J(t)
            ≤lim inf_n→∞1/nlogℙ{Y_n∈ B}≤lim sup_n→∞1/nlogℙ{Y_n∈ B}≤ -inf_t∈B̅ J(t),

where B^∘ is the interior of B and B̅ is its closure.


If the Y_n take values in a compact subset K of ℝ, then to establish that {Y_n: n ∈ℕ} satisfies the LDP it is sufficient <cit.> to prove that the following exists for all t∈ K

    lim_ϵ↓0lim inf_n→∞1/nlogℙ{Y_n∈ (t-ϵ, t+ϵ)}
            =lim_ϵ↓0lim sup_n→∞1/nlogℙ{Y_n∈ (t-ϵ, t+ϵ)}
            = - J(t),

where ↓ and ↑ denote approaching from above and from below, respectively.
Note that all of the processes of interest to us take values in compact sets, since for all x^n ∈X^n,

    1/n g_^n(x^n) ∈ [0, log |X|],      1/n r_^n(x^n)  ∈ [0, log |X|],       1/n_^n(x^n)  ∈[log1/ε , log1/ε].

Thus, for our purposes it is sufficient to prove that

    lim_ϵ↓  0lim_n →∞1/nlog(1/ℙ{|Y_n -t |<ϵ}) = J(t).


Christiansen and Duffy proved that the logarithm of (forward) guesswork, {1/ng_^n(X^n) : n ∈ℕ}, defined in Definition <ref> satisfies a LDP and characterized the rate function as the solution to an optimization problem <cit.>, which is the Legendre-Fenchel transform of the scaled cumulant generating function.
In the rest of this section, we characterize the large deviations behavior of reverse guesswork, guesswork, and information, respectively, and provide their rate functions in terms of information theoretic quantities.




 §.§ Reverse guesswork

First, we use the generalization of the typical set and its properties, established in the previous section, to prove that the logarithm of reverse guesswork satisfies a LDP. We emphasize that the method used by Christiansen and Duffy <cit.> would not lead to proving a LDP for the logarithm of reverse guesswork  because the resulting rate function is non-convex as will be proved later in this section.



For any ∈M_X, the sequence {1/n r_^n(x^n): n∈ℕ} satisfies a LDP, and the corresponding rate function is implicitly given by

    J^r_(t) = D(T(, α_^r(t))|| ),

where

    α_^r(t) = _α∈ℝ_-*{ H(T(, α)) = t}.





Consider α_^r(t) defined in (<ref>) implying that H(T(, α_^r(t))) = t. Hence, for sufficiently large n,

    ℙ_{|1/nlog R_^n(X^n) - t| < ϵ}   =ℙ_{|1/nlog R_^n(X^n) - H(T(, α_^r(t))) | < ϵ}
       = ℙ_{| log R_^n(X^n) - H^n(T(, α_^r(t)))| < nϵ}
       ≤ℙ_{ X^n ∈D^n_, α_^r(t), (2ϵ) / α_^r(t)}
       ≤ e^-D^n(T(, α_^r(t))||) + 2|1-α_^r(t)|/α_^r(t)n ϵ,

where (<ref>) holds because (<ref>) ensures that for sufficiently large n we have

    {x^n: | log R_^n(x^n) - H^n(T(, α_^r(t)))| < nϵ}⊆D^n_, α_^r(t), (2ϵ) / α_^r(t),

and hence 

    P_{x^n: | log R_^n(x^n) - H^n(T(, α_^r(t)))| < nϵ}≤ P_{ X^n ∈D^n_, α_^r(t), (2ϵ) / α_^r(t)},

and (<ref>) is a direct application of the upper bound in (<ref>) to D^n_, α_^r(t), 2ϵ / α_^r(t).
Consequently,

    1/nlog(1/ℙ_{|1/nlog R_^n(X^n) - t| < ϵ}) ≥1/nD^n(T(, α_^r(t))||) - 2|1-α_^r(t)|/α_^r(t)ϵ.

Taking limits as n→∞ and letting ϵ↓ 0 would lead to

    lim_ϵ↓ 0lim_n→∞1/nlog(1/ℙ_{|1/nlog R_^n(X^n) - t| < ϵ}) ≥ D(T(, α_^r(t))||) .

Next, we will show that the left hand side of (<ref>) is also upper bounded by D(T(, α_^r(t))||). We have

    ℙ_{|1/nlog R_^n(X^n) - t| < ϵ}   =ℙ_{| log R_^n(X^n) - nH(T(, α_^r(t))) | < nϵ}
       ≥ℙ_{ X^n ∈B^n_, α_^r(t), ϵ /(2α_^r(t))}
       ≥ e^-D^n(T(, α_^r(t))||) - |1-α_^r(t)|/2α_^r(t)n ϵ,

where (<ref>) holds because (<ref>) and (<ref>) ensure that 

    B^n_, α_^r(t), ϵ / (2α_^r(t))⊆{x^n: | log R_^n(x^n) - H^n(T(, α_^r(t)))| < nϵ},

and (<ref>) is due to the lower bound in (<ref>). Hence, following steps similar to the previous case, 
 we have

    lim_ϵ↓ 0lim_n→∞1/nlog(1/ℙ_{|1/nlog R_^n(X^n) - t| < ϵ}) ≤ D(T(, α_^r(t))||),

which in conjunction with (<ref>) completes the proof.

The parametric representation of the rate function allows us to readily deduce some of the properties of the rate function.




The LDP rate function J^r_(t) associated with the logarithm of the reverse guesswork is a concave function of t, with its first and second derivatives given by

    d/dt J_^r(t) = 1- α_^r(t)/α_^r(t),
       d^2/dt^2J_^r(t) = 1/α_^r(t) V(T(, α_^r(t) )).

It also satisfies the following properties:

    lim_t ↓ 0d/dt J_^r(t) = -1,
       lim_t ↑log|X|d/dt J_^r(t) = -∞,
       lim_t ↓ 0d^2/dt^2 J_^r(t) = 0,
       lim_t ↑log|X|d^2/dt^2 J_^r(t) = -∞.




To establish (<ref>), note that since J^r_(·) could be implicitly defined as given in Theorem <ref>, and hence its derivative is given by the chain rule

    d/dt J_^r(t)    = d α_^r(t)/dt.d/dα D(T(, α)|| )|_α = α_^r(t)
         = . d/d α D(T(, α)|| ) /d/d α H(T(, α))|_α = α_^r(t)
        = α_^r(t)-1/α_^r(t),

where (<ref>) follows from the chain rule, and (<ref>) follows from the implicit function theorem implying that

    d α_^r(t)/dt  = . 1 /d/d α H(T(, α))|_α = α_^r(t).

Invoking Lemmas <ref> and <ref> to calculate the numerator and denominator in (<ref>) would lead to the desired result in (<ref>).

To establish (<ref>), note that 

    d^2/dt^2 J_^r(t)    = d/dt{d/dt J_^r(t)}
        =  d/dt{α_^r(t)-1/α_^r(t)}
        = dα_^r(t)/d t.  d/dα{α-1/α}|_α = α_^r(t)
        = .  d/dαα-1/α/d/d α H(T(, α))|_α = α_^r(t)
        =  1/α_^r(t) V(T(, α_^r(t) )),

where (<ref>) follows from (<ref>), (<ref>) follows from the application of the implicit function theorem in (<ref>), and (<ref>) follows from Lemma <ref>, leading to the desired result in (<ref>).

Equations (<ref>) and (<ref>) are derived by noting that the limit as t ↓ 0, would be equivalent to the limit as α→ -∞ in the parametric form.
Similarly, equations (<ref>) and (<ref>) are derived by noting that the limit as t ↑log |X|, would be equivalent to the limit as α↑ 0 in the parametric form.
Finally note that the concavity of J^r_(t) is evident as d^2/dt^2J_^r(t) >0 from (<ref>) for all α <0.







 §.§ Guesswork

The same proof methodology used for the logarithm of reverse guesswork leads us to establish a LDP for the logarithm of (forward) guesswork. Although this result is already proved by Christiansen and Duffy <cit.>, we further provide the implicit characterization of the rate function of the logarithm of guesswork  for all string-sources in M_X using information theoretic quantities. 











For any ∈M_X, the sequence {1/n g_^n(X^n): n∈ℕ} satisfies the large deviations principle with rate function J^g_. The rate function is implicitly given by

    J^g_(t) = D(T(, α_^g(t))|| ),

where

    α_^g(t) := _α∈ℝ_+*{ H(T(, α)) = t}.

Further, 
J^g_(0) = lim_α→∞ D(T(, α)|| )
and 
J^g_(log |X|) = D(u_X|| ),
where u_X is the uniform string-source on the alphabet X (see (<ref>)).



The steps of the proof are very similar to the steps of the proof of Theorem <ref> except that in this case α >0, and we will be invoking the bounds on G_^n in (<ref>)–(<ref>). We will also need to separate the α∈ (0,1) case and use the bounds on E^n_, α, ϵ instead of D^n_, α, ϵ. 


Next, we use Theorem <ref> to establish some properties of the rate function for the logarithm of guesswork.



The rate function J^g_(·) associated with the logarithm of guesswork is a convex function of its argument, and particularly its first and second derivatives are given by

    d/dt J_^g(t) = 1- α_^g(t)/α_^g(t),
       d^2/dt^2J_^g(t) = 1/α_^g(t) V(T(, α_^g(t) )).

Further, the following properties are satisfied:

    lim_t ↓ 0d/dt J_^g(t) = -1,
       lim_t ↑log|X|d/dt J_^g(t) = +∞,
       lim_t ↓ 0d^2/dt^2 J_^g(t) = 0,
       lim_t ↑log|X|d^2/dt^2 J_^g(t) = +∞.




The proof steps are similar to that of the proof of Theorem <ref>. We only point out the differences here. The limit as t ↑log |X|, would be equivalent to the limit as α↓ 0 in the parametric form. The covexity of J^g_(t) is proved by noting that d^2/dt^2J_^g(t) >0 from (<ref>) for all α >0.




 §.§ Information

Next, we state a result on the large deviations of information. This result could be viewed as a generalization of the Shannon-McMillan-Breiman Theorem <cit.> and the characterization of the exponential rate of decay for the probability of atypical strings (see <cit.> for a survey on the recent results on that front).


For any ∈M_X, the sequence {1/n_^n(X^n): n∈ℕ} satisfies a LDP, and the rate function is implicitly given by

    J^_(t) = D(T(, α^_(t))|| ),

where

    α^_(t) = _α∈ℝ{ H(T(, α)||) = t}.





First notice that for any α≠ 0 we have:

    {x^n: |1/n_^n(x^n) - H(T(, α)||) | < ϵ}   = {x^n: e^-H^n(T( , α)|| )-n ϵ <μ^n(x^n) < e^-H^n(T( , α)|| )+n ϵ}
        = { x^n: x^n ∈A^n_, α, ϵ}.

Now, consider α_^(t) defined in (<ref>) implying that H(T(, α_^(t)||) = t.

    ℙ_{|1/n_^n(X^n) - t| < ϵ}   =ℙ_{|1/n_^n(X^n) - H(T(, α_^(t))||) | < ϵ}
       = ℙ_{ X^n ∈A^n_, α_^(t), ϵ}
        < e^-D^n(T(, α_^(t))||) + |1-α_^(t)| n ϵ,

where (<ref>) follows from (<ref>), 
and (<ref>) is a direct application of the upper bound in (<ref>).
Consequently,

    1/nlog(1/ℙ_{|1/n_^n(X^n) - t| < ϵ}) ≥1/nD^n(T(,α_^(t))||) - |1-α_^(t)|ϵ.

Taking limits as n→∞ and letting ϵ↓ 0 would lead to

    lim_ϵ↓ 0lim_n→∞1/nlog(1/ℙ_{|1/n_^n(X^n) - t| < ϵ}) ≥ D(T(, α_^(t))||).

The rest of the proof entails showing that the above limit is upper bounded by D(T(, α_^(t))||). 
We have

    ℙ_{|1/n_^n(X^n) - t| < ϵ}   = ℙ_{ X^n ∈A^n_, α_^(t), ϵ}
        > (1 - V^n(T(, α)||)/n^2 ϵ^2) e^-D^n(T(, α_^(t))||) - |1-α_^(t)| n ϵ,

where (<ref>) is a direct application of the upper bound in (<ref>). 
Hence, following steps similar to the previous case, 
 we have

    lim_ϵ↓ 0lim_n→∞1/nlog(1/ℙ_{|1/n_^n(X^n) - t| < ϵ}) ≤ D(T(, α_^(t))||).

which in conjunction with (<ref>) completes the proof.




The above theorem on large deviations of information also lets us establish some properties of information.

For any ∈M_X, the min-cross entropy is defined as

    t_^- : = lim_α→ +∞ H(T(, α)||),

and the max-cross entropy  is defined as

    t_^+ : = lim_α→ -∞ H(T(, α)||).



Roughly speaking, the likelihood of the most likely string scales like e^-t_^- n. In words, the likelihood of the most likely string scales exponentially with n and the exponent of the scaling is the negative min-cross entropy. Similarly, the likelihood of the least likely string scales as e^-t_^+ n.
By definition, for any x^n ∈X^n, up to a multiplicative (1+ o_n(1)) term, we have

    t_^- ≤1/nlog1/μ^n(x^n)≤ t_^+.

Thus, the normalized negative log-likelihood is bounded between the min-cross entropy and the max-cross entropy.
Equipped with this definition, we will characterize the properties of the rate function for information in the next theorem.


The information rate function J^_ is a convex function, and its first two derivatives are given by

    d/dt J_^(t) = 1- α_^(t),
       d^2/dt^2J_^(t) = α_^(t)^2/ V(T(, α_^(t) )).

Further, it satisfies the following properties:

    lim_t ↓ t_^-d/dt J_^(t) = -∞,
       lim_t →log |X|d/dt J_^(t) = 1,
       lim_t ↑ t_^+d/dt J_^(t) = + ∞,
       lim_t ↓ t_^-d^2/dt^2 J_^(t) = +∞,
       lim_t →log |X|d^2/dt^2 J_^(t) =1/V (u_X ||),
       lim_t ↑ t_^+d^2/dt^2 J_^(t) = +∞,

where t_^- and t_^+ are the min-cross entropy and the max-cross entropy, respectively, as in Definition <ref>.



To establish (<ref>), note that  J^_ could be implicitly defined as given in Theorem <ref>, and thus its derivative would be given by

    d/dt J_^(t) = . d/d α D(T(, α)|| ) /d/d α H(T(, α) || )|_α = α_^(t),

invoking the implicit function theorem similar to the proof of Theorem <ref>.
Invoking Lemmas <ref> and <ref> to calculate the numerator and denominator in (<ref>) would lead to (<ref>).

To establish (<ref>), note that applying the implicit function theorem we get

    d^2/dt^2 J_^(t) = d/dtd/dt J_^(t) = .  d/dα  (1-α)/d/d α H(T(, α)||)|_α = α_^(t).

The desired result is obtained by applying Lemma <ref> to the denominator of (<ref>).

The rest of the properties are established by noting the definition of t_^- and t_^+ in Definition <ref> and considering the limits as α→+ ∞ and α→ -∞, respectively.





§ APPROXIMATION OF THE PROBABILITY MASS FUNCTION OF GUESSWORK



Thus far, we provided some results on the asymptotic scaling of guesswork. In this section, we would like to provide more practical results that would be applicable for small sequences in practice.
Inspired from the characterization of guesswork using the tilt, we provide an approximation formula that is accurate even when the length n is small. Our justification mostly relies on Theorem <ref> where we employ additional insights to compensate the impact of the finite sequence length.
The main contribution of this section is the following set of approximation formulas. 

For any ∈M_X, the size of the tilted weakly typical set of order α≠ 0 can be approximated by:

    |A^n_, α, ϵ| ≈1 - e^-2α n ϵ/√(2π V^n(T(, α))) e^H^n(T(, α)) +α n ϵ





For any ∈M_X, and for any x^n such that μ^n(x^n) = e^-H^n(T(, α)||) for some α∈ℝ_+*, we can approximately express its guesswork as

    G^n_(x^n) ≈e^H^n(T(, α ))/√(π/2V^n(T(, α))) + √(π/2 V^n(T(, α)) + 4).

Furthermore, for any x^n such that μ^n(x^n) = e^-H^n(T(, α)||) for some α∈ℝ_-*, the reverse guesswork is approximately given by

    R^n_(x^n) ≈e^H^n(T(, α ))/√(π/2V^n(T(, α))) + √(π/2 V^n(T(, α)) + 4).

Alternatively, guesswork can be approximated by

    G^n_(x^n)    = |X|^n - R^n_(x^n) 
       ≈ |X|^n - e^H^n(T(, α ))/√(π/2V^n(T(, α))) + √(π/2 V^n(T(, α)) + 4) .


Finally, for any x^n such that μ^n(x^n) = e^-H^n(𝐮_X ||), the guesswork would be approximated as 

    G^n_(x^n) ≈1/2 |X|^n.


[Justification]
We have

    G^n_(x^n)    ≈∫_0^∞1/√(2π V^n(T(, α)))e^H^n(T(, α )) - t - 1/2 V^n(T(, α)) t^2 dt 
        = 1/2exp(1/2V^n(T(, α))) erfc(√(1/2 V^n(T(, α)))) exp(H^n(T(, α )))
       ≈e^H^n(T(, α ))/√(π/2V^n(T(, α))) + √(π/2 V^n(T(, α)) + 4),

where (<ref>) follows because of the Laplace's method, (<ref>) follows the definition of erfc(·), and (<ref>) follows by applying the lower bound in <cit.>.




In the rest of this section, we provide numerical examples to show the effectiveness of the approximation formulas in Approximation <ref>. We will also plot their asymptotic properties, such as the large deviations performance of the logarithm of guesswork using the formulas derived in the previous sections.
To this end, we formally define the four string-sources that will be used in the numerical experiments. The subscript in the following definitions denotes the alphabet size.




The first example is a binary string-source.

Let S_2 refer to a Bernoulli source on alphabet on a binary alphabet with parameter vector (categorical distribution) θ = (0.2, 0.8).
We will use the notation S_2,n to denote a source with output of length n.



The next string-source is the ternary memoryless source used  as the working example throughout the paper.

Let S_3 refer to a memoryless string-source alphabet X = {a,b,c } of size |X| =3 with parameter vector (categorical distribution) θ = (0.2, 0.3, 0.5). 


Our last working example is a 77-ary source that is inspired from the true distribution of characters in password databases.

Let S_77 refer to a memoryless string-source alphabet size |X| =77 where the parameter vector (categorical distribution) is inspired from the empirical distribution of characters in passwords from <cit.>. 








We let X^n be a random string of length n that will be drawn from the string-source S_i where i will be clear from the context. The approximations of the probability are plotted in Fig. <ref>, where we have chosen the sequence length to be n=8. As can be seen the approximations in (<ref>) and (<ref>) collectively approximate well the distribution of guesswork for different string-sources with very good accuracy even for small sequence lengths.
Note that it is straightforward to calculate the formulas provided in Approximation <ref> for any memoryless process by sweeping α over the real line.




In Fig. <ref>, we further plot the rate functions J_^g, J_^r, and J_^ for string-sources S_2, S_3, and S_77. As can be seen, J_^g(t) and J_^(t) are convex functions of t whereas J_^r(t) is a concave function of t (as has already been proved). The rest of the properties of the rate functions could also be verified numerically and are observable from the plots.







§ CONCLUDING REMARKS AND FUTURE WORK


Guesswork is an important element of information theory that is intimately related to famous problems in information theory, such as the distribution of the length of one-shot source coding, the computational complexity of sequential decoding, the probability of error in list decoding, and the quantification of computational security against brute-force attacks.
In this paper, we defined the tilt operation, leading to derivation of tight bounds and accurate approximations to the distribution, and the large deviations behavior of guesswork. Using the tilt operation, we characterized the tilted family of a string-source and established several main properties of the tilted family. In particular, we showed that the set of all string-sources that result in the same ordering of all strings from the most likely to the least likely coincides with the tilted family of the string-source. We also used the tilted family of the string-source to characterize the large deviations behavior of the logarithm of forward/reverse guesswork and information. Finally, we provided an approximation formula for the PMF of guesswork and established its effectiveness using several numerical examples.

While this paper was focused on memoryless string-sources, future work would naturally consider a richer set of stationary ergodic string-sources, such as Markov or hidden Markov processes, or other mixing processes.  This research direction appears promising, as empirically comparing actual distributions and the approximations that are obtained by applying our approximation formulas to Markov or hidden Markov string-sources yield excellent concordance.   To illustrate this point, let us define two string-sources as follows.

Let S^M_3 refer to a first order Markov source on alphabet X = {a,b,c } of size |X| =3 with transition matrix T^M_3 given by

    T^M_3 = (
    [ 0.7 0.1 0.2; 0.2 0.3 0.5; 0.3 0.6 0.1 ]),

and where the initial distribution is chosen to be the stationary distribution of the chain.



Let S_3^H refer to a hidden Markov string-source on alphabet X = {a,b,c } of size |X| =3 with hidden states d and e, with 2 × 2 transition matrix T^H_3 given by

    T^H_3 = (
    [ 0.8 0.2; 0.4 0.6 ])

and the emission probabilities are grouped in the matrix E_3^H below.

    E_3^H = 
     (
    [ 0.1 0.3 0.6; 0.2 0.6 0.2;     ]).




In Fig. <ref>, we use the formulas (<ref>) and (<ref>) to provide an approximation on the distribution of guesswork. Note that in this case we have used the entropy and varentropy of the words rather than the rates in order to obtain the approximation. We observe that the formulas provide accurate approximations on the distribution of guesswork even for a hidden Markov source with infinite memory, and we conclude that the generalizing techniques developed in this paper is a direction for further work that is solidly motivated by empirical evidence. Moreover, from a heuristic perspective, our guesswork approximation techniques  may provide some indicative information regarding guesswork for more sources beyond memoryless string-sources, even though the analysis currently does not provide guarantees.













§ ACKNOWLEDGEMENT

The authors are thankful to Erdal Arıkan (Bilkent University) for informative discussions about guesswork and sequential decoding, Andrew Barron (Yale University) for discussions that led to the improvement of the approximations in the small sequence length regime, Mokshay Madiman (University of Delaware) for discussions on the connections with the Shannon-McMillan-Breiman Theorem,  Ali Makhdoumi (Duke University) for several discussions about the properties of exponential families and careful reading of an earlier version of this paper,  and Jossy Sayir (University of Cambridge) for suggesting the symmetric plotting of the probability simplex on an equilateral triangle.
IEEEtran


Ahmad Bierami is a research scientist at Electronic Arts Digital Platform – Data & AI,  leading fundamental research and development on training AI agents in multi-agent systems. His research interests broadly include AI, machine learning, statistics, information theory, and networks. Prior to joining EA in 2018, he held postdoctoral fellow positions at Duke, MIT, and Harvard. He received the BS degree in 2007 from Sharif University of Technology, Iran, and the PhD degree in 2014 from the Georgia Institute of Technology, in electrical and computer engineering. He is the recipient of the 2015 Sigma Xi Best PhD Thesis Award from Georgia Tech.


Robert Calderbank (M'89–SM'97–F'98) received the BSc degree in 1975 from Warwick University,
England, the MSc degree in 1976 from Oxford University, England, and the PhD degree in 1980 from the
California Institute of Technology, all in mathematics.

Dr. Calderbank is Professor of Electrical and Computer Engineering at Duke University where he directs
the Information Initiative at Duke (iiD). Prior to joining Duke in 2010, Dr. Calderbank was Professor of
Electrical Engineering and Mathematics at Princeton University where he directed the Program in
Applied and Computational Mathematics. Prior to joining Princeton in 2004, he was Vice President for
Research at AT&T, responsible for directing the first industrial research lab in the world where the
primary focus is data at scale. At the start of his career at Bell Labs, innovations by Dr. Calderbank were
incorporated in a progression of voiceband modem standards that moved communications practice
close to the Shannon limit. Together with Peter Shor and colleagues at AT&T Labs he developed the
mathematical framework for quantum error correction. He is a co-inventor of space-time codes for
wireless communication, where correlation of signals across different transmit antennas is the key to
reliable transmission.

Dr. Calderbank served as Editor in Chief of the IEEE TRANSACTIONS ON INFORMATION THEORY from
1995 to 1998, and as Associate Editor for Coding Techniques from 1986 to 1989. He was a member of
the Board of Governors of the IEEE Information Theory Society from 1991 to 1996 and from 2006 to
2008. Dr. Calderbank was honored by the IEEE Information Theory Prize Paper Award in 1995 for his
work on the Z4 linearity of Kerdock and Preparata Codes (joint with A.R. Hammons Jr., P.V. Kumar, N.J.A.
Sloane, and P. Sole), and again in 1999 for the invention of space-time codes (joint with V. Tarokh and N.
Seshadri). He has received the 2006 IEEE Donald G. Fink Prize Paper Award, the IEEE Millennium Medal,
the 2013 IEEE Richard W. Hamming Medal, and the 2015 Shannon Award. He was elected to the US
National Academy of Engineering in 2005.


Mark M. Christiansen is an assistant manager in the quantitative risk team in Grant Thornton. He received his B.A. (mod) in mathematics from Trinity College Dublin and his PhD in mathematics at Hamilton Institute in Maynooth. His interests include Probability Theory, Information Theory and their use in finance and security.



Ken R. Duffy is a Professor at Maynooth University where he is currently the Director of the Hamilton Institute. He received the B.A.(mod) and Ph.D. degrees in mathematics from the Trinity College Dublin. His primary research interests are in probability and statistics, and their applications in science and engineering.


Muriel Médard is the Cecil H. Green Professor in the Electrical Engineering and Computer Science (EECS) Department at MIT and leads the Network Coding and Reliable Communications Group at the Research Laboratory for Electronics at MIT. She has co-founded three companies to commercialize network coding, CodeOn, Steinwurf and Chocolate Cloud. She has served as editor for many publications of the Institute of Electrical and Electronics Engineers (IEEE), of which she was elected Fellow, and she has served as Editor in Chief of the IEEE Journal on Selected Areas in Communications. She was President of the IEEE Information Theory Society in 2012, and served on its board of governors for eleven years. She has served as technical program committee co-chair of many of the major conferences in information theory, communications and networking. She received the 2009 IEEE Communication Society and Information Theory Society Joint Paper Award, the 2009 William R. Bennett Prize in the Field of Communications Networking, the 2002 IEEE Leon K. Kirchmayer Prize Paper Award, the 2018 ACM SIGCOMM Test of Time Paper Award and several conference paper awards. She was co-winner of the MIT 2004 Harold E. Edgerton Faculty Achievement Award, received the 2013 EECS Graduate Student Association Mentor Award and served as Housemaster for seven years. In 2007 she was named a Gilbreth Lecturer by the U.S. National Academy of Engineering. She received the 2016 IEEE Vehicular Technology James Evans Avant Garde Award, the 2017 Aaron Wyner Distinguished Service Award from the IEEE Information Theory Society and the 2017 IEEE Communications Society Edwin Howard Armstrong Achievement Award.

 


