1 Bounds on the Lambert function and their application to the outage analysis of user cooperation Ioannis Chatzigeorgiou, Member, IEEE 2 Abstract—Problems formulated in terms of logarithmic or exponentialequationsoftenusetheLambertW functionintheir solutions. Expansions, approximations and bounds on W have 1 been derived in an effort to gain a better understanding of the relationshipbetweenequationparameters.Inthispaper,wefocus 0 6 ononeofthebranchesofW,denotedasW ,wederivetractable 1 −1 upper and lower bounds and we illustrate their usefulness in 0 identifying conditions under which user cooperation can yield a z)−1 2 lower outage probability than non-cooperative transmission. W( −2 n Index Terms—Lambert function, bounds, cooperation, decode a and forward, outage probability, Rayleigh fading. J −3 19 I. INTRODUCTION −4 W0(z) THE Lambert function, denoted as W(z) for z ∈ C, is W−1(z) ] T defined as the function that satisfies −−51 0 1 z2 3 4 5 .I W(z)eW(z) =z. (1) s Fig. 1. The two real-valued branches of the Lambert W function. Both c Taking logarithms of both sides of (1) and rearranging terms, [ branchesaredefinedforz≥−1/e,whereW−1(z)≤−1andW0(z)≥−1. we obtain the equivalent expression [1] Thetwobranchesmeetatthepoint(−1/e,−1). 1 v W(z)=ln(z)−ln(W(z)). (2) 5 If z is real, that is z ∈ R, W(z) can take two possible real solutions involving the Lambert function were derived in [6], 9 8 valuesfor−1/e≤z <0.ValuessatisfyingW(z)≥−1belong [7] but their focus was mainly on the primary branch W0. 4 to the principal branch, which is denoted as W0(z), while Algorithmic approaches were used in [8] to derive accurate 0 values satisfying W(z) ≤ −1 belong to the W−1(z) branch. approximations to the W−1 branch, for example 1. The two branches meet at the branch point for z = −1/e, W (z)≈ln(−z)−2α−1 −1 60 wfohrezre≥W00(−be1/loe)ng=toWt−he1(−pr1i/nec)ip=al−br1a.ncAhllWva0l(uze)s. oTfheWt(wzo)  (cid:34) (cid:18) 1+ln(−z)(cid:19)12(cid:35)−1 (3) 1 × 1− 1+α − branches of the W(z) are depicted in Fig. 1. 2 :   v The Lambert W function has been recognised in the solu- Xi tion of scientific and engineering problems and it has been where α=0.3205. introduced as a special function in numerical computation In this paper, we use functional analysis methods to derive r a software packages, such as Maple and MATLAB. It has upper and lower bounds on the W branch. Our objective is −1 also appeared in recent research in communications, such toobtainexpressionswhichmightnotbeasaccurateas(3)but as relaying strategies [2], moment generating functions for are simpler, more tractable and can shed light on the essence modelling signal fading [3] and long-haul cooperative power of solutions that involve the W function. −1 allocation methods [4]. Numerical evaluation of the Lambert The remainder of this paper has been organised as follows. W function makes use of recursive schemes. Non-recursive Section II presents bounds on the natural logarithm which expansionshavealsobeenobtainedforsmallandlargevalues are used as a stepping stone for the derivation of bounds on of z [1], [5]. For instance, the first few terms of the series the W function. Section III considers a simple cooperative −1 expansion of W(z) about the branch point are network and assesses the tightness and usefulness of the 1 11 proposed upper and lower bounds. Section IV summarises the W(z)=−1+p− p2+ p3+... 3 72 main points of the paper and discusses future work. (cid:112) (cid:112) where p= 2(e·z+1) for W and p=− 2(e·z+1) for 0 W . Tractable bounds that provide clearer interpretations of II. DERIVATIONOFBOUNDSONTHEW−1 FUNCTION −1 We will now introduce two lemmata which will help us I. Chatzigeorgiou is with the School of Computing and Communica- derive lower and upper bounds on the Lambert function tions,InfoLab21,LancasterUniversity,LA14WA,UnitedKingdom,(e-mail: [email protected]) W−1(z) for z =−e−u−1 and u>0. 2 Lemma 1. For x≥0, the natural logarithm is bounded from above by −1.9 x2 (cid:18) 1 (cid:19)2 ln(1+x) ≤ x− (4) −2 2 1+x/3 where equality holds for x=0. −2.1 Proof: Let −2.2 x2 (cid:18) 1 (cid:19)2 LambertW−1(−e−u−1) f(x)=ln(1+x)−x+ . −2.3 2 1+x/3 Upperboundforu∈(0,∞) Iff(x)≤0forx≥0,thelemmaistrue.Differentiatingf(x) −2.4 Lowerboundforu∈(0,∞) with respect to x, we obtain Lowerboundforu∈(0,1) −2.5 df(x) x3(x+9) 0.2 0.25 0.3 0.35 0.4 0.45 0.5 =− . u dx (x+1)(x+3)3 We observe that d f(x) = 0 for x = 0, while d f(x) < 0 cFoigrr.es2p.ondsTthoethueprpiegrht-bhoaunnddsiodne etxhpereLssaimonbeortf (f7u)ncatnidon(8W),−w1h(ic−hei−suv−al1id) dx dx for x>0. Therefore, f(x) is a decreasing function which has for every u > 0. The left-hand side of (7) generates a lower bound which canbemadetighterforu∈(0,1),usingtheleft-handsideof(8). a maximum at x=0, implying that f(x)≤0. As a lower bound on the natural logarithm, we use the first two terms of the Taylor series expansion of ln(1+x), that is approaches the minimum value of zero for x→0. Therefore x2 f(x,1)>0 for every x>0. ln(1+x) ≥ x− . (5) 2 Theorem 1. The Lambert function W (−e−u−1) for u > 0 −1 Lemma 2. For x>0 and g(x)=x−ln(1+x), we have is bounded as follows 2 (cid:112) √ √ 2 g(x) < x− 2g(x) < g(x). (6) −1− 2u−u<W (−e−u−1)<−1− 2u− u. (7) 3 −1 3 Proof: For c∈R, let Proof: Using (2), we express W (−e−u−1) as −1 f(x,c)=cg(x)+(cid:112)2g(x)−x. W (−e−u−1)=ln(−e−u−1)−ln(cid:0)W (−e−u−1)(cid:1) −1 −1 =−u−1+ln(−1)−ln(cid:0)W (−e−u−1)(cid:1) To prove the left-hand side and right-hand side of (6), we −1 need to show that f(x,2/3)<0 and f(x,1)>0, respectively. =−u−1+ln(1)−ln(cid:0)−W−1(−e−u−1)(cid:1) Substituting g(x) in f(x,c) and taking the derivative, we =−u−1−ln(cid:0)−W (−e−u−1)(cid:1). −1 obtain (cid:113) From the definition of the Lambert function, we have (cid:0) (cid:1) (cid:0) (cid:1) df(x,c) x− 1+x(1−c) 2 x−ln(1+x) W−1(−e−u−1)<−1, thus −W−1(−e−u−1)−1>0. We now = (cid:113) . invoke (6), set x=−W (−e−u−1)−1 and write g(x) as dx (cid:0) (cid:1) −1 (1+x) 2 x−ln(1+x) g(x)=x−ln(x+1) Weobservethatlimx→0(cid:0)ddxf(x,c)(cid:1)=0foreveryc∈R.Given =−W−1(−e−u−1)−1−ln(−W−1(−e−u−1)) that x takes positive values only, we can say that for x → 0, =u. the value of f(x,c) is maximised or minimised depending on whether f(x,c) is a decreasing or an increasing function, Substituting x with −W (−e−u−1)−1 and g(x) with u in −1 respectively. (6) produces (7). If f(x,c) is a decreasing function, then d f(x,c) < 0. dx Remark. In summary, if we define Taking into account that the denominator of the derivative is √ positive for x > 0, the numerator should be less than zero, F(u,c)=−1− 2u−cu which implies that we demonstrated that F(u,c) generates lower bounds on x2 (cid:18) 1 (cid:19)2 W−1(−e−u−1) for c≥1 and upper bounds for c≤2/3. The ln(1+x) < x− . 2 1+x(1−c) tightest lower and upper bounds are obtained for c=1 and c=2/3,respectively,whenu∈(0,∞).However,iftheinterval The above inequality holds for c = 2/3 as per (4) but is of u has a finite upper endpoint, that is, u ∈ (0,u ), we can 0 also valid for every c < 2/3. Thus, considering that the experimentally determine a value of 2/3<c<1 that generates maximum value of f(x,2/3) is just below zero for x → 0 a lower bound which is tighter than F(u,1). For example, and that f(x,2/3) is a decreasing function, we conclude that if u ∈ (0,1), the Lambert function W (−e−u−1) can be −1 f(x,2/3)<0 for every x>0. bounded as follows Following the same line of reasoning and invoking (5), we can show that for c≥1, f(x,c) is an increasing function that F(u,3/4)<W−1(−e−u−1)<F(u,2/3) (8) 3 as shown in Fig. 2. Note that F(u,3/4) and W−1(−e−u−1) B. Requirements for beneficial cooperation intersect for a value of u (not shown in the graph) that falls If we divide both parts of (9) by −e, we obtain outside the specified range (0,1). (cid:18)−1− θ(cid:48) (cid:19)e−1−0.θ5(cid:48)γ <−e−1−γθ. (10) III. APPLICATIONTOUSERCOOPERATION 0.5γ In this Section, we consider a simple case of decode-and- Recalling that W(z) is the solution to W(z)eW(z)=z, where forward cooperation [9] to illustrate the application of (7) and z = −e−1−γθ in this case, we can reduce (10) to (8) to the outage probability analysis of the system. θ(cid:48) (cid:16) (cid:17) −1− >W −e−1−γθ . (11) 0.5γ A. System model and problem formulation Let two users equipped with identical wireless transceivers We observe that the input to the W function takes values transmit to the same access point over orthogonal channels between −1/e and −1/e2, while the value of the output is whicharesubjecttofrequency-flatquasi-staticRayleighfading expectedtobelessthan-1.WecanthusinferthattheLambert and additive white Gaussian noise. Channel state information W functionin(11)correspondstotheW−1branch.From(11), is available to the access point, which can use coherent we conclude that the SNR threshold θ(cid:48) needs to be bounded detection to recover the received signals. as follows In the first scenario, the two users transmit their own data γ (cid:16) (cid:16) (cid:17) (cid:17) directly to the access point in a single step. We denote as θ ≤θ(cid:48) <−2 W−1 −e−1−γθ +1 , (12) θ the signal-to-noise ratio (SNR) threshold that characterises the modulation and coding (M&C) scheme employed by in order to ensure that condition (9) is met and cooperation each transceiver [10]. If γ is the average SNR of the uplink offers a lower outage probability than non-cooperation. channels, we assume that a suitable M&C scheme has been Even though (12) is accurate, it does not provide sufficient employedsothatθ <γ.Theoutageprobabilityofdirectnon- insight into the dependence between θ(cid:48), θ and γ. A more cooperative transmission is given by [11] conservative but more tractable upper bound on θ(cid:48) can be obtained if we invoke the right-hand side inequality in (7), Pnc =1−e−γθ. which gives (cid:114) In the second scenario, each user dedicates the first of a θ ≤θ(cid:48) ≤ γθ + θ. (13) two-stepprocesstotransmititsowndatadirectlytotheaccess 2 3 point while listening to the transmission of its partner over a The above expression implies that θ (left-hand side) is always perfect inter-user channel. In the second step, each user uses (cid:112) less than or equal to γθ/2 + θ/3 (right-hand side) or, its own uplink channel to transmit the successfully recovered equivalently,θ ≤(9/8)γ.Thisistruegiventhatweworkunder data of its partner to the access point. The SNR threshold in the assumption that θ <γ from the beginning of the analysis. this cooperative scenario is taken to be θ(cid:48) ≥ θ. The reason Wehaveestablishedthatifthevalueofθ(cid:48)isbetweenthetwo for our choice is that the two cooperating users, in an effort endpoints in (13), cooperation will definitely provide gains in to match the data rate of non-cooperative transmission, might reliability compared to non-cooperation. Taking into account use a higher code rate or a higher modulation order, which would make the adopted M&C scheme more susceptible to that θ/γ ∈ (0,1), we can use the tight lower bound on W−1 shown in (8) and combine it with (12) to state with certainty channelerrorsandwouldincreasetherequiredSNRthreshold. that if Ifeachuserallocateshalfofitspowertotransmititsowndata (cid:114) directly to the destination and the remaining half to transmit γθ 3θ θ(cid:48) ≥ + (14) the data of its partner, the outage probability of cooperative 2 8 communication is [11] cooperation should be avoided. Pc =1−(cid:18)1+ 0.θ5(cid:48)γ(cid:19)e−0.θ5(cid:48)γ beeRnegpiolontsteodfibnenFeifig.ci3al. cMooopreerastpieocnifiacsaldley,finFeidg.b3ya(1s2h)owhasvae snapshot of θ(cid:48) as a function of γ for θ =5 dB, while Fig. 3b provided that the access point uses maximal ratio combining. depicts the dependence of θ(cid:48) on θ for γ =5 dB. As expected, Cooperationwillbebeneficialforthetwousersonlyifdata whenthequalityoftheuplinkchannel(γ)increasesrelativeto transfertothedestinationismorereliablethannon-cooperative the SNR threshold of non-cooperative transmission (θ), users transmission. This implies that P <P or, equivalently, c nc havetheflexibilitytochooseanSNRthresholdforcooperative (cid:18)1+ θ(cid:48) (cid:19)e−0.θ5(cid:48)γ >e−γθ. (9) t(rFaings.m3ias)s.ioTnhi(sθ(cid:48)t)refnrodmisarnevinecrsreedaswinhgelynbθroaapdperroaracnhgesetohfevvaaluluees 0.5γ of γ (Fig. 3b). We observe that the top border of the shaded Our objective is to determine the range of values of θ(cid:48) as a regions is tightly enveloped by the bounds in (13) and (14), function of θ and γ for which condition (9) is met. which have a much simpler representation than (12). 4 10 5 Regionofbeneficialcooperation 9.5 Upperboundonhighestθ′forcooperation 4 9 Lowerboundonhighestθ′forcooperation 8.5 3 8 2 B) B) d7.5 d ( ( ′θ ′θ 1 7 6.5 0 6 Regionofbeneficialcooperation −1 Upperboundonhighestθ′forcooperation 5.5 Lowerboundonhighestθ′forcooperation 5 −2 5 6 7 8 9 10 11 12 13 14 15 −2 −1 0 1 2 3 4 5 γ(dB) θ(dB) (a)θ(cid:48) asafunctionofγ forθ=5dB (b)θ(cid:48) asafunctionofθ forγ=5dB Fig.3. Cooperationyieldsaloweroutageprobabilitythannon-cooperationforanyvalueofθ(cid:48) withintheshadedregions,whichsatisfy(12).Lower(blue dashedline)andupper(reddash-dottedline)boundsonthetopborderoftheregioncorrespondtotheright-handsideof(13)and(14),respectively. C. Example case REFERENCES Considerthecasewhentwousersemployrate-1/2convolu- [1] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth,“OntheLambertWfunction,”Adv.ComputationalMath.,vol.5, tional coding with θ = −0.983 dB in non-cooperative mode. no.1,pp.329–359,Jan.1996. These two users decide to cooperate and switch to uncoded [2] T.Cui,T.Ho,andJ.Kliewer,“Memorylessrelaystrategiesfortwo-way binary phase shift keying (BPSK) with θ(cid:48) =5.782 dB [12] in relaychannels,”IEEETrans.Commun.,vol.57,no.10,pp.3132–3143, Oct.2009. order to maintain a constant transfer rate. As we can deduce [3] C. Tellambura and D. Senaratne, “Accurate computation of the MGF from Fig. 3b, cooperation will have a negative effect on the ofthelognormaldistributionanditsapplicationtosumoflognormals,” outage probability if the average uplink SNR is γ = 5 dB. IEEETrans.Commun.,vol.58,no.5,pp.1568–1577,May2010. [4] D. Wu, Y. Cai, L. Zhou, and J. Wang, “A cooperative communication Solving the right-hand side inequality in (13) for γ, we find schemebasedoncoalitionformationgameinclusteredwirelesssensor that cooperation will be beneficial only if networks,” IEEE Trans. Wireless Commun., vol. 11, no. 3, pp. 1190– 1200,Mar.2012. (cid:32) √ (cid:33)2 [5] F.Chapeau-BlondeauandA.Monir,“NumericalevaluationoftheLam- θ(cid:48) θ γ ≥2 √ − bertWfunctionandapplicationtogenerationofgeneralizedGaussian θ 3 noise with exponent 1/2,” IEEE Trans. Signal Process., vol. 50, no. 9, pp.2160–2164,Sep.2002. [6] A. Hoorfar and M. Hassani, “Inequalities on the Lambert W function or γ ≥ 14.925 dB for this example. Note that γ cannot be and hyperpower function,” J. Inequalities in Pure and Applied Math., determined as easily from (12), where it is both a factor of θ(cid:48) vol.9,no.2,2008. and an input to W . [7] S. M. Stewart, “On certain inequalities involving the Lambert W −1 function,” J. Inequalities in Pure and Applied Math., vol. 10, no. 4, 2009. [8] D.A.Barry,L.Li,andD.-S.Jeng,“Commentson“Numericalevaluation IV. CONCLUSIONSANDFUTUREWORK oftheLambertWfunctionandapplicationtogenerationofgeneralized Gaussian noise with exponent 1/2”,” IEEE Trans. Signal Process., In this paper, we focused on the W branch of the vol.52,no.5,pp.1456–1458,May2004. −1 [9] A.Sendonaris,E.Erkip,andB.Aazhang,“Usercooperationdiversity- Lambert W function and we derived tractable closed-form PartI:Systemdescription,”IEEETrans.Commun.,vol.51,no.11,pp. upper and lower bounds. We then considered a network of 1927–1938,Nov.2003. two users and an access point, and we demonstrated that our [10] Y.Xi,A.Burr,J.Wei,andD.Grace,“Ageneralupperboundtoevaluate packeterrorrateoverquasi-staticfadingchannels,”IEEETrans.Wireless proposed bounds can identify operational regions of mutually Commun.,vol.10,no.5,pp.1373–1377,May2011. beneficial cooperation based on system characteristics, such [11] Y.Zhao,R.Adve,andT.J.Lim,“OutageprobabilityatarbitrarySNR asthechannelqualityandtheemployedtransmissionscheme. withcooperativediversity,”IEEECommun.Lett.,vol.9,no.8,pp.700– 702,Aug.2005. The derived expressions can be used to make decisions on [12] I. Chatzigeorgiou, I. J. Wassell, and R. Carrasco, “On the frame error whether nodes should cooperate or not, if their objective is to rateoftransmissionschemesonquasi-staticfadingchannels,”inProc. improve outage probability. Conf.onInformationSciencesandSystems,Princeton,USA,Mar.2008. To illustrate the application of the Lambert function and the proposed bounds, we assumed that inter-user channels are perfectanduplinkchannelsarestatisticallysimilar.Follow-on workwillaimtoderiveconditionsforcooperationinnetworks whereinter-userchannelscanbereciprocalorindependentand uplink channels can be statistically similar or dissimilar.