text:
# References

Magnetic field-induced Landau Fermi Liquid in high-$`T_c`$ metals

M.Ya. Amusiaa,b, V.R. Shaginyana,c 111E–mail: vrshag@thd.pnpi.spb.ru

$`^a`$The Racah Institute of Physics, the Hebrew University, Jerusalem 91904, Israel;
$`^b`$A.F. Ioffe Physical-Technical Institute, 194021 St. Petersburg, Russia;
$`^c`$Petersburg Nuclear Physics Institute, Gatchina, 188300, Russia

## Abstract

We consider the behavior of strongly correlated electron liquid in high-temperature superconductors within the framework of the fermion condensation model. We show that at low temperatures the normal state recovered by the application of a magnetic field larger than the critical field can be viewed as the Landau Fermi liquid induced by the magnetic field. In this state, the Wiedemann-Franz law and the Korringa law are held and the elementary excitations are the Landau Fermi Liquid quasiparticles. Contrary to what might be expected from the Landau theory, the effective mass of quasiparticles depends on the magnetic field. The recent experimental verifications of the Wiedemann-Franz law in heavily hole-overdoped, overdoped and optimally doped cuprates and the verification of the Korringa law in the electron-doped copper-oxide superconductor strongly support the existence of fermion condensate in high-$`T_c`$ metals.

PACS: 74.25.Fy; 74.72.-h; 74.20.-z

Keywords: High temperature superconductivity; Wiedemann-Franz law; Korringa law

The Landau Fermi Liquid (LFL) theory belongs to the most important achievements in physics . The LFL theory has revealed that the low-energy elementary excitations of a Fermi liquid look like the spectrum of an ideal Fermi gas. These excitations are described in terms of quasiparticles with an effective mass $`M^{}`$, charge $`e`$ and spin $`1/2`$. The quasiparticles define the major part of the low-temperature properties of Fermi liquids. Note that this powerful theory gives theoretical grounds for the theory of conventional superconductivity. On the other hand, despite outstanding results obtained in the condensed matter physics, the understanding of the rich and striking behavior of the high-temperature superconductors remains, as years before, among the main problems of the condensed matter physics. There is also a fundamental question about whether or not the properties of this electron liquid in high-$`T_c`$ metals can be understood within the framework of the LFL theory.

It was reported recently that in the normal state obtained by applying a magnetic field greater than the upper critical filed $`B_c`$, in a hole-doped cuprates at overdoped concentration (Tl2Ba2CuO6+δ)  and at optimal doping concentration (Bi2Sr2CuO6+δ) , there are no any sizable violations of the Wiedemann-Franz (WF) law. In the electron-doped copper oxide superconductor Pr0.91LaCe0.09Cu04-y ($`T_c`$=24 K) when superconductivity is removed by a strong magnetic field, it was found that the spin-lattice relaxation rate $`1/T_1`$ follows the $`T_1T=constant`$ relation, known as Korringa law , down to temperature of $`T=0.2`$ K . At elevated temperatures and applied magnetic fields of 15.3 T perpendicular to the CuO2 plane, $`1/T_1T`$ as a function of $`T`$ is a constant below $`T=55`$ K. At $`300`$ K $`>T>50`$ K, $`1/T_1T`$ decreases with increasing $`T`$ . Recent measurements for strongly overdoped non-superconducting La1.7Sr0.3CuO4 have shown that the resistivity $`\rho `$ exhibits $`T^2`$ behavior, $`\rho =\rho _0+\mathrm{\Delta }\rho `$ with $`\mathrm{\Delta }\rho =AT^2`$, and the WF law is verified to hold perfectly . Since the validity of the WF law and of the Korringa law are a robust signature of LFL, these experimental facts demonstrate that the observed elementary excitations cannot be distinguished from the Landau quasiparticles. This imposes strong constraints for models describing the hole-doped and electron-doped high-temperature superconductors. For example, in the cases of a Luttinger liquid , spin-charge separation (see e.g. ), and in some solutions of $`tJ`$ model  a violation of the WF law was predicted.

In this Letter, we consider the behavior of strongly correlated electron liquid in high-temperature metals within the framework of the fermion condensation model . We show that at temperatures $`T0`$ the normal state recovered by the application of a magnetic field larger than the critical field $`B_c`$ can be viewed as LFL induced by the magnetic field. In this state, the WF law and the Korringa law are held and the elementary excitations are LFL quasiparticles. We show that contrary to what might be expected from the Landau theory, the effective mass of quasiparticles depends on the magnetic field.

At $`T0`$, the ground state energy $`E_{gs}[\kappa (𝐩),n(𝐩)]`$ of an electron liquid is a functional of the order parameter of the superconducting state $`\kappa (𝐩)`$ and of the quasiparticle occupation numbers $`n(𝐩)`$. Here we assume that the electron system is two-dimensional, while all results can be transported to the case of three-dimensional system. This energy is determined by the known equation of the weak-coupling theory of superconductivity, see e.g.

$$E_{gs}=E[n(𝐩)]+\lambda _0V(𝐩_1,𝐩_2)\kappa (𝐩_1)\kappa ^{}(𝐩_2)\frac{d𝐩_1d𝐩_2}{(2\pi )^4}.$$
(1)
Here $`E[n(𝐩)]`$ is the ground-state energy of a normal Fermi liquid, $`n(𝐩)=v^2(𝐩)`$ and $`\kappa (𝐩)=v(𝐩)\sqrt{1v^2(𝐩)}`$. It is assumed that the pairing interaction $`\lambda _0V(𝐩_1,𝐩_2)`$ produced, for instance, by electron-phonon interaction in high-$`T_c`$ metals is weak. Minimizing $`E_{gs}`$ with respect to $`\kappa (𝐩)`$ we obtain the equation connecting the single-particle energy $`\epsilon (𝐩)`$ to the superconducting gap $`\mathrm{\Delta }(𝐩)`$,

$$\epsilon (𝐩)\mu =\mathrm{\Delta }(𝐩)\frac{12v^2(𝐩)}{2\kappa (𝐩)},$$
(2)
where the $`\mu `$ is the chemical potential, and single-particle energy $`\epsilon (𝐩)`$ is determined by the Landau equation

$$\epsilon (𝐩)=\frac{\delta E[n(𝐩)]}{\delta n(𝐩)}.$$
(3)
Note that $`E[n(𝐩)]`$, $`\epsilon [n(𝐩)]`$, and the Landau amplitude $`F_L(𝐩,𝐩_1)=\delta E^2[n(𝐩)]/\delta n(𝐩)\delta (𝐩_1)`$ implicitly depend on the density $`x`$ which defines the strength of $`F_L`$. The equation for the superconducting gap $`\mathrm{\Delta }(𝐩)`$ is of the form

$`\mathrm{\Delta }(𝐩)`$ $`=`$ $`{\displaystyle \lambda _0V(𝐩,𝐩_1)\kappa (𝐩_1)\frac{d𝐩_1}{4\pi ^2}}`$ (4)
$`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle \lambda _0V(𝐩,𝐩_1)\frac{\mathrm{\Delta }(𝐩_1)}{\sqrt{(\epsilon (𝐩_1)\mu )^2+\mathrm{\Delta }^2(𝐩_1)}}\frac{d𝐩_1}{4\pi ^2}}.`$
If $`\lambda _00`$, than the maximum value of the superconducting gap $`\mathrm{\Delta }_10`$, and Eq. (2) reduces to the equation

$$\epsilon (𝐩)\mu =0,\text{ if}0<n(𝐩)<1;p_ipp_f.$$
(5)
A new state of electron liquid with the fermion condensate (FC)  is defined by Eq. (5) and characterized by a flat part of the spectrum in the $`(p_ip_f)`$ region. Apparently, the momenta $`p_i`$ and $`p_f`$ have to satisfy $`p_i<p_F<p_f`$, where $`p_F`$ is the Fermi momentum. When the amplitude $`F_L(p=p_F,p_1=p_F)`$ as a function of the density $`x`$ becomes sufficiently small, the flat part vanishes, Eq. (5) has the only trivial solution $`\epsilon (p=p_F)=\mu `$, and the quasiparticle occupation numbers are given by the step function, $`n(𝐩)=\theta (p_Fp)`$ . Note, that a formation of the flat part of the spectrum has been recently confirmed in Ref. .

Now we can study the relationships between the state defined by Eq. (5) and the superconductivity. At $`T0`$, Eq. (5) defines a particular state of a Fermi liquid with FC, for which the modulus of the order parameter $`|\kappa (𝐩)|`$ has finite values in the $`(p_ip_f)`$ region, whereas $`\mathrm{\Delta }_10`$ unlike the conventional theory of superconductivity, which demands that $`\mathrm{\Delta }_1`$ vanishes simultaneously with the order parameter $`\kappa (𝐩)`$. Such a situation can take place because the order parameter $`\kappa (𝐩)`$, as it follows from Eqs. (3) and (5), is determined by the Landau amplitude $`F_L`$, while $`\mathrm{\Delta }_1`$ is given by Eq. (4) and tends to zero at $`\lambda _00`$. This state can be considered as superconducting, with an infinitely small value of $`\mathrm{\Delta }_1`$, so that the entropy of this state is equal to zero. It is obvious that this state being driven by the quantum phase transition disappears at $`T>0`$ . Any quantum phase transition, which takes place at temperature $`T=0`$, is determined by a control parameter other than temperature, for example, by pressure, by magnetic field, or by the density of mobile charge carriers $`x`$. The quantum phase transition occurs at a quantum critical point. At some density $`xx_{FC}`$, when the Landau amplitude $`F_L`$ becomes sufficiently weak, and $`p_ip_Fp_f`$, Eq. (5) determines the critical density $`x_{FC}`$ at which the fermion condensation quantum phase transition (FCQPT) takes place leading to the formation of FC . It follows from Eq. (5) that the system becomes divided into two quasiparticle subsystems: the first subsystem in the $`(p_ip_f)`$ range is characterized by the quasiparticles with the effective mass $`M_{FC}^{}1/\mathrm{\Delta }_1`$, while the second one is occupied by quasiparticles with finite mass $`M_L^{}`$ and momenta $`p<p_i`$. The density of states near the Fermi level tends to infinity, $`N(0)M_{FC}^{}1/\mathrm{\Delta }_1`$ .

If $`\lambda _00`$, then $`\mathrm{\Delta }_1`$ becomes finite. It is seen from Eq. (4) that the superconducting gap depends on the single-particle spectrum $`\epsilon (𝐩)`$. On the other hand, it follows from Eq. (2) that $`\epsilon (𝐩)`$ depends on $`\mathrm{\Delta }(𝐩)`$ provided that at $`\mathrm{\Delta }_10`$ the spectrum is given by Eq. (5). Let us assume that $`\lambda _0`$ is small so that the particle-particle interaction $`\lambda _0V(𝐩,𝐩_1)`$ can only lead to a small perturbation of the order parameter $`\kappa (𝐩)`$ determined by Eq. (5). Upon differentiation both parts of Eq. (2) with respect to the momentum $`p`$, we obtain that the effective mass $`M_{FC}=d\epsilon (p)/dp_{|p=p_F}`$ becomes finite

$$M_{FC}^{}p_F\frac{p_fp_i}{2\mathrm{\Delta }_1}.$$
(6)
It is clear from Eq. (6) that the effective mass and the density of states $`N(0)M_{FC}^{}1/\mathrm{\Delta }_1`$ are finite. As a result, we are led to the conclusion that in contrast to the conventional theory of superconductivity the single-particle spectrum $`\epsilon (𝐩)`$ strongly depends on the superconducting gap and we have to solve Eqs. (3) and (4) in a self-consistent way.

Since the particle-particle interaction is small, the order parameter $`\kappa (𝐩)`$ is governed mainly by FC and we can solve Eq. (4) analytically taking the Bardeen-Cooper-Schrieffer approximation for the particle-particle interaction: $`\lambda _0V(𝐩,𝐩_1)=\lambda _0`$ if $`|\epsilon (𝐩)\mu |\omega _D`$, i.e. the interaction is zero outside this region, with $`\omega _D`$ being the characteristic phonon energy. As a result, the maximum value of the superconducting gap is given by

$$\mathrm{\Delta }_1(0)\frac{\lambda _0p_F(p_fp_F)}{2\pi }\mathrm{ln}\left(1+\sqrt{2}\right)2\beta \epsilon _F\frac{p_fp_F}{p_F}\mathrm{ln}\left(1+\sqrt{2}\right).$$
(7)
Here, the Fermi energy $`\epsilon _F=p_F^2/2M_L^{}`$, and the dimensionless coupling constant $`\beta `$ is given by the relation $`\beta =\lambda _0M_L^{}/2\pi `$. Taking the usual values of $`\beta `$ as $`\beta 0.3`$, and assuming $`(p_fp_F)/p_F0.2`$, we get from Eq. (7) a large value of $`\mathrm{\Delta }_1(0)0.1\epsilon _F`$, while for normal metals one has $`\mathrm{\Delta }_1(0)10^3\epsilon _F`$. Now we determine the energy scale $`E_0`$ which defines the region occupied by quasiparticles with the effective mass $`M_{FC}^{}`$

$$E_0=\epsilon (𝐩_f)\epsilon (𝐩_i)2\frac{(p_fp_F)p_F}{M_{FC}^{}}2\mathrm{\Delta }_1.$$
(8)
We have returned back to the Landau Fermi liquid theory since high energy degrees of freedom are eliminated and the quasiparticles are introduced. The only difference between LFL, which serves as a basis when constructing the superconducting state, and Fermi liquid after FCQPT is that we have to expand the number of relevant low energy degrees of freedom by introducing new type of quasiparticles with the effective mass $`M_{FC}^{}`$ given by Eq. (6) and the energy scale $`E_0`$ given by Eq. (8). Therefore, the single-particle spectrum $`\epsilon (𝐩)`$ of system in question is characterized by two effective masses $`M_L^{}`$ and $`M_{FC}^{}`$ and by the scale $`E_0`$, which define the low temperature properties including the line shape of quasiparticle excitations . We note that both the effective mass $`M_{FC}^{}`$ and the scale $`E_0`$ are temperature independent at $`T<T_c`$, where $`T_c`$ is the critical temperature of the superconducting phase transition . Obviously, we cannot directly relate these new quasiparticle excitations with the quasiparticle excitations of an ideal Fermi gas because the system in question has undergone FCQPT. Nonetheless, the main basis of the Landau Fermi liquid theory survives FCQPT: the low energy excitations of a strongly correlated liquid with FC are quasiparticles.

As it was shown above, properties of these new quasiparticles are closely related to the properties of the superconducting state. We may say that the quasiparticle system in the range $`(p_ip_f)`$ becomes very “soft” and is to be considered as a strongly correlated liquid. On the other hand, the system’s properties and dynamics are dominated by a strong collective effect having its origin in FCQPT and determined by the macroscopic number of quasiparticles in the range $`(p_ip_f)`$. Such a system cannot be perturbed by the scattering of individual quasiparticles and has features of a “quantum protectorate” .

As any phase transition, FCQPT is related to the order parameter, which induces a broken symmetry. As we have seen above, the order parameter is the superconducting order parameter $`\kappa (𝐩)`$, while $`\mathrm{\Delta }_1`$ being proportional to the coupling constant (see Eqs. (5) and (7)) can be small. Therefore, the existence of such a state, that is electron liquid with FC, can be revealed experimentally. Since the order parameter $`\kappa (𝐩)`$ is suppressed by the critical magnetic field $`B_c`$, when $`B_c^2\mathrm{\Delta }_1^2`$. If the coupling constant $`\lambda _00`$, the weak critical magnetic field $`B_c0`$ will destroy the state with FC converting the strongly correlated Fermi liquid into LFL. In this case the magnetic field play a role of the control parameter determining the effective mass

$$M_{FC}^{}(B)\frac{1}{\sqrt{B}}.$$
(9)
Note, that the outlined above behavior was observed experimentally in the heavy-electron metal YbRh2Si2 .

If $`\lambda _0`$ is finite, the critical field is also finite, and Eq. (9) is valid at $`B>B_c`$. In that case, the effective mass $`M_{FC}^{}(B)`$ is finite, and the system is driven back to LFL and has the LFL behavior induced by the magnetic field. At a constant magnetic field, the low energy elementary excitations are characterized by $`M_{FC}^{}(B)`$ and cannot be distinguished from Landau quasiparticles. As a result, at $`T0`$, the WF law is held in accordance with experimental facts . On the hand, in contrast to the LFL theory, the effective mass $`M_{FC}^{}(B)`$ depends on the magnetic field.

Equation (9) shows that by applying a magnetic field $`B>B_c`$ the system can be driven back into LFL with the effective mass $`M_{FC}^{}(B)`$ which is finite and independent of the temperature. This means that the low temperature properties depend on the effective mass in accordance with the LFL theory. In particular, the resistivity $`\rho (T)`$ as a function of the temperature behaves as $`\rho (T)=\rho _0+\mathrm{\Delta }\rho (T)`$ with $`\mathrm{\Delta }\rho (T)=AT^2`$, and the factor $`A(M_{FC}^{}(B))^2`$. At finite temperatures, the system persists to be LFL, but there is the crossover from the LFL behavior to the non-Fermi liquid behavior at temperature $`T^{}(B)\sqrt{B}`$. At $`T>T^{}(B)`$, the effective mass starts to depend on the temperature $`M_{FC}1/T`$, and the resistivity possesses the non-Fermi liquid behavior with a substantial linear term, $`\mathrm{\Delta }\rho (T)=aT+bT^2`$ . Such a behavior of the resistivity was observed in the cuprate superconductor Tl2Ba2CuO6+δ ($`T_c<`$ 15 K) . At B=10 T, $`\mathrm{\Delta }\rho (T)`$ is a linear function of the temperature between 120 mK and 1.2 K, whereas at B=18 T, the temperature dependence of the resistivity is consistent with $`\rho (T)=\rho _0+AT^2`$ over the same temperature range .

In LFL, the nuclear spin-lattice relaxation rate $`1/T_1`$ is determined by the quasiparticles near the Fermi level whose population is proportional to $`M^{}T`$, so that $`1/T_1TM^{}`$ is a constant . As it was shown, when the superconducting state is removed by the application of a magnetic field, the underlying ground state can be seen as the field induced LFL with effective mass depending on the magnetic field. As a result, the rate $`1/T_1`$ follows the $`T_1T=constant`$ relation, that is the Korringa law is held. Unlike the behavior of LFL, as it follows from Eq. (9), $`1/T_1TM_{FC}^{}(B)`$ decreases with increasing the magnetic field at $`T<T^{}(B)`$. While, at $`T>T^{}(B)`$, we observe that $`1/T_1T`$ is a decreasing function of the temperature, $`1/T_1TM_{FC}^{}1/T`$. These observations are in a good agreement with the experimental facts . Since $`T^{}(B)`$ is an increasing function of the magnetic field, the Korringa law retains its validity to higher temperatures at elevated magnetic fields. We can also conclude, that at temperature $`T_0T^{}(B_0)`$ and elevated magnetic fields $`B>B_0`$, the system shows a more pronounced metallic behavior since the effective mass decreases with increasing $`B`$, see Eq. (9). Such a behavior of the effective mass can be observed in the de Haas van Alphen-Shubnikov studies, $`1/T_1T`$ measurements, and the resistivity measurements. These experiments can shed light on the physics of high-$`T_c`$ metals and reveal relationships between high-$`T_c`$ metals and heavy-electron metals.

The existence of FCQPT can also be revealed experimentally because at densities $`x>x_{FC}`$, or beyond the FCQPT point, the system should be LFL at sufficiently low temperatures . Recent experimental data have shown that this liquid exists in heavily overdoped non-superconducting La1.7Sr0.3CuO4 . It is remarkable that up to $`T=55`$ K the resistivity exhibits the $`T^2`$ behavior with no additional linear term, and the WF law is verified to within the experimental resolution . While at elevated temperatures, a strong deviations from the LFL behavior are observed. We anticipate that the system can be again driven back to the LFL behavior by the application of sufficiently strong magnetic fields .

In summary, we have shown that the Landau Fermi liquid properties of high-$`T_c`$ metals observed at low temperatures in optimally hole-doped, overdoped and electron-doped cuprates by the application of a magnetic field higher than the critical field can be explained within the frameworks of the fermion condensation theory of high-$`T_c`$ superconductivity. In that case of LFL obtained by applying magnetic field, the effective mass depends on the magnetic field, the WF law and the Korringa law are held. These observations are in good agreement with experimental facts. The recent experimental verifications of the WF law in heavily overdoped, overdoped and optimally doped cuprates and the verification of the Korringa law in the electron-doped copper-oxide superconductor give strong support in favor of the existence of FC in high-$`T_c`$ metals.

MYA is grateful to the Hebrew University Intramural fund of the Hebrew University for financial support. VRS is grateful to Racah Institute of Physics for the hospitality during his stay in Jerusalem. This work was supported in part by the Russian Foundation for Basic Research, project No 01-02-17189.


format: text

text:
# The Cardy-Verlinde formula and entropy of Topological Kerr-Newman black holes in de Sitter spaces

## 1 Introduction

Holography is believed to be one of the fundamental principles of the true quantum theory of gravity. An explicitly calculable example of holography is the much-studied AdS/CFT correspondence. Unfortunately, it seems that we live in a universe with a positive cosmological constant which will look like de Sitter space-time in the far future. Therefore, we should try to understand quantum gravity or string theory in de Sitter space preferably in a holographic way. Of course, physics in de Sitter space is interesting even without its connection to the real world; de Sitter entropy and temperature have always been mysterious aspects of quantum gravity.
While string theory successfully has addressed the problem of entropy for black holes, dS entropy remains a mystery. One reason is that the finite entropy seems to suggest that the Hilbert space of quantum gravity for asymptotically de Sitter space is finite dimensional, . Another, related, reason is that the horizon and entropy in de Sitter space have an obvious observer dependence. For a black hole in flat space (or even in AdS) we can take the point of view of an outside observer who can assign a unique entropy to the black hole. The problem of what an observer venturing inside the black hole experiences, is much more tricky and has not been given a satisfactory answer within string theory. While the idea of black hole complementarity provides useful clues, , rigorous calculations are still limited to the perspective of the outside observer. In de Sitter space there is no way to escape the problem of the observer dependent entropy. This contributes to the difficulty of de Sitter space.
More recently, it has been proposed that defined in a manner analogous to the AdS/CFT correspondence, quantum gravity in a de Sitter (dS) space is dual to a certain Euclidean CFT living on a spacelike boundary of the dS space  (see also earlier works -). Following the proposal, some investigations on the dS space have been carried out recently -. According to the dS/CFT correspondence, it might be expected that as the case of AdS black holes , the thermodynamics of cosmological horizon in asymptotically dS spaces can be identified with that of a certain Euclidean CFT residing on a spacelike boundary of the asymptotically dS spaces.
One of the remarkable outcomes of the AdS/CFT and dS/CFT correspondence has been the generalization of Cardy’s formula (Cardy-Verlinde formula) for arbitrary dimensionality, as well as a variety AdS and dS backgrounds. In this paper, we will show that the entropy of cosmological horizon in the 4-dimensional Topological Kerr-Newman-de Sitter spaces (TKNdS) can also be rewritten in the form of Cardy-Verlinde formula. We then show that if one uses the Abbott and Deser (AD) prescription , the entropy of black hole horizons in dS spaces can also be expressed by the Cardy-Verlinde formula . In a previous paper , we have shown that the entropy of cosmological horizon in Topological Reissner-Nordström- de Sitter spaces in arbitrary dimension can be described by the Cardy-Verlinde formula. Each of these cases is found to have interesting implications in the context of the proposed correspondence. The Cardy-Verlinde formula in 4-dimensional Kerr-Newman-de Sitter has been studied previously in  (the dS/CFT correspondence have considered for the three-dimensional Kerr-de Sitter space already at ), In the KNdS case the cosmological horizon geometry is spherical, also the black hole have two event horizon, but in the TKNdS case the cosmological horizon geometry is spherical, flat and hyperbolic for k=1,0,-1, respectively, also for the case k=0,-1 the black hole have not event horizon. In the other hand the entropy of such spaces come from both cosmological and event horizon, then absence of event horizon or existanc of extra cosmological horizon change the result for the total entropy.

## 2 Topological Kerr-Newman-de Sitter Black Holes

The line element of TKNdS black holes in 4-dimension is given by

$`ds^2`$ $`=`$ $`{\displaystyle \frac{\mathrm{\Delta }_r}{\rho ^2}}\left(dt{\displaystyle \frac{a}{\mathrm{\Xi }}}\mathrm{sin}^2\theta d\varphi \right)^2+{\displaystyle \frac{\rho ^2}{\mathrm{\Delta }_r}}dr^2+{\displaystyle \frac{\rho ^2}{\mathrm{\Delta }_\theta }}d\theta ^2`$ (1)
$`+{\displaystyle \frac{\mathrm{\Delta }_\theta \mathrm{sin}^2\theta }{\rho ^2}}\left[adt{\displaystyle \frac{(r^2+a^2)}{\mathrm{\Xi }}}d\varphi \right]^2,`$
where

$`\mathrm{\Delta }_r`$ $`=`$ $`(r^2+a^2)\left(k{\displaystyle \frac{r^2}{l^2}}\right)2Mr+q^2,`$
$`\mathrm{\Delta }_\theta `$ $`=`$ $`1+{\displaystyle \frac{a^2\mathrm{cos}^2\theta }{l^2}},`$
$`\mathrm{\Xi }`$ $`=`$ $`1+{\displaystyle \frac{a^2}{l^2}},`$
$`\rho ^2`$ $`=`$ $`r^2+a^2\mathrm{cos}^2\theta .`$ (2)
here the parameters $`M`$, $`a`$, and $`q`$ are associated with the mass, angular momentum, and electric charge parameters of the space-time, respectively. The topological metric Eq.(1) will only solve the Einstein equations if k=1, which is the spherical topology. In fact when $`k=1`$, the metric Eq.(1) is just the Kerr-Newman -de Sitter solution. Three real roots of the equation $`\mathrm{\Delta }_r=0`$, are the location of three horizon, the largest on is the cosmological horizon $`r_c`$, the smallest is the inner horizon of black hole, the one in between is the outer horizon $`r_b`$ of the black hole.
If we want the $`k=0,1`$ cases solve the Einstein equations, then we must set $`sin\theta \theta `$, and $`sin\theta sinh\theta `$ respectively -. When $`k=0`$ or $`k=1`$, there is only one positive real root of $`\mathrm{\Delta }_r`$, and this locates the position of cosmological horizon $`r_c`$. When $`q=0`$, $`a=0`$ and $`MM`$ the metric Eq.(1)is the TdS (Topological de Sitter) solution , which have a cosmological horizon and a naked singularity, for this type of solution, the Cardy-Verlinde formula also work well.
Here we review the BBM prescription  for computing the conserved quantities of asymptotically de Sitter spacetimes briefly. In a theory of gravity, mass is a measure of how much a metric deviates near infinity from its natural vacuum behavior; i.e, mass measures the warping of space. Inspired by the analogous reasoning in AdS space  one can construct a divergence-free Euclidean quasilocal stress tensor in de Sitter space by the response of the action to variation of the boundary metric, in 4-dimensional spacetime we have

$`T^{\mu \nu }`$ $`=`$ $`{\displaystyle \frac{2}{\sqrt{h}}}{\displaystyle \frac{\delta I}{\delta h_{\mu \nu }}}={\displaystyle \frac{1}{8\pi G}}[K^{\mu \nu }Kh^{\mu \nu }+{\displaystyle \frac{2}{l}}h^{\mu \nu }+lG^{\mu \nu }],`$ (3)
where $`h^{\mu \nu }`$ is the metric induced on surfaces of fixed time, $`K_{\mu \nu }`$, $`K`$ are respectively extrinsic curvature and its trace, $`G^{\mu \nu }`$ is the Einstein tensor of the boundary geometry. To compute the mass and other conserved quantities, one can write the metric $`h^{\mu \nu }`$ in the following form

$$h_{\mu \nu }dx^\mu dx^\nu =N_\rho ^2d\rho ^2+\sigma _{ab}(d\varphi ^a+N_\mathrm{\Sigma }^ad\rho )(d\varphi ^b+N_\mathrm{\Sigma }^bd\rho )$$
(4)
where the $`\varphi ^a`$ are angular variables parametrizing closed surfaces around the origin. When there is a Killing vector field $`\xi ^\mu `$ on the boundary, then the conserved charge associated to $`\xi ^\mu `$ can be written as

$$Q=_\mathrm{\Sigma }d^2\varphi \sqrt{\sigma }n^\mu \xi ^\mu T_{\mu \nu }$$
(5)
where $`n^\mu `$ is the unit normal vector on the boundary, $`\sigma `$ is the determinant of the metric $`\sigma _{ab}`$. Therefore the mass of an asymptotically de Sitter space in 4-dimension is as

$$M=_\mathrm{\Sigma }d^2\varphi \sqrt{\sigma }N_\rho ϵ;ϵn^\mu n^\nu T_{\mu \nu },$$
(6)
where Killing vector normalized as $`\xi ^\mu =N_\rho n^\mu `$. Using this prescription , the gravitational mass, subtracted the anomalous Casimir energy, of the 4-dimensional TKNdS solution is

$$E=\frac{M}{\mathrm{\Xi }}.$$
(7)
Where the parameter $`M`$ can be obtain from equation $`\mathrm{\Delta }_r=0`$. On this basis, the following relation for the gravitational mass can be obtained

$$E=\frac{M}{\mathrm{\Xi }}=\frac{(r_c^2+a^2)(r_c^2kl^2)q^2l^2}{2\mathrm{\Xi }r_cl^2}.$$
(8)
The Hawking temperature of the cosmological horizon given by

$$T_c=\frac{1}{4\pi }\frac{\mathrm{\Delta }_r^{}(r_c)}{(r_c^2+a^2)}=\frac{3r_c^4+r_c^2(a^2kl^2)+(ka^2+q^2)l^2}{4\pi r_cl^2(r_c^2+a^2)}.$$
(9)
The entropy associated with the cosmological horizon can be calculated as

$$S_c=\frac{\pi (r_c^2+a^2)}{\mathrm{\Xi }}.$$
(10)
The angular velocity of the cosmological horizon is given by

$$\mathrm{\Omega }_c=\frac{a\mathrm{\Xi }}{(r_c^2+a^2)}.$$
(11)
The angular momentum $`J_c`$, the electric charge $`Q`$, and the electric potentials $`\varphi _{qc}`$ and $`\varphi _{qc0}`$ are given by

$`𝒥_c={\displaystyle \frac{Ma}{\mathrm{\Xi }^2}},`$
$`Q={\displaystyle \frac{q}{\mathrm{\Xi }}},`$
$`\mathrm{\Phi }_{qc}={\displaystyle \frac{qr_c}{r_c^2+a^2}},`$
$`\mathrm{\Phi }_{qc0}={\displaystyle \frac{q}{r_c}},`$ (12)
The obtained above quantities of the cosmological horizon satisfy the first law of thermodynamics

$$dE=T_cdS_c+\mathrm{\Omega }_cd𝒥_c+(\mathrm{\Phi }_{qc}+\mathrm{\Phi }_{qc0})dQ.$$
(13)
Using the Eqs.(10,12) for cosmological horizon entropy, angular momentum and charge, also equation $`\mathrm{\Delta }_r(r_c)=0`$, we can obtain the mtric parameters $`M`$, $`a`$, $`q`$ as a function of $`S_c`$, $`𝒥_c`$ and $`Q`$, after that we can write $`E`$ as a function of these thermodynamical quantities $`E(S_c,𝒥_c,Q)`$ (see ). Then one can define the quantities conjugate to $`S_c`$, $`𝒥_c`$ and $`Q`$, as

$$T_c=\left(\frac{E}{S_c}\right)_{J_c,_Q},\mathrm{\Omega }_c=\left(\frac{E}{J_c}\right)_{S_c,Q},\mathrm{\Phi }_{qc}=\left(\frac{E}{Q}\right)_{S_c,J_c}\mathrm{\Phi }_{qc0}=lim_{a0}\left(\frac{E}{Q}\right)_{S_c,J_c}$$
(14)
Making use of the fact that the metric for the boundary CFT can be determined only up to a conformal factor, we rescale the boundary metric for the CFT to be the following form

$$ds_{CFT}^2=\underset{r\mathrm{}}{lim}\frac{R^2}{r^2}ds^2,$$
(15)
Then the thermodynamic relations between the boundary CFT and the bulk TKNdS are given by

$$E_{CFT}=\frac{l}{R}E,T_{CFT}=\frac{l}{R}T,J_{CFT}=\frac{l}{R}J,\varphi _{CFT}=\frac{l}{R}\varphi ,\varphi _{0CFT}=\frac{l}{R}\varphi _0,$$
(16)
The Casimir energy $`E_c`$, defined as $`E_C=(n+1)En(T_cS_c+J_c\mathrm{\Omega }_c+Q/2\varphi _{qc}+Q/2\varphi _{qc0})`$ , and $`n=2`$ in this case, is found to be

$$E_C=\frac{k(r_c^2+a^2)l}{R\mathrm{\Xi }r_c},$$
(17)
in KNdS space case  the Casimir energy $`E_c`$ is always negative, but in TKNdS space case Casimir energy can be positive, negative or vanishing depending on the choice of $`k`$. Thus we can see that the entropy Eq.(10)of the cosmological horizon can be rewritten as

$$S=\frac{2\pi R}{n}\sqrt{|\frac{E_c}{k}|(2(EE_q)E_c)},$$
(18)
where

$$E_q=\frac{1}{2}\varphi _{c0}Q.$$
(19)
We note that the entropy expression (18) has a similar form as the case of TRNdS black holes .
For the black hole horizon, which there is only for the case $`k=1`$ associated thermodynamic quantities are

$$T_b=\frac{1}{4\pi }\frac{\mathrm{\Delta }_r^{}(r_b)}{(r_b^2+a^2)}=\frac{3r_b^4+r_b^2(a^2l^2)+(a^2+q^2)l^2}{4\pi r_bl^2(r_b^2+a^2)}.$$
(20)
$$S_b=\frac{\pi (r_b^2+a^2)}{\mathrm{\Xi }}.$$
(21)
$$\mathrm{\Omega }_b=\frac{a\mathrm{\Xi }}{(r_b^2+a^2)}.$$
(22)
$$𝒥_b=\frac{Ma}{\mathrm{\Xi }^2},$$
(23)
$$Q=\frac{q}{\mathrm{\Xi }},$$
(24)
$$\mathrm{\Phi }_{qb}=\frac{qr_b}{r_b^2+a^2},$$
(25)
$$\mathrm{\Phi }_{qb0}=\frac{q}{r_b}.$$
(26)
Now if we uses the BBM mass Ee.(7) the black hole horizon entropy cannot be expressed by a form like Cardy-Verlinde formula . The other way for computing conserved quantities of asymptotically de Sitter space is Abbott and Deser (AD) prescription . According to this prescription, the gravitational mass of asymptotically de Sitter space coincides with the ADM mass in asymptotically flat space, when the cosmological constant goes to zero. Using the AD prescription for calculating conserved quantities the black hole horizon entropy of TKNdS space can be expressed in term of Cardy-Verlind formula . The AD mass of TKNdS solution can be expressed in terms of black hole horizon radius $`r_b`$, $`a`$ and charge $`q`$,

$$E^{}=\frac{M}{\mathrm{\Xi }}=\frac{(r_b^2+a^2)(r_b^2l^2)q^2l^2}{2\mathrm{\Xi }r_bl^2}.$$
(27)
The obtained above quantities of the black hole horizon also satisfy the first law of thermodynamics as

$$dE^{}=T_bdS_b+\mathrm{\Omega }_bd𝒥_b+(\mathrm{\Phi }_{qb}+\mathrm{\Phi }_{qb0})dQ.$$
(28)
The thermodynamics quantities of the CFT must be rescaled by a factor $`\frac{l}{R}`$ similar to the pervious case. In this case, the Casimir energy, defined as $`E_C^{}=(n+1)E^{}n(T_bS_b+J_b\mathrm{\Omega }_b+Q/2\varphi _{qb}+Q/2\varphi _{qb0})`$, is

$$E_C^{}=\frac{(r_b^2+a^2)l}{R\mathrm{\Xi }r_b},$$
(29)
and the black hole entropy $`S_b`$ can be rewritten as

$$S_b=\frac{2\pi R}{n}\sqrt{E_C^{}|(2(E^{}E_q^{})E_C^{})|},$$
(30)
where

$$E_q^{}=\frac{1}{2}\varphi _{qb0}Q.$$
(31)
which is the energy of electromagnetic field outside the black hole horizon. Thus we demonstrate that the black hole horizon entropy of TKNdS solution can be expressed in a form as the Cardy-Verlinde formula. However, if one uses the BBM mass Eq.(8) the black hole horizon entropy $`S_b`$ cannot be expressed by a form like the Cardy-Verlinde formula. Our result is in favour of the dS/CFT correspondence.

## 3 Conclusion

The Cardy-Verlinde formula recently proposed by Verlinde , relates the entropy of a certain CFT to its total energy and Casimir energy in arbitrary dimensions. In the spirit of dS/CFT correspondence, this formula has been shown to hold exactly for the cases of dS Schwarzschild, ds topological, ds Reissner-Nordström , dS Kerr, and dS Kerr-Newman black holes. In this paper we have further checked the Cardy-Verlinde formula with topological Kerr-Newman de Sitter black hole.
It is well-known that there is no black hole solution whose event horizon is not sphere, in de Sitter background although there are such solutions in anti-de Sitter background, then in TKNdS space for the case k=0,-1 the black hole have not event horizon, however the cosmological horizon geometry is spherical, flat and hyperbolic for k=1,0,-1, respectively. As we have shown there exist two different temperature and entropy associated with the cosmological horizon and black hole horizon, in TKNdS spacetimes. If the temperatures of the black hole and cosmological horizon are equal, then the entropy of system is the sum of entropies of cosmological and black hole horizons. The geometric features of black hole temperature and entropy seem to imply that the black hole thermodynamics is closely related to nontrivial topological structure of spacetime. In  Cai, et al in order to relate the entropy with Euler characteristic $`\chi `$ of the corresponding Euclidean manifolds have been presented the following relation

$$S=\frac{\chi _1A_{BH}}{8}+\frac{\chi _2A_{CH}}{8},$$
(32)
in which the Euler number of the manifolds divided into two parts, one first part comes from the black hole horizon and the second part come from the cosmological horizon (see also ). If one uses the BBM mass of the asymptotically dS spaces, the black hole horizon entropy cannot be expressed by a form like the Cardy-Verlinde formula. In this paper, we have found that if one uses the AD prescription to calculate conserved charges of asymptotically dS spaces, the TKNdS black hole horizon entropy can also be rewritten in a form of Cardy-Verlinde formula, which indicates that the thermodynamics of black hole horizon in dS spaces can be also described by a certain CFT. Our result is also reminiscent of the Carlip’s claim (to see new formulation which is free of inconsistencies encountered in Carlip’s ref.) that for black holes in any dimension the Bekenstein-Hawking entropy can be reproduced using the Cardy formula . Also we have shown that the Casimir energy for cosmological horizon in TKNdS space case can be positive, negative or vanishing depending on the choice of $`k`$, by contrast the Casimir energy for cosmological horizon in KNdS space is always negative .

## Acknowledgement

We would like to thank Prof. Robert Mann for useful comments and suggestions.


text:
# Multicanonical Chain Growth Algorithm

## Abstract

We present a temperature-independent Monte Carlo method for the determination of the density of states of lattice proteins that combines the fast ground-state search strategy of the nPERM chain growth and multicanonical reweighting for sampling the complete energy space. Since the density of states contains all energetic information of a statistical system, we can directly calculate the mean energy, specific heat, Gibbs free energy, and entropy for all temperatures. We apply this method to HP lattice proteins and for the examples of sequences considered, we identify the transitions between native, globule, and random coil states. Since no special properties of heteropolymers are involved in this algorithm, the method applies to polymer models as well.

The simulation of protein folding is extremely challenging, since the interactions between the constituents of the macromolecule and the influence of the environment require sophisticated models. One of the most essential aspects in the description of the folding process is the formation of a compact core of hydrophobic amino acid residues (H) which is screened from water by hydrophilic or polar residues (P). This characteristic property of realistic proteins can be qualitatively studied with simple lattice models such as the HP model . By taking into account the attractive interaction between hydrophobic monomers only, the energy of a lattice protein with certain conformation and sequence is calculated as follows:

$$E=\underset{i,j<i1}{}\sigma _i\sigma _j,$$
(1)
where $`i,j<i1`$ symbolises that the sum is taken only over nearest lattice neighbours being nonadjacent along the self-avoiding chain of monomers. If the $`i`$th monomer is hydrophobic, $`\sigma _i=1`$, while for a polar monomer $`\sigma _i=0`$.

As it is one of the main goals in off-lattice simulations to find low-lying energy states within a rough free energy landscape, good lattice folders are expected to have low-degenerated ground states. Much work has been done on identifying designing sequences with such native states. Ground-state search strategies on three-dimensional lattices range, for example, from enumeration  over hydrophobic core construction  and contact interaction  to chain growth methods . Low-lying energy states for HP sequences with up to 136 monomers were identified with these methods.

In contrast, there were only few attempts to study the thermodynamic properties of the HP model in three dimensions . The main reason is that conventional Monte Carlo methods like Metropolis sampling, but also more sophisticated methods like simulated  and parallel  tempering as well as histogram reweighting Monte Carlo algorithms such as multicanonical sampling  or the Wang-Landau method  expose problems in tackling “hidden” conformational barriers in combination with chain update moves which become usually inefficient at low temperatures, where many attempted moves are rejected due to the self-avoidance constraint. One possibility to update the conformation is to apply move sets. Widely used sets usually consist of operations that change a single bond (end flips), two bonds (corner flips), three (crankshaft) or even more bonds, and pivot rotations, where the $`i`$th monomer serves as pivot point and one of the two partial chains connected with it is rotated about any axis through the pivot. Unfortunately, the more dense the conformation, the more inefficient this procedure becomes.

Alternatively, it is possible to let the polymer grow, i.e., the $`n`$th monomer is placed at a randomly chosen next-neighbour site of the $`(n1)`$th monomer ($`nN`$ with $`N`$ being the total length of the polymer). If this new site is already occupied, the entire chain would have to be discarded to obtain correct statistics. This simple chain growth is not efficient, since the number of discarded chains grows exponentially with the chain length. Rosenbluth chain growth  avoids occupied neighbours at the expense of a bias, since the probability of such a chain is $`p_n\left(_{l=2}^nm_l\right)^1`$, where $`m_l`$ is the number of free lattice sites to place the $`l`$th monomer. This bias is balanced out by assigning each conformation a Rosenbluth weight $`W_n^\mathrm{R}p_n^1`$. Chain growth methods with population control such as PERM (Pruned-Enriched Rosenbluth Method)  and its recent modifications nPERM$`{}_{\mathrm{is}}{}^{}{}_{}{}^{\mathrm{ss}}`$  improve this procedure considerably by utilising the counterbalance between Rosenbluth weight and Boltzmann probability. The weight factor $`W_n^\mathrm{R}`$ is therefore replaced by

$`W_n^{\mathrm{PERM}}={\displaystyle \underset{l=2}{\overset{n}{}}}m_le^{(E_lE_{l1})/k_BT},`$ (2)
$`2nN(E_1=0,W_1^{\mathrm{PERM}}=1),`$ (3)
where $`E_l`$ is the energy of the partial chain $`𝐗_l=(𝐱_1,\mathrm{},𝐱_l)`$ created with Rosenbluth chain growth and $`T`$ is the temperature.

To explain the main ideas, we shall confine ourselves for the moment to the original PERM formulation , where the sample of chains of length $`n`$ is enriched by making identical copies once $`W_n^{\mathrm{PERM}}`$ is bigger than a certain threshold value $`W_n^>`$. In this case, the weight $`W_n^{\mathrm{PERM}}`$ is divided among the clones. For $`W_n^{\mathrm{PERM}}`$ being smaller than a lower bound $`W_n^<`$, the chain is pruned with probability $`1/2`$ and the weight of a surviving chain is doubled. The partition sum is proportional to the sum of weight factors (2) for the conformations $`𝐗_{n,t}`$ of length $`n`$ sampled at “time” $`t`$,

$$Z_n\underset{t}{}W_n^{\mathrm{PERM}}(𝐗_{n,t}).$$
(4)
The PERM algorithms are very successful as ground-state searchers and the canonical distribution at a given temperature $`T`$ is well reproduced over some orders of magnitude, but states that are highly suppressed at this temperature are not hit in a reasonable time. Standard reweighting techniques are applicable only in a small region around $`T`$. Thus, recording temperature-dependent quantities such as the specific heat requires simulations at different temperatures.

As the partition sum of a polymer or a heteropolymer with fixed sequence can be expressed in terms of the density (or degeneracy) of states $`g(E)`$, $`Z=_{\{𝐱\}}e^{\beta E(\{𝐱\})}=_ig(E_i)e^{\beta E_i}`$ ($`\beta 1/k_BT`$), all energetic quantities such as the mean energy $`E(T)=(/\beta )\mathrm{ln}Z`$, the specific heat $`C_V(T)=\left(E^2E^2\right)/k_BT^2`$, Gibbs free energy $`F(T)=k_BT\mathrm{ln}Z`$, and entropy $`S(T)=\left(EF\right)/T`$ can directly be calculated if the density of states is known. These quantities are of particular interest, since they are indicators of temperature-dependent conformational transitions.

Our method allows within one simulation the direct sampling of the density of states $`g(E)`$ over the entire range of the energy space with probabilities ranging over many orders of magnitude, due to combining the advantages of energetic flat histogram reweighting at infinite temperature and chain growth. The flat distribution can then be reweighted to any desired temperature. Rare, i.e. low-lying energy states are also hit and therefore the low-temperature behaviour of the polymer can be reproduced well, in particular the low-temperature transition between compact globules and ground states of lattice proteins with low ground-state degeneracy. Using the HP model, we applied the method to lattice proteins with more than 40 monomers and different ground-state degeneracies and found for examples with low ground-state degeneracy pronounced low-temperature peaks in the specific heat indicating ground-state – globule transitions. Since our method is completely general, it is also applicable to other polymer models.

In order to achieve a flat distribution of energetic states using chain growth, we introduce into the partition sum (4) an additional weight $`W_n^{\mathrm{flat}}(E_n(𝐗_n))`$ that depends on the energy $`E_n`$ of a given conformation $`𝐗_n=(𝐱_1,\mathrm{},𝐱_n)`$:

$`Z_n{\displaystyle \underset{t}{}}W_n^{\mathrm{PERM}}(𝐗_{n,t})`$ (5)
$`\times W_n^{\mathrm{flat}}(E_n(𝐗_{n,t}))\left[W_n^{\mathrm{flat}}(E_n(𝐗_{n,t}))\right]^1.`$ (6)
Since the histograms at all intermediate stages of the chain growth process are required to be flat, the new reweighting factor is rewritten in product form and we have

$`Z_n{\displaystyle \underset{t}{}}\left[W_n^{\mathrm{flat}}(E_n)\right]^1`$ (7)
$`\times {\displaystyle \underset{l=2}{\overset{n}{}}}m_le^{(E_lE_{l1})/k_BT}{\displaystyle \frac{W_l^{\mathrm{flat}}(E_l)}{W_{l1}^{\mathrm{flat}}(E_{l1})}}`$ (8)
with $`W_1^{\mathrm{flat}}=1`$. The PERM weight factors (2) lead to a canonical distribution $`P_n^{\mathrm{can},T}(E_n)`$ which shall be deformed to a constant distribution $`P_n^{\mathrm{flat},T}(E_n)`$ over the entire energy space. This requires the weights $`W_n^{\mathrm{flat}}`$ to be proportional to the inverse of the canonical distribution, $`W_n^{\mathrm{flat}}1/P_n^{\mathrm{can},T}(E_n)`$, a condition that can obviously only be satisfied iteratively . As we are mainly interested in the density of states, which is proportional to the canonical probability distribution at $`\beta =1/k_BT=0`$, $`g_n(E_n)P_n^{\mathrm{can},\mathrm{}}(E_n)`$, we will effectively perform the simulation at infinite temperature. Consequently, $`W_n^{\mathrm{flat}}1/g_n(E_n)`$ and $`Z_n_tg_n(E_n(𝐗_{n,t}))W_n(𝐗_{n,t})`$. Here we have introduced the combined weight

$$W_n(𝐗_n)=\underset{l=2}{\overset{n}{}}m_l\frac{g_l^1(E_l)}{g_{l1}^1(E_{l1})},W_1=g_1=1,$$
(9)
which can also be written recursively, $`W_n=W_{n1}m_ng_n^1(E_n)/g_{n1}^1(E_{n1})`$. The canonical mean value of any quantity $`O_n(𝐗_n)`$ is then calculated as follows:

$`O_n_{\mathrm{can}}`$ $`=`$ $`{\displaystyle \frac{\underset{t}{}O_n(𝐗_{n,t})g_n(E_n(𝐗_{n,t}))W_n(𝐗_{n,t})}{\underset{t}{}g_n(E_n(𝐗_{n,t}))W_n(𝐗_{n,t})}}`$ (10)
$`=`$ $`{\displaystyle \frac{O_ng_n(E_n)_{\mathrm{flat}}}{g_n(E_n)_{\mathrm{flat}}}},`$ (11)
where we have used mean values according to the flat distribution $`\mathrm{}_{\mathrm{flat}}=_t\mathrm{}W_n(𝐗_{n,t})/Z_n^{\mathrm{flat}}`$ with the partition sum of the flat distribution $`Z_n^{\mathrm{flat}}=_tW_n(𝐗_{n,t})`$. The most important technical part of the algorithm is the determination of the weights $`W_n^{\mathrm{flat}}`$, since they are directly connected with the desired densities of states $`g_n(E)`$. As the weights are completely unknown in the beginning, we evaluate them iteratively, starting from unity, $`W_n^{\mathrm{flat},(0)}(E)=1`$ ($`2nN`$) for all values of $`E`$. This means that the zeroth iteration is a pure chain growth run without reweighting.

Each time, a chain of length $`n`$ with energy $`E`$ is created, the corresponding histogram value $`h_n(E)`$ is increased by the weight $`W_n`$ of the chain. If a certain number of chains with total length $`N`$ was produced, the iteration is finished and the new weights $`W_n^{\mathrm{flat},(i)}(E)`$ are determined by calculating $`W_n^{\mathrm{flat},(i)}(E)=W_n^{\mathrm{flat},(i1)}(E)/h_n(E)`$, $`2nN`$. Before the next iteration starts, the histogram is reset, $`h_n(E)=0`$. The correct weights are found, when $`h_n(E)`$ is “flat”, i.e., it has approximately the same value for all energies. In our actual implementation we employed a suitably adapted multicanonical variant of nPERMis (new PERM with importance sampling) .

Before we present results obtained with the new algorithm, we discuss general properties of heteropolymers exemplified for 14mers which can still be analysed by exact enumeration. Among all $`2^{14}`$ sequences for 14mers there is only one designing sequence, i.e. a sequence to which a unique ground state belongs (up to a reflection symmetry).

We compared thermodynamic properties of four 14mers with different sequences but same hydrophobicity ($`n_H=8`$) and identical lowest energy ($`E_{\mathrm{min}}=8`$). Figure 1 shows the specific heat for the different 14mers. A pronounced low-temperature peak that indicates the transition between ground states and compact globule states is only observed for the 14mer with the native ground state, 14.1. These results show qualitatively how the conformational transitions depend on the ground-state degeneracy $`g_0`$ of the polymer. For the sequences 14.2 and 14.3 it is twice that of the designing sequence, and 14.4 is even four times higher degenerate.

The first example to which we applied our multicanonical chain growth algorithm is a 42mer with the sequence PH2PHPH2PHPHP2H3PHPH2PHPH3P2HPHPH2PHPH2P whose ground-state properties have similarities with the parallel $`\beta `$-helix of pectate lyase C . The lattice model with only four-fold ground-state degeneracy has a ground-state energy of $`E_{\mathrm{min}}=34`$. In order to investigate the low-temperature behaviour of this system it is necessary that the algorithm correctly samples the low-energy states and that it also hits the ground states. The measured density of states ranges over about 25 orders of magnitude and covers the entire energy space $`[34,0]`$, as shown in Fig. 2.

Figure 3(a) shows the results for the heat capacity and the mean energy. Writing out the raw energies and weights from the simulation, we analysed the data and calculated the statistical error by means of the jackknife blocking method. Due to the low degeneracy of the ground states, the transition between native states and globule states is very pronounced and occurs at a temperature $`T_00.27`$. The globule – random coil transition at $`T_10.53`$, on the other hand, is rather weak. This confirms the results of Ref. . From the density of states, we also obtain the Gibbs free energy $`F(T)`$ and the entropy $`S(T)`$. Since the ground-state degeneracy $`g_0`$ is not accessible by stochastic search algorithms in general, we have plotted in Fig. 3(b) the reduced free energy $`\stackrel{~}{F}(T)=F(T)+TS_0`$ and the entropy $`\stackrel{~}{S}(T)=S(T)S_0`$, up to the constant $`S_0=\mathrm{ln}g_0`$, where $`g_0`$ is the degeneracy of the ground state.

Finally, similar to the consideration of the 14mers, we compare two 48mers with different ground-state properties. The first one, which we denote by $`48.1`$ has the sequence PHPH2PH6P2HPHP2HPH2PHPHP3HP2H2P2H2P2HPHP2HP and its ground state with the energy $`34`$ is $`5000`$-fold degenerate. The ground state of the other 48mer ($`48.2`$) with the sequence HPH2P2H4PH3P2H2P2HPH3PHPH2P2H2P3HP8H2 has the much higher degeneracy of $`1.5\times 10^6`$ and possesses the energy $`32`$ . As is demonstrated in Fig. 4, we also observe for these longer chains that the conformational transition between the lowest-energy states and the globules is stronger the lower the ground-state degeneracy is.

In conclusion, we have developed a multicanonical chain growth algorithm that allows the simulation of the thermodynamic properties of polymers and heteropolymers. It is based on energetic flat histogram sampling of the density of states in combination with PERM chain growth. We applied this algorithm to heteropolymers with more than 40 monomers and obtained accurate densities of states over about 25 orders of magnitude that cover the entire energy range, thus yielding very good results for all derived energetic quantities such as mean energy, specific heat, free energy, and entropy. In particular, this enabled us to determine the low-temperature behaviour of the systems with high precision and to observe pronounced low-temperature peaks of the specific heat for lattice proteins with low ground-state degeneracy indicating the ground-state – globule transition.
We thank Peter Grassberger and Hsiao-Ping Hsu for helpful discussions on the new PERM algorithms. This work is partially supported by the German-Israel-Foundation (GIF) under contract No. I-653-181.14/1999.


text:
# Commitment Capacity of Discrete Memoryless Channels

## 1 Introduction

Chess masters Alice and Bob are playing for the world chess championship and, after playing for several hours, realize that they will have to stop the game and resume it on the next morning. However, a problem arises: if Alice plays her turn before stopping the game, Bob will have the entire night to think of his next move, giving him an unfair advantage. If Alice does not play, she will have the entire night to thing of her move. How can they get out of this problem?

If there is a trusted referee, Alice can write down her move and put it into an envelope and give it to the referee, who will announce it to Bob in the next morning. As the referee is trusted, Alice will be unable to change her move after writing it down, also Bob will be unable to learn Alice’s move before the next morning. Can Alice and Bob solve this problem without the help of a trusted referee?

To solve these kind of problems without the use of an active trusted party, Blum introduced commitment schemes in . In a commitment scheme, Alice commits to an information by sending some piece of information to Bob during a commit phase. Later on, she can unveil the information she committed to by sending some opening information to Bob during an unveiling (also called reveal) phase. The protocol is said to be concealing if the information sent by Alice during the commit phase does not help Bob to learn a non–negligible amount of information on the value Alice is committing to. It is said to be binding if Alice is unable to commit to a certain information (which is usually a string of bits) and later on unveil a different one.

Without any kind of computational assumptions and assuming noiseless communications, commitment schemes are impossible (see e.g. ; the generalisation to quantum protocols is due to Mayers ). Therefore, research has mostly focused on schemes were the receiver is computationally bounded (computationally concealing schemes) or schemes were the sender is computationally bounded (computationally binding schemes). Examples of computationally binding but unconditionally concealing schemes are  and . Examples of computationally concealing but unconditionally binding schemes are  and .

It is now known that noise is a powerful resource for the implementation of cryptographic primitives: it allows for the construction of *information theoretically secure* cryptographic protocols — a task typically impossible without the noise, and in practice done by relaxing to *computational security*, assuming conjectures from complexity theory.

In his famous paper , Wyner was the first to exploit noise in order to establish a secure channel in the presence of an eavesdropper. These results were extended in studies of secret key distillation by Maurer , Ahlswede and Csiszár  and followers. The noise in these studies is assumed to affect the eavesdropper: thus, to work in practice, it has to be guaranteed or certified somehow. This might be due to some — trusted — third party who controls the channel (and thus prevents the cryptographic parties from cheating), or due to physical limitations, as in quantum key distribution . Recently, Crépeau and Kilian  showed how information theoretically secure bit commitment can be implemented using a binary symmetric channel, their results being improved in  and .

The object of the present study is to optimise the use of the noisy channel, much as in Shannon’s theory of channel capacities: while the previous studies have concentrated on the *possibility* of bit commitment using noisy channels, here we look at committing to one out of a larger message set, e.g. a bit string. We are able, for a general discrete memoryless channel, to characterise the commitment capacity by a simple (single–letter) formula (theorem 2), stated in section 2, and proved in two parts in sections 3 and 4. A few specific examples are discussed in section 5 to illustrate the main result. In section 6 results on an extension to quantum channels are related, and we close with a discussion (section 7). An appendix collects some facts abut typical sequences used in the main proof.

## 2 Definitions and main result

In the commitment of a message there are two parties, called *Alice* and *Bob*, the first one given the message $`a`$ from a certain set $`𝒜`$. The whole procedure consists of two stages: first the *commit phase*, in which Alice (based on $`a`$) and Bob exchange messages, according to a protocol. This will leave Bob with a record (usually called *view*), to be used in the second stage, the *reveal phase*. This consists of Alice disclosing $`a`$ and other relevant information to Bob. Bob performs a test on all his recorded data which accepts if Alice followed the rules and disclosed the correct information in the second stage, and rejects if a violation of the rules is discovered.

To be useful, such a scheme has to fulfill two requirements: it must be “concealing” as well as “sound” and “binding”: the first property means that after the commit phase Bob has no or almost no information about $`a`$ (i.e., even though Alice has “committed” herself to something by the communications to Bob, this commitment remains secret), and this has to hold even if Bob does not follow the protocol, while Alice does. Soundness means that if both parties behave according to the protocol, Bob’s test will accept (with high probability) after the reveal phase. The protocol to be binding means that Bob’s test is such that whatever Alice did in the commit phase (with Bob following the rules) there is only at most one $`a`$ she can “reveal” which passes Bob’s test.

In our present consideration there is an unlimited bidirectional noiseless channel available between Alice and Bob, and in addition a discrete memoryless noisy channel $`W:𝒳𝒵`$ from Alice to Bob, which may be used $`n`$ times: on input $`x^n=x_1\mathrm{}x_n`$, the output distribution on $`𝒵^n`$ is $`W_{x^n}^n=W_{x_1}\mathrm{}W_{x_n}`$.

###### Definition 1

The channel $`W`$ is called *non–redundant*, if none of its output distributions is a convex combination of its other output distributions:

$$yP\text{ s.t. }P(y)=0W_y\underset{x}{}P(x)W_x.$$

In geometric terms this means that all distributions $`W_x`$ are distinct extremal points of the polytope $`𝒲=\mathrm{conv}\{W_x:x𝒳\}`$, the convex hull of the output distributions within the probability simplex over $`𝒵`$. Clearly, we can make $`W`$ into a non–redundant channel $`\stackrel{~}{W}`$ by removing all input symbols $`x`$ whose output distribution $`W_x`$ is not extremal. The old channel can be simulated by the new one, because by feeding it distributions over input symbols one can generate the output distributions of the removed symbols.

The channel $`W`$ is called *trivial*, if after making it non–redundant its output distributions have mutually disjoint support. This means that from the output one can infer the input with certainty.

With this we can pass to a formal definition of a protocol: this, consisting of the named two stages, involves creation on Alice’s side of either messages intended for the noiseless channel, or inputs to the noisy channel, based on previous messages receive from Bob via the noiseless channel, which themselves are based on data received before, etc. Both agents may employ probabilistic choices, which we model by Alice and Bob each using a random variable, $`M`$ and $`N`$, respectively. This allows them to use *deterministic* functions in the protocol. Note that this makes all messages sent and received into well-defined random variables, *dependent on $`a`$*.

*Commit Phase:* The protocol goes for $`r`$ rounds of Alice–to–Bob and Bob–to–Alice noiseless communications $`U_j`$ and $`V_j`$. After round $`r_i`$ ($`r_1\mathrm{}r_nr`$) Alice will also send a symbol $`X_i`$ down the noisy channel $`W`$, which Bob receives as $`Z_i`$. Setting $`r_0=0`$ and $`r_{n+1}=r`$:
Round $`r_i+k`$ ($`1kr_{i+1}r_i`$): Alice sends $`U^{r_i+k}=f_{r_i+k}(a,M,V^{r_i+k1})`$ noiselessly. Bob answers $`V_{r_i+k}=g_{r_i+k}(Z^i,N,U^{r_i+k})`$, also noiselessly. After round $`r_i`$ and before round $`r_i+1`$ ($`1in`$), Alice sends $`X_i=F_i(a,M,V^{r_i})`$, which Bob receives as $`Z_i=W(X_i)`$.

*Reveal Phase:* A similar procedure as the Commit Phase, but without the noisy channel uses, including Alice’s sending $`a`$ to Bob. At the end of the exchange Bob performs a test as to whether to accept Alice’s behaviour or not. It is easily seen that this procedure can be simulated by Alice simply telling Bob $`a`$ and $`M`$, after which Bob performs his test $`\beta (Z^n,N,U^r;a,M)\{\mathrm{ACC},\mathrm{REJ}\}`$. I.e., requiring Alice to reveal $`M`$ and $`a`$ makes cheating for her only more difficult.

We shall, for technical reasons, impose the condition that the range of the variable $`U^r`$ is bounded:

$$\left|U^r\right|\mathrm{exp}(Bn),$$
(1)
with a constant $`B`$. Note that $`\mathrm{exp}`$ and $`\mathrm{log}`$ in this paper are always to basis $`2`$, unless otherwise stated.

Now, the mathematical form of the conditions for concealing as well as for soundness and binding is this: we call the above protocol *$`ϵ`$–concealing* if for any two messages $`a,a^{}𝒜`$ and any behaviour of Bob during the commit phase,

$$\frac{1}{2}\mathrm{Distr}_a(Z^nNU^r)\mathrm{Distr}_a^{}(Z^nNU^r)_1ϵ,$$
(A)
where $`\mathrm{Distr}_a(Z^nNU^r)`$ is the distribution of the random variables $`Z^nNU^r`$ after completion of the commit phase which Alice entered with the message $`a`$ and the randomness $`M`$, and with the $`\mathrm{}_1`$–norm $`_1`$; the above expression is identical to the total variational distance of the distributions. This is certainly the strongest requirement one could wish for: it says that no statistical test of Bob immediately after the commit phase can distinguish between $`a`$ and $`a^{}`$ with probability larger than $`ϵ`$. Note that $`V^r`$ is a function of $`Z^nNU^r`$, and hence could be left out in eq. (A). Assuming any probability distribution on the messages, $`a`$ is the value of a random variable $`A`$, and it is jointly distributed with all other variables of the protocol. Then, whatever Bob’s strategy,

$$I\left(AZ^nNU^r\right)ϵ^{}=H(2ϵ,12ϵ)+2nϵ(\mathrm{log}B+\mathrm{log}|𝒵|),$$
(A’)
where

$$I(XY)=H(X)+H(Y)H(XY)$$

is the (Shannon) mutual information between $`X`$ and $`Y`$, and

$$H(X)=\underset{x}{}\mathrm{Pr}\{X=x\}\mathrm{log}\mathrm{Pr}\{X=x\}$$

is the (Shannon) entropy of $`X`$ .

We call the protocol *$`\delta `$–sound and –binding* (*$`\delta `$–binding* for short), if for Alice and Bob following the protocol, for all $`a𝒜`$,

$$\mathrm{Pr}\left\{\beta (Z^nNU^r;aM)=\mathrm{ACC}\right\}1\delta ,$$
(B1)
and, whatever Alice does during the commit phase, governed by a random variable $`S`$ with values $`\sigma `$ (which determines the distribution of $`Z^nNU^r`$), for all $`A=a(S,V^r)`$, $`A^{}=a^{}(S,V^r)`$, $`\stackrel{~}{M}=\mu (S,V^r)`$ and $`\stackrel{~}{M}^{}=\mu ^{}(S,V^r)`$ such that $`AA^{}`$ with probability $`1`$,

$$\mathrm{Pr}\left\{\beta (Z^nNU^r;A\stackrel{~}{M})=\mathrm{ACC}\&\beta (Z^nNU^r;A^{}\stackrel{~}{M}^{})=\mathrm{ACC}\right\}\delta .$$
(B2)
Note that by convexity the cheating attempt of Alice is w.l.o.g. *deterministic*, which is to say that $`S`$ takes on only one value $`\sigma `$ with non-zero probability, hence $`\mathrm{Pr}\{S=\sigma \}=1`$.

We call $`\frac{1}{n}\mathrm{log}|𝒜|`$ the *(commitment) rate* of the protocol. A rate $`R`$ is said to be *achievable* if there exist commitment protocols for every $`n`$ with rates converging to $`R`$, which are $`ϵ`$–concealing and $`\delta `$–binding with $`ϵ,\delta 0`$ as $`n\mathrm{}`$. The *commitment capacity $`C_{\mathrm{com}}(W)`$* of $`W`$ is the supremum of all achievable rates.

The main result of this paper is the following theorem:

###### Theorem 2

The commitment capacity of the discrete channel $`W`$ (assumed to be non–redundant) is

$$C_{\mathrm{com}}(W)=\mathrm{max}\left\{H(X|Z):X,Z\text{ RVs, }\mathrm{Distr}(Z|X)=W\right\},$$

i.e., the maximal *equivocation* of the channel over all possible input distributions.

###### Corollary 3

Every non–trivial discrete memoryless channel can be used to perform bit commitment. $`\mathrm{}`$

By invoking the well–known reduction of coin tossing to bit commitment  we obtain:

###### Corollary 4

The channel $`W`$ can be used for secure two–party coin tossing at rate at least $`C_{\mathrm{com}}(W)`$. I.e., for the naturally defined coin tossing capacity $`C_{\mathrm{c}.\mathrm{t}.}(W)`$, one has $`C_{\mathrm{c}.\mathrm{t}.}(W)C_{\mathrm{com}}(W)`$. $`\mathrm{}`$

This theorem will be proved in the following two sections (propositions 8 and 9): first we construct a protocol achieving the equivocation bound, showing that exponential decrease of $`ϵ`$ and $`\delta `$ is possible, and without using the noiseless side channels at all during the commit phase. Then we show the optimality of the bound.

To justify our allowing small errors both in the concealing and the binding property of a protocol, we close this section by showing that demanding too much trivialises the problem:

###### Theorem 5

There is no bit–commitment via $`W`$ which is $`ϵ`$–concealing and $`0`$–binding with $`ϵ<1`$. I.e., not even two distinct messages can be committed: $`|𝒜|=1`$.

*Proof .* If the protocol is $`0`$–sound, this means that for *every* value $`\mu `$ attained by $`M`$ with positive probability, Bob will accept the reveal phase if Alice behaved according to the protocol. On the other hand, that the protocol is $`0`$–binding means that for $`aa^{}`$ and arbitrary $`\mu ^{}`$, Bob will never accept if Alice behaves according to the protocol in the commit phase, with values $`a\mu `$ but tries to “reveal” $`a^{}\mu ^{}`$. This opens the possibility of a decoding method for $`a`$ based on $`Z^nNU^r`$: Bob simply tries out all possible $`a\mu `$ with his test $`\beta `$ — the single $`a`$ which is accepted must be the one used by Alice. Hence the scheme cannot be $`ϵ`$–concealing with $`ϵ<1`$. $`\mathrm{}`$

###### Remark 6

By contrast, is is easy to construct schemes both $`0`$–concealing and $`\delta `$-binding with $`\delta <1`$, for an appropriately defined channel:

Consider the channel $`F`$ with input and output alphabets $`𝒳=𝒵=\{0,1,2,3\}`$ and signals defined by

$$F_x(z)=\{\begin{array}{cc}\frac{1}{2}\hfill & \text{if }zx0\text{ or }1mod4,\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$

Alice commits to the bit $`b`$ by picking $`c\{0,1\}`$ at random and sending $`x=b+2c`$ (for which Bob receives a random $`z`$ such that $`zx0\text{ or }1mod4`$). To reveal, she tells him $`x`$ (which decodes to a unique $`b`$) and he accepts iff $`zx0\text{ or }1mod4`$.

Cleary, this scheme is $`0`$–concealing because for both $`b=0`$ and $`b=1`$ Bob sees the uniform distribution on $`𝒵`$. Equally obviously, it is $`0`$–sound, but it is also $`\frac{1}{2}`$–binding: for if Alice wants to “reveal” $`b^{}b`$ (with corresponding $`x^{}x`$), she has only a probability of $`\frac{1}{2}`$ to pick $`x^{}`$ with $`zx^{}0\text{ or }1mod4`$.

This simple scheme is in fact the template for the coding scheme of proposition 8: put differently, on sufficiently large scale (block length) every channel looks like $`F`$.

## 3 A scheme meeting the equivocation bound

Here we describe and prove security bounds of a scheme which is very simple compared to the generality we allowed in section 4: in the commit phase it consists only of a single block use of the noisy channel $`W^n`$, with no public discussion at all, where the input $`X^n`$ is a random one–to–many function of $`a`$ (in particular, $`a`$ is a function of the $`x^n`$ chosen). In the reveal phase Alice simply announces $`X^n`$ to Bob.

###### Proposition 7

Given $`\sigma ,\tau >0`$, and a distribution $`P`$ of $`X𝒳`$, with the output $`Z=W(X)`$, $`Q=\mathrm{Distr}(Z)`$. Then there exists a collection of codewords

$$\left(\xi _{a\mu }𝒳^n:a=1,\mathrm{},K,\mu =1,\mathrm{},L\right)$$

with the following properties:

1. For all $`(a,\mu )(a^{},\mu ^{})`$, $`d_\mathrm{H}(\xi _{a\mu },\xi _{a^{}\mu ^{}})2\sigma n`$.
2. For every $`a`$:

$$\frac{1}{2}\frac{1}{L}\underset{\mu =1}{\overset{L}{}}W_{\xi _{a\mu }}^nQ^n_125|𝒳||𝒵|\mathrm{exp}(n\tau ).$$
3. There are constants $`G,G^{}`$ and a continuous function $`G^{\prime \prime }`$ vanishing at $`0`$ such that

$`K`$ $`{\displaystyle \frac{1}{2n}}(3+\mathrm{log}|𝒳|+\mathrm{log}|𝒵|)^1\mathrm{exp}\left(nH(X|Z)n\sqrt{2\tau }G^{}nG^{\prime \prime }(\sigma )\right),`$
$`L`$ $`n(3+\mathrm{log}|𝒳|+\mathrm{log}|𝒵|)\mathrm{exp}\left(nI(XZ)+n\sqrt{2\tau }G\right).`$

*Proof .* To get the idea, imagine a wiretap channel  with $`W`$ as the stochastic matrix of the eavesdropper and a symmetric channel $`S_\sigma :𝒳𝒴=𝒳`$ for the legal user:

$$S_\sigma (y|x)=\{\begin{array}{cc}1\sigma \hfill & \text{ if }x=y,\hfill \\ \frac{1}{|𝒳|}\sigma \hfill & \text{ if }xy.\hfill \end{array}$$

The random coding strategy for such a channel, according to Wyner’s solution  (but see also  and ) will produce a code with the properties $`2`$ and $`3`$. Because the code for the legal user must fight the noise of the symmetric channel $`S_\sigma `$, we can expect its codewords to be of large mutual Hamming distance, i.e., we should get property $`1`$.

In detail: pick the $`\xi _{a\mu }`$ i.i.d. according to the distribution $`\stackrel{~}{P}^n`$, which is $`0`$ outside $`𝒯_{P,\sqrt{2\tau }}^n`$ (the typical sequences, see appendix A) and $`P^n`$ within, suitably normalised. Also introduce the subnormalised measures $`\widehat{W}_{x^n}^n`$: this is identical to $`W_{x^n}^n`$ within $`𝒯_{W,\sqrt{2\tau }}^n(x^n)`$ and $`0`$ outside. We will show that with high probability we can select codewords with properties 2 and 3, and only a small proportion of which violate property 1; then by an expurgation argument will we obtain the desired code.

By eqs. (9) and (14) in the appendix we have

$$\frac{1}{2}𝔼\widehat{W}_{\xi _{a\mu }}^nQ^n3|𝒳||𝒵|\mathrm{exp}(n\tau ),$$
(2)
with the expectation referring to the distribution $`\stackrel{~}{P}^n`$ of the $`\xi _{a\mu }`$. Observe that the support of all $`\widehat{W}_{\xi _{a\mu }}^n`$ is contained in $`𝒯_{Q,2|𝒳|\sqrt{\tau }}^n`$, using eq. (18) of the appendix. Now, $`𝒮`$ is defined as the set of those $`z^n`$ for which

$$𝔼\widehat{W}_{\xi _{a\mu }}^n(z^n)T:=\mathrm{exp}(n\tau )\mathrm{exp}\left(nH(Q)n\sqrt{2\tau }|𝒳|F\right),$$

with $`F=_{z:Q(z)0}\mathrm{log}Q(z)`$, and define $`\stackrel{~}{W}_{x^n}^n(z^n)=\widehat{W}_{x^n}^n(z^n)`$ if $`z^n𝒮`$ and $`0`$ otherwise. With the cardinality estimate eq. (11) of the appendix and eq. (2) we obtain

$$\frac{1}{2}𝔼\stackrel{~}{W}_{\xi _{a\mu }}^nQ^n4|𝒳||𝒵|\mathrm{exp}(n\tau ).$$
(3)
The Chernoff bound allows us now to efficiently sample the expectation $`\stackrel{~}{Q}^n:=𝔼\stackrel{~}{W}_{\xi _{a\mu }}^n`$: observe that all the values of $`\stackrel{~}{W}_{\xi _{a\mu }}^n`$ are upper bounded by

$$t:=\mathrm{exp}\left(nH(W|P)+n\sqrt{2\tau }|𝒳|\mathrm{log}|𝒵|+n\sqrt{2\tau }E\right),$$

using eq. (15). Thus, rescaling the variables, by lemma 13 and with the union bound, we get

$$\begin{array}{cc}\hfill \mathrm{Pr}& \left\{az^n𝒮\frac{1}{L^{}}\underset{\mu =1}{\overset{L^{}}{}}\stackrel{~}{W}_{\xi _{a\mu }}^n(z^n)[(1\pm \mathrm{exp}(n\tau ))\stackrel{~}{Q}^n(z^n)]\right\}\hfill \\ & 2K|𝒮|\mathrm{exp}\left(L\frac{T}{t}\frac{\mathrm{exp}(2n\tau )}{2\mathrm{ln}2}\right),\hfill \end{array}$$
(4)
which is smaller than $`1/2`$ if

$$L^{}>2+n(\mathrm{log}|𝒳|+\mathrm{log}|𝒵|)\mathrm{exp}\left(nI(XZ)+n\sqrt{2\tau }G\right),$$

with $`G=3+|𝒳|F+|𝒳|\mathrm{log}|𝒵|+E`$. Note that in this case, there exist values for the $`\xi _{a\mu }`$ such that the averages $`\frac{1}{L^{}}_\mu W_{\xi _{a\mu }}^n`$ are close to $`Q^n`$.

Now we have to enforce property 1: in a random batch of $`\xi _{a\mu }`$ we call $`a\mu `$ *bad* if $`\xi _{a\mu }`$ has Hamming distance less than $`2\sigma n`$ from another $`\xi _{a^{}\mu ^{}}`$. The probability that $`a\mu `$ is bad is easily bounded:

$$\begin{array}{cc}\hfill \mathrm{Pr}\{a\mu \text{ bad}\}& 2|𝒳|\mathrm{exp}(n\tau )+P^n\left(\underset{a^{}\mu ^{}a\mu }{}B_{2n\sigma }(\xi _{a^{}\mu ^{}})\right)\hfill \\ & 2|𝒳|\mathrm{exp}(n\tau )+\mathrm{max}\left\{P^n(𝒜):|𝒜|K^{}L^{}\left(\genfrac{}{}{0pt}{}{n}{2n\sigma }\right)|𝒳|^{2n\sigma }\right\}\hfill \\ & 5|𝒳|\mathrm{exp}(n\tau ),\hfill \end{array}$$

by eq. (13) in the appendix, because we choose

$$\begin{array}{cc}\hfill K^{}& \frac{1}{n}(3+\mathrm{log}|𝒳|+\mathrm{log}|𝒵|)^1\hfill \\ & \mathrm{exp}\left(nH(X|Z)n\sqrt{2\tau }G2n\sqrt{2\tau }DnH(2\sigma ,12\sigma )2n\sigma \mathrm{log}|𝒳|\right),\hfill \end{array}$$

hence

$$K^{}L^{}\left(\genfrac{}{}{0pt}{}{n}{2n\sigma }\right)|𝒳|^{2n\sigma }<\mathrm{exp}\left(nH(P)2n\sqrt{2\tau }D\right).$$

Thus, with probability at least $`1/2`$, only a fraction of $`10|𝒳|\mathrm{exp}(n\tau )`$ of the $`a\mu `$ are bad. Putting this together with eq. (4), we obtain a selection of $`\xi _{a\mu }`$ such that

$$a\frac{1}{2}\frac{1}{L^{}}\underset{\mu }{}W_{\xi _{a\mu }}^nQ^n_15|𝒳||𝒵|\mathrm{exp}(n\tau )$$
(5)
and only a fraction of $`10|𝒳|\mathrm{exp}(n\tau )`$ of the $`a\mu `$ are bad.

This means that for at least half of the $`a`$, w.l.o.g. $`a=1,\mathrm{},K=K^{}/2`$, only a fraction $`20|𝒳|\mathrm{exp}(n\tau )`$ of the $`\mu `$ form bad pairs $`a\mu `$, w.l.o.g. for $`\mu =L+1,\mathrm{},L^{}`$, with $`L=\left(120|𝒳|\mathrm{exp}(n\tau )\right)L^{}`$. Throwing out the remaining $`a`$ and the bad $`\mu `$, we are left with a code as desired. $`\mathrm{}`$

Observe that a receiver of $`Z^n`$ can efficiently check claims about the input $`\xi _{a\mu }`$ because of property $`1`$, that distinct codewords have “large” Hamming distance. The non–redundancy of $`W`$ shuns one–sided errors in this checking, as we shall see. The test $`\beta `$ is straightforward: it accepts iff $`Z^N𝒯_{W,\sqrt{2\tau }}^n(\xi _{a\mu })`$, the set of *conditional typical sequences*, see appendix A. This ensures soundness; for the bindingness we refer to the following proof.

We are now in a position to describe a protocol, having chosen codewords according to proposition 7:

> *Commit phase:* To commit to a message $`a`$, Alice picks $`\mu \{1,\mathrm{},L\}`$ uniformly at random and sends $`\xi _{a\mu }`$ through the channel. Bob obtains a channel output $`z^n`$.
>
> *Reveal phase:* Alice announces $`a`$ and $`\mu `$. Bob performs the test $`\beta `$: he accepts if $`z^n_{a\mu }:=𝒯_{W,\sqrt{2\tau }}^n(\xi _{a\mu })`$ and rejects otherwise.

###### Proposition 8

Assume that for all $`x𝒳`$ and distributions $`P`$ with $`P(x)=0`$,

$$W_x\underset{y}{}P(y)W_y_1\eta .$$

Let $`\tau =\frac{\sigma ^4\eta ^2}{8|𝒳|^4|𝒵|^2}`$: then the above protocol implements an $`ϵ`$–concealing and $`\delta `$–binding commitment with rate

$$\frac{1}{n}\mathrm{log}KH(X|Z)\sqrt{2\tau }G^{}H(2\sigma ,12\sigma )2\sigma \mathrm{log}|𝒳|\frac{\mathrm{log}n}{n}O\left(\frac{1}{n}\right)$$

and exponentially bounded security parameters:

$`ϵ`$ $`=50|𝒳||𝒵|\mathrm{exp}(n\tau ),`$
$`\delta `$ $`=2|𝒳||𝒵|\mathrm{exp}\left(2n\tau ^2\right).`$
*Proof .* That the protocol is $`ϵ`$–concealing is obvious from property 2 of the code in proposition 7: Bob’s distribution of $`Z^n`$ is always $`ϵ/2`$-close to $`Q^n`$, whatever $`a`$ is.

To show $`\delta `$–bindingness observe first that if Alice is honest, sending $`\xi _{a\mu }`$ in the commit phase and later revealing $`a\mu `$, the test $`\beta `$ will accept with high probability:

$$\begin{array}{cc}\hfill \mathrm{Pr}\left\{Z^n_{a\mu }\right\}& =W_{\xi _{a\mu }}^n\left(𝒯_{W,\sqrt{2\tau }}^n(\xi _{a\mu })\right)\hfill \\ & 12|𝒳||𝒵|\mathrm{exp}(n\tau )1\delta ,\hfill \end{array}$$

by eq. (14) in the appendix.

On the other hand, if Alice cheats, we may — in accordance with our definition — assume her using a deterministic strategy: i.e., she “commits” sending some $`x^n`$ and later attempts to “reveal” either $`a\mu `$ or $`a^{}\mu ^{}`$, with $`aa^{}`$. Because of property 1 of the code in proposition 7, at least one of the codewords $`\xi _{a\mu }`$, $`\xi _{a^{}\mu ^{}}`$ is at Hamming distance at least $`\sigma n`$ from $`x^n`$: w.l.o.g., the former of the two. But then the test $`\beta `$ accepts “revelation” of $`a\mu `$ with small probability:

$$\mathrm{Pr}\left\{Z^n_{a\mu }\right\}=W_{x^n}^n\left(𝒯_{W,\sqrt{2\tau }}^n(\xi _{a\mu })\right)2\mathrm{exp}(2n\tau ^2)\delta ,$$

by lemma 14 in the appendix. $`\mathrm{}`$

## 4 Upper bounding the achievable rate

We assume that $`W`$ is non–redundant. We shall prove the following assertion, assuming a uniformly distributed variable $`A𝒜`$ of messages.

###### Proposition 9

Consider an $`ϵ`$–concealing and $`\delta `$–binding commitment protocol with $`n`$ uses of $`W`$. Then

$$\begin{array}{cc}\hfill \mathrm{log}|𝒜|& n\mathrm{max}\{H(X|Z):\mathrm{Distr}(Z|X)=W\}\hfill \\ & +n\left(ϵ(\mathrm{log}B+\mathrm{log}|𝒵|)+5\sqrt[3]{\delta }\mathrm{log}|𝒳|\right)+2.\hfill \end{array}$$
(6)
The key, as it turns out, of its proof, is the insight that in the above protocol, should it be concealing and binding, $`x^n`$ together with Bob’s view of the commit phase (essentially) determine $`a`$. In the more general formulation we permitted in section 2, we prove :

$$H(A|Z^nNU^r;X^n)\delta ^{}=H(5\sqrt[3]{\delta },15\sqrt[3]{\delta })+5\sqrt[3]{\delta }\mathrm{log}|𝒜|.$$
(B’)
Intuitively, this means that with the items Alice entered into the commit phase of the protocol and those which are accessible to Bob, not too many values of $`A`$ should be consistent — otherwise Alice had a way to cheat.

*Proof of eq. (B’).*  For each $`a\mu `$ the commit protocol (both players being honest) creates a distribution $`\mathrm{\Delta }_{a\mu }`$ over *conversations* $`(x^nv^r;z^nu^r)`$. We leave out Bob’s random variable $`N`$ here, noting that he can create its correct conditional distribution from $`z^nu^r;v^r`$, which is his view of the conversation. The only other place where he needs it is to perform the test $`\beta `$. We shall in the following assume that it includes this creation of $`N`$, which makes $`\beta `$ into a probabilistic test, depending on $`(a\mu v^r;z^nu^r)`$.

The pair $`a\mu `$ has a probability $`\alpha _{a\mu }`$ that its conversation with subsequent revelation of $`a\mu `$ is accepted. By soundness, we have

$$\underset{\mu }{}\mathrm{Pr}\{M=\mu \}\alpha _{a\mu }1\delta ,$$

for every $`a`$. Hence, by Markov inequality, there exists (for every $`a`$) a set of $`\mu `$ of total probability $`1\sqrt[3]{\delta ^2}`$ for which $`\alpha _{a\mu }1\sqrt[3]{\delta }`$. We call such $`\mu `$ *good for* $`a`$.

From this we get a set $`𝒞_{a\mu }`$ of “partial” conversations $`(x^nv^r;u^r)`$, with probability $`\mathrm{\Delta }_{a\mu }\left(𝒞_{a\mu }\right)1\sqrt[3]{\delta }`$, which are accepted with probability at least $`1\sqrt[3]{\delta }`$. (In the test also $`Z^n`$ enters, which is distributed according to $`W_{x^n}^n`$.)

Let us now define the set

$$𝒞_a:=\underset{\mu \text{ good for }a}{}𝒞_{a\mu },$$

which is a set of “partial conversations” which are accepted with probability at least $`1\sqrt[3]{\delta }`$ and

$$\mathrm{\Delta }_a\left(𝒞_a\right)12\sqrt[3]{\delta },$$

with the distribution

$$\mathrm{\Delta }_a:=\underset{\mu }{}\mathrm{Pr}\{M=\mu \}\mathrm{\Delta }_{a\mu }$$

over “partial conversations”: it is the distribution created by the commit phase give the message $`a`$.

We claim that

$$\mathrm{\Delta }_a\left(X^nV^r;U^r\underset{a^{}a}{}𝒞_a^{}\right)3\sqrt[3]{\delta }.$$
(7)
Indeed, if this were not the case, Alice had the following cheating strategy: in the commit phase she follows the protocol for input message $`a`$. In the reveal phase she looks at the “partial conversation” $`x^nv^r;u^r`$ and tries to “reveal” some $`a^{}\mu ^{}`$ for which the partial conversation is in $`𝒞_{a^{}\mu ^{}}`$ (if these do not exist, $`a^{}\mu ^{}`$ is arbitrary). This defines random variables $`A^{}`$ and $`\stackrel{~}{M}^{}`$ for which it is easily checked that

$$\mathrm{Pr}\left\{\beta (Z^nNU^r;aM)=\mathrm{ACC}\&\beta (Z^nNU^r;A^{}\stackrel{~}{M}^{})=\mathrm{ACC}\right\}>\delta ,$$

contradicting the $`\delta `$–bindingness condition.

Using eq. (7) we can build a decoder for $`A`$ from $`X^nV^r;U^r`$: choose $`\widehat{A}=a`$ such that $`X^nV^r;U^r𝒞_a`$ — if there exists none or more than one, let $`\widehat{A}`$ be arbitrary. Clearly,

$$\mathrm{Pr}\{A\widehat{A}\}5\sqrt[3]{\delta },$$

and invoking Fano’s inequality we are done. $`\mathrm{}`$

Armed with this, we can now proceed to the

*Proof of proposition 9* We can successively estimate,

$$\begin{array}{cc}\hfill H(X^n|Z^n)& H(X^n|Z^nNU^r)\hfill \\ & =H(AX^n|Z^nNU^r)H(A|Z^nNU^r;X^n)\hfill \\ & H(A|Z^nNU^r)H(A|Z^nNU^r;X^n)\hfill \\ & H(A|Z^nNU^r)\delta ^{}\hfill \\ & =H(A)I(AZ^nNU^r)\delta ^{}\hfill \\ & H(A)ϵ^{}\delta ^{},\hfill \end{array}$$

using eq. (B’) in the fourth, eq. (A’) in the sixth line. On the other hand, subadditivity and the conditioning inequality imply

$$H(X^n|Z^n)\underset{k=1}{\overset{n}{}}H(X_k|Z_k),$$

yielding the claim, because $`H(A)=\mathrm{log}|𝒜|`$.

The application to the proof of the converse of theorem 2 is by observing that $`ϵ^{},\delta ^{}=o(n)`$. $`\mathrm{}`$

Note that for the proof of the proposition we considered only a very weak attempt of Alice to cheat: she behaves according to the protocol during the commit phase, and only at the reveal stage she tries to be inconsistent. Similarly, our concealingness condition considered only passive attempts to cheat by Bob, i.e., he follows exactly the protocol, and tries to extract information about $`A`$ only by looking at his view of the exchange.

Thus, even in the model of *passive cheating*, which is less restrictive than our definition in section 2, we obtain the upper bound of proposition 9

## 5 Examples

In this section we discuss some particular channels, which we present as stochastic matrices with the rows containing the output distributions.

1. Binary symmetric channel $`B_p`$: Let $`0p1`$. Define

$`B_p:=`$    $``$ $`0`$ $`1`$    $`0`$ $`1p`$ $`p`$  $`1`$ $`p`$ $`1p`$

The transmission capacity if this channel is easily computed from Shannon’s formula : $`C(B_p)=1H(p,1p)`$, which is non–zero iff $`p1/2`$. The optimal input distribution is the uniform distribution $`(1/2,1/2)`$ on $`\{0,1\}`$. Note that this channel is trivial if $`p\{0,1/2,1\}`$, hence $`C_{\mathrm{com}}(B_p)=0`$ for these values of $`p`$. We may thus, w.l.o.g., assume that $`0<p<1/2`$, for which $`B_p`$ is non–redundant. It is not hard to compute the optimal input distribution as the uniform distribution, establishing $`C_{\mathrm{com}}(B_p)=H(p,1p)`$.

The result is in accordance with our intuition: the noisier the channel is, the worse it is for transmission, but the better for commitment.

2. A trivial channel: Consider the channel

$`T:=`$    $``$ $`0`$ $`1`$    $`a`$ $`1/2`$ $`1/2`$  $`b`$ $`1`$ $`0`$  $`c`$ $`0`$ $`1`$

Clearly, $`T`$ is trivial, hence $`C_{\mathrm{com}}(T)=0`$. Still it is an interesting example in the light of our proof of proposition 8: for assume a wiretap channel for which $`T`$ is the stochastic matrix of the eavesdropper, while the legal user obtains a noiseless copy of the input. Then clearly the wiretap capacity of this system is $`1`$, with optimal input distribution $`(1/2,1/4,1/4)`$.

3. Transmission and commitment need not be opposites: We show here an example of a channel where the optimising input distributions for transmission and for commitment are very different:

$`V:=`$    $``$ $`0`$ $`1`$    $`0`$ $`1/2`$ $`1/2`$  $`1`$ $`1`$ $`0`$

It can be easily checked that the maximum of the mutual information, i.e. the transmission capacity, is attained for the input distribution

$$P(0)=\frac{2}{5}=0.4,P(1)=\frac{3}{5}=0.6,$$

from which we obtain $`C(V)0.3219`$. On the other hand, the equivocation is maximised for the input distribution

$$P^{}(0)=1\sqrt{\frac{1}{5}}0.5528,P^{}(1)=\sqrt{\frac{1}{5}}0.4472,$$

from which we get that $`C_{\mathrm{com}}(V)0.6942`$. The maximising distributions are so different that the sum $`C(V)+C_{\mathrm{com}}(V)>1`$, i.e. it exceeds the maximum input and output entropies of the channel.

## 6 Quantum channels

The construction of section 3 can be carried over to a class of quantum channels, namely so–called *cq–channels* (classical–quantum channels):

$$W:𝒳𝒮(),$$

a map from an input alphabet (here assumed to be finite) into the set of states on a Hilbert space $``$, also assumed to be finite–dimensional in the present discussion. (For an overview of quantum information theory see  and the textbook .) *Non–redundancy* means the same here, only that the convex structure is now the convex compact set of states, instead of the probability simplex. We assume this property of $`W`$ silently in the following.

###### Theorem 10

For a distribution $`P`$ on the input alphabet, one can achieve the commitment rate

$$H(P)\chi \left(\{P(x);W_x\}\right),$$
(8)
with the Holevo mutual information

$$\chi \left(\{P(x);W_x\}\right)=S\left(\underset{x}{}P(x)W_x\right)\underset{x}{}P(x)S(W_x),$$

where $`S(\rho )=\mathrm{Tr}\rho \mathrm{log}\rho `$ is the von Neumann entropy of a state.

The maximum of the expression (8) is optimal in the case of *no noiseless side communication* during the commit phase.

*Proof (Sketch).*  For the achievability one proves a coding result similar to proposition 7, with the $`_1`$–norm denoting trace norm. The most crucial point is property $`2`$: our proof used two things: restricting the distributions $`W_{x^n}^n`$ to typical sequences — this can be done also for states by constructing typical subspaces — and Chernoff bound to obtain a “small sample”. We use an analogue of this for operators from , stated below as lemma 11. This technique is actually used in the work of Cai and Yeung  to construct codes for the quantum wiretap channel

For the optimality, it is not hard to prove the quantum analogues of eqs. (A’) and (B’), and then the upper bound follows exactly as in our proof of proposition 9. $`\mathrm{}`$

###### Lemma 11 (Ahlswede, Winter )

Let $`X_1,\mathrm{},X_L`$ be i.i.d. random variables taking values in the operators $`()`$ on the $`D`$–dimensional Hilbert space $``$, $`0X_{\mathrm{}}𝟙`$, with $`A=𝔼X_{\mathrm{}}\alpha 𝟙`$, and let $`\eta >0`$. Then

$$\mathrm{Pr}\left\{\frac{1}{L}\underset{\mathrm{}=1}{\overset{L}{}}X_{\mathrm{}}[(1\eta )A;(1+\eta )A]\right\}2D\mathrm{exp}\left(L\frac{\alpha \eta ^2}{2\mathrm{ln}2}\right),$$

where $`[A;B]=\{X:AXB\}`$ is an interval in the operator order. $`\mathrm{}`$

###### Example 12

Assume any set of distinct pure qubit states $`W_x=|\psi _x\psi _x|`$. Then, with $`\rho =_xP(x)W_x`$, the rate

$$\underset{P}{\mathrm{max}}\{H(P)S(\rho )\}$$

is achievable. Because of $`S(\rho )1`$ this is positive if the input alphabet has at least three symbols; in the case of two input symbols it is positive iff the two states are non–orthogonal.

This is no contradiction to Mayer’s no–go theorem for quantum bit commitment even though the channel might appear to be noiseless: it is, however, not a noiseless qubit channel, because the states are restricted to a set of pure states. Modelled as a completely positive map, it would be a measurement–prepare channel of the form

$`W:\left(𝒳\right)`$ $`()`$
$`\sigma `$ $`{\displaystyle \underset{x}{}}x|\sigma |xW_x.`$
I.e., its use involves a “guaranteed (von Neumann) measurement” on all messages which come from Alice.

Regarding theorem 10, we conjecture the achievable rate stated there to remain optimal even if unlimited noiseless quantum communication is allowed. There is however the much more interesting question of more general quantum channels, for example a depolarising qubit channel, the quantum analogue of a binary symmetric channel: does it allow bit commitment, and if so, at which rate?

This generalisation may be significant because first of all, information theoretically secure bit commitment is not possible with noiseless quantum communication . Here we have shown that it is possible under the assumption of a noisy channel. This opens the possibility of perhaps *having* bit commitment under realistic conditions where one can ensure that all available channels are noisy.

## 7 Discussion

We have considered bit–string commitment by using a noisy channel and have characterised the exact capacity for this task by a single–letter formula. This implies a lower bound on the coin tossing capacity of that channel by the same formula, which in fact we conjecture to be an equality.

Satisfactory as this result is, it has to be noted that we are not able in general to provide an explicit protocol: our proof is based on the random coding technique and shows only existence. What is more, even if one finds a good code it will most likely be inefficient: the codebook is just the list of $`\xi _{a\mu }`$. In this connection we conjecture that the commitment capacity can be achieved by random linear codes (compare the situation for channel coding!). It is in any case an open problem to find efficient good codes, even for the binary symmetric channel. Note that we only demand efficient *encoding* — there is no decoding of errors in our scheme, only an easily performed test.

Our scheme is a block–coding method: Alice has to know the whole of her message, say a bit string, before she can encode. One might want to use our result as a building block in other protocols which involve committing to bits at various stages — then the natural question arises whether there is an “online” version which would allow Alice to encode and send bits as she goes along.

In the same direction of better applicability it would be desirable to extend our results to a more robust notion of channel: compare the work of  where a cheater is granted partial control over the channel characteristics. Still, the fixed channel is not beyond application: note that it can be simulated by pre–distributed data from a trusted party via a “noisy one–time pad” (compare  and ).

Another open question of interest is to determine the reliability function, i.e., the optimal asymptotic rate of the error $`ϵ+\delta `$ (note that implicit in our proposition 8 is a lower bound): it is especially interesting at $`R=0`$, because there the rate tells exactly how secure single–bit commitment can be made.

Finally, we have outlined that a class of quantum channels also allows bit commitment: they even have a commitment capacity of the same form as the classical result. This opens up the possibility of unconditionally secure bit commitment for other noisy quantum channels.

We hope that our work will stimulate the search for optimal rates of other cryptographic primitives, some of which are possible based on noise, e.g. oblivious transfer.

## Acknowledgements

We thank Ning Cai and Raymond W. Yeung for sharing their ideas on the quantum wiretap channel, and making available to us their manuscript . We also acknowledge interesting discussions with J. Müller–Quade and P. Tuyls at an early stage of this project.

AW is supported by the U.K. Engineering and Physical Sciences Research Council. ACAN and HI are supported by the project “Research and Development of Quantum Cryptography” of the Telecommunications Advancement Organisation as part of the programme “Research and Development on Quantum Communication Technology” of the Ministry of Public Management, Home Affairs, Posts and Telecommunications, Japan.

## Appendix A Typical sequences

This appendix collects some facts about typical sequences used in the main body of the text. We follow largely the book of Csiszár and Körner .

The fundamental fact we shall use is the following large deviation version of the law of large numbers:

###### Lemma 13 (Chernoff )

For i.i.d. random variables $`X_1,\mathrm{},X_N`$, with $`0X_n1`$ and with expectation $`𝔼X_n=p`$:

$`\mathrm{Pr}\left\{{\displaystyle \frac{1}{N}}{\displaystyle \underset{n=1}{\overset{N}{}}}X_n(1+\eta )p\right\}`$ $`\mathrm{exp}\left(N{\displaystyle \frac{p\eta ^2}{2\mathrm{ln}2}}\right),`$
$`\mathrm{Pr}\left\{{\displaystyle \frac{1}{N}}{\displaystyle \underset{n=1}{\overset{N}{}}}X_n(1\eta )p\right\}`$ $`\mathrm{exp}\left(N{\displaystyle \frac{p\eta ^2}{2\mathrm{ln}2}}\right).`$
$`\mathrm{}`$

For a probability distribution $`P`$ on $`𝒳`$ and $`ϵ>0`$ define the set of $`ϵ`$–typical sequences:

$$𝒯_{P,ϵ}^n=\{x^n:x\left|N(x|x^n)P(x)n\right|ϵn\&P(x)=0N(x|x^n)=0\},$$

with the number $`N(x|x^n)`$ denoting the number of letters $`x`$ in the word $`x^n`$. The probability distribution $`P_{x^n}(x)=\frac{1}{n}N(x|x^n)`$ is called the *type* of $`x^n`$. Note that $`x^n𝒯_{P,ϵ}^n`$ is equivalent to $`|P_{x^n}(x)P(x)|ϵ`$ for all $`x`$.

These are the properties of typical sequences we shall need:

$$P^n\left(𝒯_{P,ϵ}^n\right)12|𝒳|\mathrm{exp}\left(nϵ^2/2\right).$$
(9)
This is an easy consequence of the Chernoff bound, lemma 13, applied to the indicator variables $`X_k`$ of the letter $`x`$ in position $`k`$ in $`X^n`$, with $`\eta =ϵP(x)^1`$.

$$x^n𝒯_{P,ϵ}^n\{\begin{array}{cc}P^n(x^n)\mathrm{exp}\left(nH(P)+nϵD\right),\hfill & \\ P^n(x^n)\mathrm{exp}\left(nH(P)nϵD\right),\hfill & \end{array}$$
(10)
with the constant $`D=_{x:P(x)0}\mathrm{log}P(x)`$. See .

$`\left|𝒯_{P,ϵ}^n\right|`$ $`\mathrm{exp}\left(nH(P)+nϵD\right),`$ (11)
$`\left|𝒯_{P,ϵ}^n\right|`$ $`\left(12|𝒳|\mathrm{exp}\left(nϵ^2/2\right)\right)\mathrm{exp}\left(nH(P)nϵD\right).`$ (12)
This follows from eq. (10). These estimates also allow to lower bound the size of sets with large probability: assume $`P^n(𝒞)\eta `$, then

$$|𝒞|\left(\eta 2|𝒳|\mathrm{exp}\left(nϵ^2/2\right)\right)\mathrm{exp}\left(nH(P)nϵD\right).$$
(13)
We also use these notions in the “non–stationary” case: consider a channel $`W:𝒳𝒵`$, and an input string $`x^n𝒳^n`$. Then define, with $`ϵ>0`$, the set of conditional $`ϵ`$–typical sequences:

$$\begin{array}{cc}\hfill 𝒯_{W,ϵ}^n(x^n)& =\{z^n:x,z|N(xz|x^nz^n)nW(z|x)P_{x^n}(x)|ϵn.\hfill \\ & \&.W(z|x)=0N(xz|x^nz^n)=0\}\hfill \\ & =\underset{x}{}𝒯_{W_x,ϵP_{x^n}(x)^1}^_x,\hfill \end{array}$$

with the sets $`_x`$ of positions in the word $`x^n`$ where $`x_k=x`$. The latter product representation allows to easily transport all of the above relations for typical sequences to conditional typical sequences:

$$W_{x^n}^n\left(𝒯_{W,ϵ}^n(x^n)\right)12|𝒳||𝒵|\mathrm{exp}\left(nϵ^2/2\right).$$
(14)
$$x^n𝒯_{W,ϵ}^n(x^n)\{\begin{array}{cc}W_{x^n}^n(x^n)\mathrm{exp}\left(nH(W|P_{x^n})+nϵE\right),\hfill & \\ W_{x^n}^n(x^n)\mathrm{exp}\left(nH(W|P_{x^n})nϵE\right),\hfill & \end{array}$$
(15)
with $`E=\mathrm{max}_x_{z:W_x(z)0}\mathrm{log}W_x(z)`$ and the conditional entropy $`H(W|P)=_xP(x)H(W_x)`$.

$`\left|𝒯_{W,ϵ}^n(x^n)\right|`$ $`\mathrm{exp}\left(nH(W|P_{x^n})+nϵE\right),`$ (16)
$`\left|𝒯_{W,ϵ}^n(x^n)\right|`$ $`\left(12|𝒳||𝒵|\mathrm{exp}\left(nϵ^2/2\right)\right)\mathrm{exp}\left(nH(W|P_{x^n})nϵE\right).`$ (17)
A last elementary property: for $`x^n`$ of type $`P`$ and output distribution $`Q`$, with $`Q(z)=_xP(x)W_x(z)`$,

$$𝒯_{W,ϵ}^n(x^n)𝒯_{Q,ϵ|𝒳|}^n.$$
(18)
As an application, let us prove the following lemma:

###### Lemma 14

For words $`x^n`$ and $`y^n`$ with $`d_H(x^n,y^n)\sigma n`$, and a channel $`W`$ such that

$$x𝒳,P\text{ p.d. with }P(x)=0W_x\underset{y}{}P(y)W_y_1\eta ,$$

one has, with $`ϵ=\frac{\sigma ^2\eta }{2|𝒳|^2|𝒵|}`$,

$$W_{y^n}^n\left(𝒯_{W,ϵ}^n(x^n)\right)2\mathrm{exp}(nϵ^4/2)$$

*Proof .* There exists an $`x`$ such that the word $`x^_x`$ (composed of letters $`x`$ only) has distance at least $`\frac{1}{|𝒳|}\sigma n`$ from $`y^_x`$. In particular, $`N_x:=N(x|x^n)=|_x|\frac{1}{|𝒳|}\sigma n`$.

This implies also, by assumption on the channel,

$$\frac{1}{N_x}\underset{k_x}{}W_{y_k}W_x_1\frac{1}{|𝒳|}\sigma \eta .$$

Hence there must be a $`z𝒵`$ with

$$\left|\frac{1}{N_x}\underset{k_x}{}W_{y_k}(z)W_x(z)\right|\frac{1}{|𝒳||𝒵|}\sigma \eta .$$

By definition, this in turn implies that for all $`z^n𝒯_{W,ϵ}^n(x^n)`$,

$$|N(z|z^_x)\underset{k_x}{}W_{y_k}(z)|\frac{1}{2|𝒳||𝒵|}\sigma \eta N_x.$$

Introducing the sets $`𝒥_{xy}=\{k_x:y_k=y\}`$, with cardinalities $`N_{xy}=|_{yx}|`$, there is a $`y`$ such that (still for all $`z^n𝒯_{W,ϵ}^n(x^n)`$),

$$\begin{array}{cc}\hfill |N(z|z^{𝒥_{xy}})N_{xy}W_y(z)|& \frac{1}{2|𝒳|^2|𝒵|}\sigma \eta N_x\hfill \\ & \frac{1}{2|𝒳|^2|𝒵|}\sigma \eta N_{xy}.\hfill \end{array}$$

This implies

$$N_{xy}\frac{1}{4|𝒳|^2|𝒵|}\sigma \eta N_x\frac{1}{4|𝒳|^3|𝒵|}\sigma ^2\eta n,$$

and with lemma 13 we obtain the claim. $`\mathrm{}`$