# Discrimination of two channels by adaptive methods and its application to
quantum system

Masahito Hayashi  M. Hayashi is with Graduate School of Information Sciences,
Tohoku University, Aoba-ku, Sendai, 980-8579, Japan (e-mail:
<EMAIL_ADDRESS>
###### Abstract

The optimal exponential error rate for adaptive discrimination of two channels
is discussed. In this problem, adaptive choice of input signal is allowed.
This problem is discussed in various settings. It is proved that adaptive
choice does not improve the exponential error rate in these settings. These
results are applied to quantum state discrimination.

###### Index Terms:

Simple hypothesis testing, Channel, Discrimination, Quantum state, One-way
LOCC, Active learning, Experimental design, Stein’s lemma, Chernoff bound,
Hoeffding bound, Han-Kobayashi bound

##  I Introduction

Discriminating two distributions is treated as a fundamental problem in the
field of statistical inference. This problem can be regarded as simple
hypothesis testing because both hypotheses consist of a single distribution.
Many researchers, Stein, Chernoff[3], Hoeffding[16], and Han-Kobayashi[10]
have studied the asymptotic behavior when the number $n$ of identical and
independent observations is sufficiently large. They formulated a simple
hypothesis testing/discrimination of two distributions as an optimization
problem and derived the respective optimum value, e.g., the optimal
exponential error rate. We call these optimum values the Stein bound, the
Chernoff bound, the Hoeffding bound, and the Han-Kobayashi bound,
respectively. Han [8, 9] later extended these results to the discrimination of
two general sequences of distributions, including the Markovian case. Nagaoka-
Hayashi [21] simplified Han’s discussion and generalized Han’s extension of
the Han-Kobayashi bound.

In the present paper, we consider another extension of the above results. That
is, we extend the above results to the discrimination of two (classical)
channels, in which two probabilistic transition matrices are given. Such a
problem has appeared in Blahut[2]. In this problem, the number of applications
of this channel is fixed to a given constant $n$, and we can choose
appropriate inputs for this purpose. In this case, we assume that the given
channel is memoryless. If we use the same input to all applications of the
given channel, the $n$ output data obeys an identical and independent
distribution. This property holds even if we choose the input randomly based
on the same distribution on input signals. This strategy is called the non-
adaptive method. In particular, when the same input is applied to all
channels, it is called the deterministic non-adaptive method. If the input is
determined stochastically, it is called the stochastic non-adaptive method,
which was treated by Blahut[2]. In the non-adaptive method, our task is
choosing the optimal input for distinguishing two channels most efficiently.
In the present paper, we assume that we can choose the $k$-th input signal
based on the preceding $k-1$ output data. This strategy is called the adaptive
method, which is the main focus of the present paper. In the parameter
estimation, such an adaptive method improves estimation performance. That is,
in the one-parameter estimation, the asymptotic estimation error is bounded by
the inverse of the optimum Fisher information. However, if we do not apply the
adaptive method, it is generally impossible to realize the optimum Fisher
information in all points at the same time. It is known that the adaptive
method realizes the optimum Fisher information in all points[13, 7].
Therefore, one may expect that the adaptive method improves the performance of
discriminating two channels.

As our main result, we succeeded in proving that the adaptive method cannot
improve the non-adaptive method in the sense of all of the above mentioned
bounds, i.e., the Stein bound, the Chernoff bound, the Hoeffding bound, and
the Han-Kobayashi bound. That is, there is no difference between the non-
adaptive method and the adaptive method in these asymptotic formulations.
Indeed, as is proven herein, the deterministic non-adaptive method gives the
optimum performance with respect to the Stein bound, the Chernoff bound, and
the Hoeffding bound. However, in order to attain the Han-Kobayashi bound, in
general, we need the stochastic non-adaptive method.

On the other hand, the research field in quantum information has treated the
discrimination of two quantum states. Hiai-Petz[15] and Ogawa-Nagaoka[18]
proved the quantum version of Stein’s lemma. Audenaert et al. [1] and
Nussbaum-Szkoła [23, 24] obtained the quantum version of the Chernoff bound.

Ogawa-Hayashi [17] derived a lower bound of the quantum version of the
Hoeffding bound. Later, Hayashi [12] and Nagaoka [20] obtained its tight bound
based on the results by Audenaert et al. [1] and Nussbaum-Szkoła [23, 24].
Hayashi [11] (in p.90) obtained the quantum version of the Han-Kobayashi bound
based on Nagaoka[19]’s discussion. These discussions assume that any
measurement on the $n$-tensor product system is allowed for testing the given
state. Hence, the next goal is the derivation of these bounds under some
locality restrictions on an $n$-partite system for possible measurements. One
easy setting is restricting the present measurement to be identical to that in
the respective system. In this case, our task is the choice of the optimal
measurement on the single system. By considering the measurement and the
quantum state as the input and the channel, respectively, we can treat this
problem by the non-adaptive method of the classical channel. Another setting
is restricting our measurement to one-way local operations and classical
communications (one-way LOCC). In the above-mentioned correspondence, the one-
way LOCC setting can be regarded as the adaptive method of the classical
channel. Hence, applying the above argument to discrimination of two quantum
states, we can conclude that one-way communication does not improve
discrimination of two quantum states in the respective asymptotic
formulations.

Furthermore, the same problem appears in adaptive experimental design and
active learning. In learning theory, we identify the given system by using the
obtained sequence of input and output pairs. In particular, in active
learning, we can choose the inputs using the preceding data. Hence, the
present result indicates that active learning does not improve the performance
of learning when the candidates of the unknown system are given by only two
classical channels. In experimental design, we choose suitable design of our
experiment for inferring the unknown parameter. Adaptive improvement for the
design is allowed in adaptive experimental design. When the candidates of the
unknown parameter are only two values, the obtained result can be applied.
That is, adaptive improvement for design does not work.

The remainder of the present paper is organized as follows. Section II reviews
the Stein bound, the Chernoff bound, the Hoeffding bound, and the Han-
Kobayashi bound in discrimination of two probability distributions. In Section
III, we present our formulation and notations of the adaptive method in the
discrimination of two (classical) channels, and discuss the adaptive-method
versions of the Stein bound, the Chernoff bound, the Hoeffding bound, and the
Han-Kobayashi bound, respectively. In Section IV, we consider a simple
example, in which the stochastic non-adaptive method is required for attaining
the Han-Kobayashi bound. In Section V, we apply the present result to
discrimination of two quantum states by one-way LOCC. In Sections VI, VII, and
VIII, we prove the adaptive-method versions of Stein bound, the Chernoff
bound, the Hoeffding bound, and the Han-Kobayashi bound, respectively.

##  II Discrimination/simple hypothesis testing between two probability
distributions

In preparation for the main topic, we review the simple hypothesis testing
problem for the null hypothesis $H_{0}$ : $P^{n}$ versus the alternative
hypothesis $H_{1}$: ${\overline{P}}^{n}$, where $P^{n}$ and
${\overline{P}}^{n}$ are the $n$-th identical and independent distributions of
$P$ and $\overline{P}$, respectively on the probability space ${\cal Y}$. The
problem is to decide which hypothesis is true based on $n$ outputs
$y_{1},\ldots,y_{n}$. In the following, randomized tests are allowed as our
decision. Hence, our decision method is described by a $[0,1]$-valued function
$f$ on ${\cal Y}^{n}$. When we observe $n$ outputs $y_{1},\ldots,y_{n}$, we
accept the alternative hypothesis $\overline{P}$ with the probability
$f(y_{1},\ldots,y_{n})$. We have two types of errors. In the first type, the
null hypothesis $P$ is rejected despite being correct. In the second type, the
alternative $\overline{P}$ is rejected despite being correct. Hence, the first
type of error probability is given by ${\rm E}_{P^{n}}f$, and the second type
of error probability is by ${\rm E}_{{\overline{P}}^{n}}(1-f)$. Note that
${\rm E}_{P}$ describes the expectation under the distribution $P$.

In the following, we assume that

$\displaystyle\Phi(s|P\|\overline{P})$ $\displaystyle:=\int_{{\cal
Y}}(\frac{\partial\overline{P}}{\partial P}(y))^{s}P(dy)<\infty$
$\displaystyle\phi(s|P\|\overline{P})$
$\displaystyle:=\log\Phi(s|P\|\overline{P})$

and $\phi(s|P\|\overline{P})$ is $C^{2}$-continuous. In the present paper, we
choose the base of the logarithm to be $e$. In the discrimination of two
distributions, we treat two types of probabilities equally. Then, we simply
minimize the equal sum ${\rm E}_{P^{n}}f+{\rm E}_{{\overline{P}}^{n}}(1-f)$.
Its optimal rate of exponential decrease is characterized by the Chernoff
bound[3]:

$\displaystyle
C(P,\overline{P}):=\lim_{n\rightarrow\infty}\frac{-1}{n}\log(\min_{f_{n}}{\rm
E}_{P^{n}}f_{n}+{\rm E}_{{\overline{P}}^{n}}(1-f_{n}))=-\min_{0\leq s\leq
1}\phi(s|P\|\overline{P}).$

In order to treat these two error probabilities asymmetrically, we often
restrict the first type of error probability ${\rm E}_{P^{n}}f$ to below a
particular threshold $\epsilon$, and minimize the second type of error
probability ${\rm E}_{{\overline{P}}^{n}}(1-f)$:

$\displaystyle\beta_{n}^{*}(\epsilon):=\min_{f}\bigl{\\{}{\rm
E}_{{\overline{P}}^{n}}(1-f)$ $\displaystyle\bigm{|}{\rm
E}_{P^{n}}f\leq\epsilon\bigr{\\}}.$

Then, the Stein’s lemma holds. For $0<\forall\epsilon<1$, the equation

$\displaystyle\lim_{n\rightarrow\infty}\frac{1}{n}\log\beta_{n}^{*}(\epsilon)=-D(P\|\overline{P})$
(1)

holds, where the relative entropy $D(P\|\overline{P})$ is defined by

$\displaystyle D(P\|\overline{P})=\int_{{\cal
Y}}-\log\frac{\partial\overline{P}}{\partial P}(y)P(dy).$

Indeed, this lemma has the following variant form. Define

$\displaystyle B(P\|\overline{P}):=$
$\displaystyle\sup_{\\{f_{n}\\}}\left\\{\left.\varliminf_{n\rightarrow\infty}\frac{-\log{\rm
E}_{{\overline{P}}^{n}}(1-f_{n})}{n}\right|\lim_{n\rightarrow\infty}{\rm
E}_{P^{n}}f_{n}=0\right\\}$ $\displaystyle B^{*}(P\|\overline{P}):=$
$\displaystyle\inf_{\\{f_{n}\\}}\left\\{\left.\varliminf_{n\rightarrow\infty}\frac{-\log{\rm
E}_{{\overline{P}}^{n}}(1-f_{n})}{n}\right|\varliminf_{n\rightarrow\infty}{\rm
E}_{P^{n}}f_{n}<1\right\\}.$

Then, these two quantities satisfy the following relations:

$\displaystyle B(P\|\overline{P})=B^{*}(P\|\overline{P})=D(P\|\overline{P}).$

As a further analysis, we focus on the decreasing exponent of the error
probability of the first type under an exponential constraint for the error
probability of the second type. When the decreasing exponent of for the error
probability of the second type is greater than the relative entropy
$D(P\|\overline{P})$ , the error probability of the second type converges to
$1$. In this case, we focus on the decreasing exponent of the probability of
correctly accepting the null hypothesis $P$. For this purpose, we define

$\displaystyle B_{e}(r|P\|\overline{P}):=$
$\displaystyle\sup_{\\{f_{n}\\}}\left\\{\left.\varliminf_{n\rightarrow\infty}\frac{-\log{\rm
E}_{{P}^{n}}f_{n}}{n}\right|\varliminf_{n\rightarrow\infty}\frac{-\log{\rm
E}_{{\overline{P}}^{n}}(1-f_{n})}{n}\geq r\right\\}$ $\displaystyle
B_{e}^{*}(r|P\|\overline{P}):=$
$\displaystyle\inf_{\\{f_{n}\\}}\left\\{\left.\varliminf_{n\rightarrow\infty}\frac{-\log{\rm
E}_{{P}^{n}}(1-f_{n})}{n}\right|\varliminf_{n\rightarrow\infty}\frac{-\log{\rm
E}_{{\overline{P}}^{n}}(1-f_{n})}{n}\geq r\right\\}.$

Then, the two quantities are calculated as

$\displaystyle B_{e}(r|P\|\overline{P})$
$\displaystyle=\min_{Q:D(Q\|\overline{P})\leq r}D(Q\|P)=\sup_{0\leq s\leq
1}\frac{-sr-\phi(s|P\|\overline{P})}{1-s}$ (2) $\displaystyle
B_{e}^{*}(r|P\|\overline{P})$ $\displaystyle=\min_{Q:D(Q\|\overline{P})\leq
r}D(Q\|P)+r-D(Q\|\overline{P})=\sup_{s\leq
0}\frac{-sr-\phi(s|P\|\overline{P})}{1-s}.$ (3)

The first expressions of (2) and (3) are illustrated by Figs. 1 and 2.

Figure 1: Figure of $B_{e}(r|P\|\overline{P})$

Figure 2: Figure of $B_{e}^{*}(r|P\|\overline{P})$ when $r0\geq r\geq
D(P\|\overline{P})$

Now, we define the new function $\overline{B}(r)$:

$\displaystyle\overline{B}_{e}(r):=\left\\{\begin{array}[]{ll}B_{e}(r|P\|\overline{P})&r\leq
D(P\|\overline{P})\\\
-B_{e}^{*}(r|P\|\overline{P})&r>D(P\|\overline{P}).\end{array}\right.$

Then, its graph is shown in Fig. 3.

Figure 3: Graph of $B_{e}(r)$

In order to give other characterizations of (2), we introduce a one-parameter
family

$\displaystyle
P_{s,P,\overline{P}}(dy):=\frac{1}{\Phi(s|P\|P)}(\frac{\partial\overline{P}}{\partial
P}(y))^{s}P(dy),$

which is abbreviated as $P_{s}$. Then, since $\phi(s)$ is $C^{1}$ continuous,

$\displaystyle D(P_{s}\|P_{1})$
$\displaystyle=(s-1)\phi^{\prime}(s)-\phi(s)\quad s\in(-\infty,1]$ (4)
$\displaystyle D(P_{0}\|P_{s})$ $\displaystyle=\phi(s)-s\phi^{\prime}(0)\quad
s\in[0,\infty).$ (5)

Since

$\displaystyle\frac{d(s-1)\phi^{\prime}(s)-\phi(s)}{ds}=-\phi^{\prime\prime}(s)<0,$

$D(P_{s}\|P_{1})$ is monotonically decreasing with respect to $s$.

As is mentioned in Theorem 4 of Blahut [2], when $r\leq D(P\|\overline{P})$,
there exists $s_{r}\in[0,1]$ such that

$\displaystyle\min_{Q:D(Q\|\overline{P})\leq r}D(Q\|P)=D(P_{s_{r}}\|P_{0}).$

Then, (4) and (5) imply that

$\displaystyle r=D(P_{s_{r}}\|P_{1})=(s_{r}-1)\phi(s_{r})-\phi(s_{r}).$

Thus, we obtain another expression.

$\displaystyle\min_{Q:D(Q\|\overline{P})\leq
r}D(Q\|P)=\min_{s\in[0,1]:D(P_{s}\|\overline{P})\leq r}D(P_{s}\|P).$ (6)

On the other hand,

$\displaystyle\frac{d}{ds}\frac{-sr-\phi(s|P\|\overline{P})}{1-s}=\frac{-r+(s-1)\phi^{\prime}(s)-\phi(s)}{(1-s)^{2}}=\frac{D(P_{s}\|P_{1})}{(1-s)^{2}}.$
(7)

Since $D(P_{s}\|P_{1})$ is monotonically decreasing with respect to $s$,
$\frac{d}{ds}\frac{-sr-\phi(s|P\|\overline{P})}{1-s}=0$ if and only if
$s=s_{r}$. The equation

$\displaystyle\min_{Q:D(Q\|\overline{P})\leq r}D(Q\|P)=\sup_{0\leq s\leq
1}\frac{-sr-\phi(s|P\|\overline{P})}{1-s}$ (8)

can be checked.

In the following, we present some explanations concerning (3). As is mentioned
by Han-Kobayashi[10] and Ogawa-Nagaoka[18], when
$r_{0}:=D(P_{-\infty}\|P_{1})\geq r\geq D(P\|\overline{P})$, the relation

$\displaystyle B_{e}^{*}(r|P\|\overline{P})=D(P_{s_{r}}\|P_{0})$

holds, where $s_{r}\in(-\infty,0]$ is defined as

$\displaystyle r=D(P_{s_{r}}\|P_{1})=(s_{r}-1)\phi(s_{r})-\phi(s_{r}).$

Thus, similar to (6) and (8), the relation

$\displaystyle\min_{Q:D(Q\|\overline{P})\leq r}D(Q\|P)+r-D(Q\|\overline{P})$
$\displaystyle=D(P_{s_{r}}\|P)=\sup_{s\leq
0}\frac{-sr-\phi(s|P\|\overline{P})}{1-s}$ (9)

holds, where $s_{r}\leq 0$ is defined by $D(P_{s_{r}}\|\overline{P})=r$[18].

As mentioned by Nakagawa-Kanaya[22], when $r\geq r_{0}$, the relation

$\displaystyle\min_{Q:D(Q\|\overline{P})\leq
r}D(Q\|P)+r-D(Q\|\overline{P})=D(P_{-\infty}\|P)+r-D(P_{-\infty}\|\overline{P})=\min_{Q:D(Q\|\overline{P})\leq
r_{0}}(D(Q\|P)+r_{0}-D(Q\|\overline{P}))+r-r_{0}$

holds. This bound is attained by the following randomized test. The hypothesis
$P$ is accepted with the probability only when the logarithmic likelihood
ratio takes the maximum value $r_{0}$. Since $D(P_{s}\|P_{1})<r$, (7) implies
that

$\displaystyle\sup_{s\leq
0}\frac{-sr-\phi(s|P\|\overline{P})}{1-s}=\lim_{s\leq-\infty}\frac{-sr-\phi(s|P\|\overline{P})}{1-s}=\lim_{s\leq-\infty}\frac{-sr_{0}-\phi(s|P\|\overline{P})}{1-s}+r-r_{0}$
$\displaystyle=$ $\displaystyle\min_{Q:D(Q\|\overline{P})\leq
r_{0}}(D(Q\|P)+r_{0}-D(Q\|\overline{P}))+r-r_{0}.$ (10)

###### Remark 1

The classical Hoeffding bound in information theory is due to Blahut[2] and
Csiszár-Longo[4]. The corresponding ideas in statistics were first put forward
by Hoeffding[16], from whom the bound received its name. Some authors prefer
to refer this bound as the Hoeffding-Blahut-Csiszár- Longo bound.

On the other hand, Han-Kobayashi[10] gave the first equation of (3), and
proved that this equation among non-randomized tests when $r_{0}\geq r\geq
D(P\|\overline{P})$. They pointed out that the minimum
$\min_{Q:D(Q\|\overline{P})\leq r}D(Q\|P)+r-D(Q\|\overline{P})$ can be
attained by $Q$ satisfying $D(Q\|\overline{P})=r$. Ogawa-Nagaoka[18]showed the
second equation of (3) for this case.

Nakagawa-Kanaya[22] proved the first equation when $r>r_{0}$. Indeed, as
pointed by Nakagawa-Kanaya[22], when $r>r_{0}$, any non-randomized test cannot
attain the minimum $\min_{Q:D(Q\|\overline{P})\leq
r}D(Q\|P)+r-D(Q\|\overline{P})$. In this case, the minimum
$\min_{Q:D(Q\|\overline{P})\leq r}D(Q\|P)+r-D(Q\|\overline{P})$ cannot be
attained by $Q$ satisfying $D(Q\|\overline{P})=r$.

##  III Main result: Adaptive method

Let us focus on two spaces, the set of input signals ${\cal X}$ and the set of
outputs ${\cal Y}$. In this case, the channel from ${\cal X}$ and ${\cal Y}$
is described by the map from the set ${\cal X}$ to the set of probability
distributions on ${\cal Y}$. That is, given a channel $W$ $W_{x}$ represents
the output distribution when the input is $x\in{\cal X}$. When ${\cal X}$ and
${\cal Y}$ have finite elements, the channel is given by transition matrix.
The main topic is the discrimination of two classical channels $W$ and
$\overline{W}$. In particular, we treat its asymptotic analysis when we can
use the unknown channel only $n$ times. That is, we discriminate two
hypotheses, the null hypothesis $H_{0}$ : $W^{n}$ versus the alternative
hypothesis $H_{1}$: ${\overline{W}}^{n}$, where $W^{n}$ and
${\overline{W}}^{n}$ are the $n$ uses of the channel $W$ and $\overline{W}$
Then, our problem is to decide which hypothesis is true based on $n$ inputs
$x_{1},\ldots,x_{n}$ and $n$ outputs $y_{1},\ldots,y_{n}$. In this setting, it
is allowed to choose the $k$-th input based on the previous $k-1$ output
adaptively. We choose the $k$-th input $x_{k}$ subject to the distribution
$P^{k}_{(x_{1},y_{1}),\ldots,(x_{k-1},y_{k-1})}(x_{k})$ on ${\cal X}$. That
is, the $k$-th input $x_{k}$ depends on $k$ conditional distributions
$\vec{P}^{k}=(P^{1},P^{2},\ldots,P^{k})$. Hence, our decision method is
described by $n$ conditional distributions
$\vec{P}^{n}=(P^{1},P^{2},\ldots,P^{n})$ and a $[0,1]$-valued function $f_{n}$
on $({\cal X}\times{\cal Y})^{n}$. In this case, when we choose $n$ inputs
$x_{1},\ldots,x_{n}$ and observe $n$ outputs $y_{1},\ldots,y_{n}$, we accept
the alternative hypothesis $\overline{W}$ with the probability
$f_{n}(x_{1},y_{1},\ldots,x_{n},y_{n})$. That is, our scheme is illustrated by
Fig. 4.

Figure 4: The adaptive method

In order to treat this problem mathematically, we introduce the following
notation. For a channel $W$ from ${\cal X}$ to ${\cal Y}$ and a distribution
$P$ on ${\cal X}$, we define two notations, the distribution $WP$ on ${\cal
X}\times{\cal Y}$ and the distribution $W\cdot P$ on ${\cal Y}$ as

$\displaystyle WP(x,y)$ $\displaystyle:=W_{x}(y)P(x)$ $\displaystyle W\cdot
P(x,y)$ $\displaystyle:=\int_{{\cal X}}W_{x}(y)P(dx).$

Using the distribution $WP$, we define two quantities:

$\displaystyle D(W\|\overline{W}|P)$ $\displaystyle:=D(WP\|\overline{W}P)$
$\displaystyle\phi(s|W\|\overline{W}|P)$
$\displaystyle:=\phi(s|WP\|\overline{W}P).$

Based on $k$ conditional distributions
$\vec{P}^{k}=(P^{1},P^{2},\ldots,P^{k})$, we define the following
distributions:

$\displaystyle Q_{W,\vec{P}^{n}}$ $\displaystyle:=WP^{n}WP^{n-1}\cdots WP^{1}$
$\displaystyle P_{W,\vec{P}^{n}}$ $\displaystyle:=P^{n}\cdot
Q_{W,\vec{P}^{n-1}}$ $\displaystyle Q_{s,W|\overline{W},\vec{P}^{n}}$
$\displaystyle:=P_{s,Q_{W,\vec{P}^{n}},Q_{\overline{W},\vec{P}^{n}}}$
$\displaystyle P_{s,W|\overline{W},\vec{P}^{n}}$ $\displaystyle:=P^{n}\cdot
Q_{s,W|\overline{W},\vec{P}^{n-1}}.$

Then, the first type of error probability is given by ${\rm
E}_{Q_{W,\vec{P}^{n}}}f_{n}$, and the second type of error probability is by
${\rm E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})$. In order to treat this
problem, we introduce the following quantities:

$\displaystyle C(W,\overline{W})$
$\displaystyle:=\lim_{n\rightarrow\infty}\frac{-1}{n}\log(\min_{\vec{P}^{n},f_{n}}{\rm
E}_{Q_{W,\vec{P}^{n}}}f_{n}+{\rm E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n}))$
$\displaystyle\beta_{n}^{*}(\epsilon)$
$\displaystyle:=\min_{\vec{P}^{n},f_{n}}\bigl{\\{}{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})\bigm{|}{\rm
E}_{Q_{W,\vec{P}^{n}}}f_{n}\leq\epsilon\bigr{\\}},$

and

$\displaystyle B(W\|\overline{W}):=$
$\displaystyle\sup_{\\{(\vec{P}^{n},f_{n})\\}}\left\\{\left.\varliminf_{n\rightarrow\infty}\frac{-\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})}{n}\right|\lim_{n\rightarrow\infty}{\rm
E}_{Q_{W,\vec{P}^{n}}}f_{n}=0\right\\}$ $\displaystyle
B^{*}(W\|\overline{W}):=$
$\displaystyle\inf_{\\{(\vec{P}^{n},f_{n})\\}}\left\\{\left.\varliminf_{n\rightarrow\infty}\frac{-\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})}{n}\right|\varliminf_{n\rightarrow\infty}{\rm
E}_{Q_{W,\vec{P}^{n}}}f_{n}<1\right\\}$ $\displaystyle
B_{e}(r|W\|\overline{W}):=$
$\displaystyle\sup_{\\{(\vec{P}^{n},f_{n})\\}}\left\\{\left.\varliminf_{n\rightarrow\infty}\frac{-\log{\rm
E}_{Q_{W,\vec{P}^{n}}}f_{n}}{n}\right|\varliminf_{n\rightarrow\infty}\frac{-\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})}{n}\geq r\right\\}$ $\displaystyle
B_{e}^{*}(r|W\|\overline{W}):=$
$\displaystyle\inf_{\\{(\vec{P}^{n},f_{n})\\}}\left\\{\left.\varliminf_{n\rightarrow\infty}\frac{-\log{\rm
E}_{Q_{W,\vec{P}^{n}}}(1-f_{n})}{n}\right|\varliminf_{n\rightarrow\infty}\frac{-\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})}{n}\geq r\right\\}.$

We obtain the following channel version of Stein’s lemma.

###### Theorem 1

Assume that $\phi(s|W_{x}\|\overline{W}_{x})$ is $C^{1}$ continuous, and

$\displaystyle\lim_{\epsilon\to+0}\frac{\phi(-\epsilon|W\|\overline{W})}{\epsilon}=\sup_{x\in{\cal
X}}D(W_{x}\|\overline{W}_{x}),$ (11)

where $\phi(s|W\|\overline{W}):=\sup_{x\in{\cal
X}}\phi(s|W_{x}|\overline{W}_{x})=\sup_{P\in{\cal P}({\cal
X})}\phi(s|W\|\overline{W}|P)$, and ${\cal P}({\cal X})$ is the set of
distributions on ${\cal X}$.

Then,

$\displaystyle
B(W\|\overline{W})=B^{*}(W\|\overline{W})=\overline{D}:=\sup_{x\in{\cal
X}}D(W_{x}\|\overline{W}_{x}).$ (12)

The following is another expression of Stein’s lemma.

###### Corollary 1

Under the same assumption,

$\displaystyle\lim_{n\rightarrow\infty}\frac{-1}{n}\log\beta_{n}^{*}(\epsilon)$
$\displaystyle=\sup_{x\in{\cal X}}D(W_{x}\|\overline{W}_{x}).$

Condition (11) can be replaced by another condition.

###### Lemma 1

When any element $x\in{\cal X}$ satisfies

$\displaystyle\phi^{\prime}(0|W_{x}\|\overline{W}_{x})=D(W_{x}\|\overline{W}_{x})$

and there exists a real number $\epsilon>0$ such that

$\displaystyle C_{1}:=\sup_{x\in{\cal
X}}\sup_{s\in[-\epsilon,0]}\frac{d^{2}\phi(s|W_{x}\|\overline{W}_{x})}{ds^{2}}$
$\displaystyle<\infty,$ (13)

then condition (11) holds.

In addition, we obtain a channel version of the Hoeffding bound.

###### Theorem 2

When

$\displaystyle\sup_{x\in{\cal
X}}\sup_{s\in[0,1]}\frac{d^{2}\phi(s|W_{x}\|\overline{W}_{x})}{ds^{2}}$
$\displaystyle<\infty$ (14)

and

$\displaystyle\sup_{x\in{\cal X}}D(\overline{W}_{x}\|W_{x})<\infty,$

then

$\displaystyle B_{e}(r|W\|\overline{W})$ $\displaystyle=\sup_{x\in{\cal
X}}\sup_{0\leq s\leq
1}\frac{-sr-\phi(s|W_{x}\|\overline{W}_{x})}{1-s}=\sup_{x\in{\cal
X}}\min_{Q:D(Q\|\overline{W}_{x})\leq r}D(Q\|W_{x}).$ (15)

###### Corollary 2

Under the same assumption,

$\displaystyle C(W,\overline{W})$ $\displaystyle=\sup_{x\in{\cal
X}}-\min_{0\leq s\leq 1}\phi(s|W_{x}\|\overline{W}_{x}).$ (16)

These arguments imply that adaptive improvement does not improve the
performance in the above senses. For example, when we apply the best input
$x_{M}:=\mathop{\rm argmax}_{x}D(W_{x}\|\overline{W}_{x})$ to all of $n$
channels, we can achieve the optimal performance in the sense of the Stein
bound. The same fact is true concerning the Hoeffding bound and the Chernoff
bound.

###### Proof:

The relation

$\displaystyle C(W,\overline{W})=\sup\\{r|B_{e}(r|W\|\overline{W})\geq r\\}$

holds. Since

$\displaystyle\sup\Bigl{\\{}r\Bigl{|}\sup_{x\in{\cal X}}\sup_{0\leq s\leq
1}\frac{-sr-\phi(s|W_{x}\|\overline{W}_{x})}{1-s}\geq r\Bigr{.}\Bigr{\\}}$
$\displaystyle=$ $\displaystyle\sup_{x\in{\cal
X}}\sup\Bigl{\\{}r\Bigl{|}\sup_{0\leq s\leq
1}\frac{-sr-\phi(s|W_{x}\|\overline{W}_{x})}{1-s}\geq r\Bigr{.}\Bigr{\\}}$
$\displaystyle=$ $\displaystyle\sup_{x\in{\cal X}}-\min_{0\leq s\leq
1}\phi(s|W_{x}\|\overline{W}_{x}),$

the relation (16) holds. ∎

The channel version of the Han-Kobayashi bound is given as follows.

###### Theorem 3

When $\phi(s|W_{x}\|\overline{W}_{x})$ is $C^{1}$ continuous, then

$\displaystyle B_{e}^{*}(r|W\|\overline{W})$ $\displaystyle=\sup_{s\leq
0}\frac{-sr-\phi(s|W\|\overline{W})}{1-s}=\inf_{P\in{\cal P}({\cal
X})}\sup_{s\leq 0}\frac{-sr-\phi(s|W\|\overline{W}|P)}{1-s}=\inf_{P\in{\cal
P}^{2}({\cal X})}\sup_{s\leq 0}\frac{-sr-\phi(s|W\|\overline{W}|P)}{1-s},$
(17)

where ${\cal P}^{2}({\cal X})$ is the distribution on ${\cal X}$ that takes
positive probability only on at most two elements.

As shown in Section IV, the equality

$\displaystyle\sup_{s\leq
0}\frac{-sr-\phi(s|W\|\overline{W})}{1-s}=\inf_{x\in{\cal X}}\sup_{s\leq
0}\frac{-sr-\phi(s|W_{x}\|\overline{W}_{x})}{1-s}$ (18)

does not necessarily hold in general. In order to understand the meaning of
this fact, we assume that the equation (18) does not hold. When we apply the
same input $x$ to all channels, the best performance cannot be achieved.
However, the best performance can be achieved by the following method. Assume
that the best input distribution $\mathop{\rm argmax}_{P\in{\cal P}^{2}({\cal
X})}\sup_{s\leq 0}\frac{-sr-\phi(s|W\|\overline{W}|P)}{1-s}$ has the support
$\\{x,x^{\prime}\\}$, and the probabilities $\lambda$ and $1-\lambda$. Then,
applying $x$ or $x^{\prime}$ to all channels with the probability $\lambda$
and $1-\lambda$, we can achieve the best performance in the sense of the Han-
Kobayashi bound. That is, the structure of optimal strategy of the Han-
Kobayashi bound is more complex than those of the above cases.

##  IV Simple example

In this section, we treat a simple example that does not satisfy (18). For
four given parameters $p,q,a>1,b>1$, we define the channels $W$ and
$\overline{W}$:

$\displaystyle W_{0}(0):=aq,\quad W_{0}(1):=1-aq,$
$\displaystyle\overline{W}_{0}(0):=q,\quad\overline{W}_{0}(1):=1-q,$
$\displaystyle W_{1}(0):=bq,\quad W_{1}(1):=1-bq,$
$\displaystyle\overline{W}_{1}(0):=q,\quad\overline{W}_{1}(1):=1-q.$

Then, we obtain

$\displaystyle\lim_{s\to-\infty}\frac{\phi(s|W_{0}\|\overline{W}_{0})}{s}=a,$
$\displaystyle\lim_{s\to-\infty}\frac{\phi(s|W_{1}\|\overline{W}_{1})}{s}=b.$

In this case,

$\displaystyle D(W_{0}\|\overline{W}_{0})=$ $\displaystyle ap\log
a+(1-ap)\log\frac{1-ap}{1-p}$ $\displaystyle D(W_{1}\|\overline{W}_{1})=$
$\displaystyle bq\log b+(1-bq)\log\frac{1-bq}{1-q}.$

When $a>b$ and $D(W_{0}\|\overline{W}_{0})<D(W_{1}\|\overline{W}_{1})$, the
magnitude relation between $\phi(s|W_{0}\|\overline{W}_{0})$ and
$\phi(s|W_{1}\|\overline{W}_{1})$ on $(-\infty,0)$ depends on
$s\in(-\infty,0)$. For example, the case of $a=100,b=1.5,p=0.0001,q=0.65$ is
shown in Fig. 5. In this case, $B_{e}^{*}(r|W_{0}\|\overline{W}_{0})$,
$B_{e}^{*}(r|W_{1}\|\overline{W}_{1})$, and $B_{e}^{*}(r|W\|\overline{W})$ are
calculated by Fig. 6. Then, the inequality (18) does not hold.

Figure 5: Magnitude relation between $\phi(s|W_{0}\|\overline{W}_{0})$ and
$\phi(s|W_{1}\|\overline{W}_{1})$ on $(-1,0)$. The upper solid line indicates
$\phi(s|W_{0}\|\overline{W}_{0})$, the dotted line indicates
$\phi(s|W_{1}\|\overline{W}_{1})$.

Figure 6:  Magnitude relation between $B_{e}^{*}(r|W_{0}\|\overline{W}_{0})$,
$B_{e}^{*}(r|W_{1}\|\overline{W}_{1})$, and $B_{e}^{*}(r|W\|\overline{W})$ on
$(-1,0)$. The upper solid line indicates
$B_{e}^{*}(r|W_{0}\|\overline{W}_{0})$, the dotted line indicates
$B_{e}^{*}(r|W_{1}\|\overline{W}_{1})$, and the lower solid line indicates
$B_{e}^{*}(r|W\|\overline{W})$.

##  V Application to adaptive quantum state discrimination

Quantum state discrimination between two states $\rho$ and $\sigma$ on a
$d$-dimensional system ${\cal H}$ with $n$ copies by one-way LOCC is
formulated as follows. We choose the first POVM $M_{1}$ and obtain the data
$y_{1}$ through the measurement $M_{1}$. In the $k$-th step, we choose the
$k$-th POVM $M_{k}((M_{1},y_{1}),\ldots,(M_{k-1},y_{k-1}))$ depending on
$(M_{1},y_{1}),\ldots,(M_{k-1},y_{k-1})$. Then, we obtain the $k$-th data
$y_{k}$ through $M_{k}((M_{1},y_{1}),\ldots,(M_{k-1},y_{k-1}))$. Therefore,
this problem can be regarded as classical channel discrimination with the
correspondence $W_{M}(y)=\mathop{\rm Tr}\nolimits M(y)\rho$ and
$\overline{W}_{M}(y)=\mathop{\rm Tr}\nolimits M(y)\sigma$. That is, in this
case, the set of input signal corresponds to the set of extremal points of the
set of POVMs on the given system ${\cal H}$. The proposed scheme is
illustrated in Fig. 7.

Figure 7: Adaptive quantum state discrimination

Now, we assume that $\rho>0$ and $\sigma>0$. In this case, ${\cal X}$ is
compact, and the map
$(s,M)\to\frac{d^{2}\phi(s|W_{M}\|\overline{W}_{M})}{ds^{2}}$ is continuous.
Then, the condition (13) holds. Therefore, one-way improvement does not
improve the performance in the sense of the Stein bound, the Chernoff bound,
the Hoeffding bound, or the Han-Kobayashi bound. That is, we obtain

$\displaystyle B(W\|\overline{W})=$ $\displaystyle
B^{*}(W\|\overline{W})=\max_{M:{\rm POVM}}D(P^{M}_{\rho}\|P^{M}_{\sigma})$
$\displaystyle B_{e}(r|W\|\overline{W})=$ $\displaystyle\max_{M:{\rm
POVM}}\sup_{0\leq s\leq
1}\frac{-sr-\phi(s|P^{M}_{\rho}\|P^{M}_{\sigma})}{1-s}$ $\displaystyle
B_{e}^{*}(r|W\|\overline{W})=$ $\displaystyle\sup_{s\leq
0}\frac{-sr-\max_{M:{\rm POVM}}\phi(s|P^{M}_{\rho}\|P^{M}_{\sigma})}{1-s}.$

Therefore, there exists a difference between one-way LOCC and collective
measurement.

##  VI Proof of the Stein bound: (12)

Now, we prove the Stein bound: (12). For any $x\in{\cal X}$, by choosing the
input $x$ in $n$ times, we obtain

$\displaystyle B(W\|\overline{W})\geq D(W_{x}\|\overline{W}_{x}).$

Taking the supremum, we have

$\displaystyle B(W\|\overline{W})\geq\sup_{x\in{\cal
X}}D(W_{x}\|\overline{W}_{x}).$

Furthermore, from the definition, it is trivial that

$\displaystyle B(W\|\overline{W})\leq B^{*}(W\|\overline{W}).$

Therefore, it is sufficient to show the strong converse part:

$\displaystyle B^{*}(W\|\overline{W})\leq\overline{D}.$ (19)

However, in preparation for the proof of (15), we present a proof of the weak
converse part:

$\displaystyle B(W\|\overline{W})\leq\overline{D}$ (20)

which is weaker argument than (19), and is valid without assumption (11). In
the following proof, it is essential to evaluate the KL-divergence concerning
the obtained data.

In order to prove (20), we prove that

$\displaystyle\varlimsup_{n\to\infty}-\frac{1}{n}\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})\leq\overline{D}$ (21)

when

$\displaystyle{\rm E}_{Q_{W,\vec{P}^{n}}}f_{n}\to 0.$ (22)

It follows from the definitions of $Q_{W,\vec{P}^{n}}$ and
$Q_{\overline{W},\vec{P}^{n}}$ that

$\displaystyle
D(Q_{W,\vec{P}^{n}}\|Q_{\overline{W},\vec{P}^{n}})=\sum_{k=1}^{n}D(W\|\overline{W}|P_{W,\vec{P}^{k}}).$

Since $-{\rm E}_{Q_{W,\vec{P}^{n}}}f_{n}\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}f_{n}\geq 0$, information processing
inequality concerning the KL divergence yields the following:

$\displaystyle-h({\rm E}_{Q_{W,\vec{P}^{n}}}(1-f_{n}))-({\rm
E}_{Q_{W,\vec{P}^{n}}}(1-f_{n}))\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})$ $\displaystyle\leq$
$\displaystyle{\rm E}_{Q_{W,\vec{P}^{n}}}(1-f_{n})(\log{\rm
E}_{Q_{W,\vec{P}^{n}}}(1-f_{n})-\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n}))+{\rm
E}_{Q_{W,\vec{P}^{n}}}f_{n}(\log{\rm E}_{Q_{W,\vec{P}^{n}}}f_{n}-\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}f_{n})$ $\displaystyle\leq$ $\displaystyle
D(Q_{W,\vec{P}^{n}}\|Q_{\overline{W},\vec{P}^{n}})=\sum_{k=1}^{n}D(W\|\overline{W}|P_{W,\vec{P}^{k}})\leq
n\overline{D}.$ (23)

That is,

$\displaystyle-\frac{1}{n}\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})\leq\frac{\overline{D}+\frac{1}{n}h({\rm
E}_{Q_{W,\vec{P}^{n}}}(1-f_{n}))}{{\rm E}_{Q_{W,\vec{P}^{n}}}(1-f_{n})}.$ (24)

Therefore, (22) yields (21).

Next, we prove the strong converse part, i.e., we show that

$\displaystyle{\rm E}_{Q_{W,\vec{P}^{n}}}(1-f_{n})\to 0$ (25)

when

$\displaystyle r:=\varliminf_{n\rightarrow\infty}\frac{-\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})}{n}>\overline{D}.$ (26)

Since

$\displaystyle\Phi(s|Q_{W,\vec{P}^{n}}\|Q_{\overline{W},\vec{P}^{n}})$
$\displaystyle=$
$\displaystyle\Phi(s|Q_{W,\vec{P}^{n-1}}\|Q_{\overline{W},\vec{P}^{n-1}})\left(\int_{{\cal
X}}\left(\int_{{\cal Y}}(\frac{\partial W_{x_{n}}^{\prime}}{\partial
W_{x_{n}}}(y_{n}))^{s}W_{x_{n}}(dy_{n})\right)P_{s,W|\overline{W},\vec{P}^{n}}(dx_{n})\right),$

we obtain

$\displaystyle\phi(s|Q_{W,\vec{P}^{n}}\|Q_{\overline{W},\vec{P}^{n}})=\phi(s|Q_{W,\vec{P}^{n-1}}\|Q_{\overline{W},\vec{P}^{n-1}})+\phi(s|W\|\overline{W}|P_{s,W|\overline{W},\vec{P}^{n}}).$
(27)

Applying (27) inductively, we obtain the relation

$\displaystyle\phi(s|Q_{W,\vec{P}^{n}}\|Q_{\overline{W},\vec{P}^{n}})=\sum_{k=1}^{n}\phi(s|W\|\overline{W}|P_{s,W|\overline{W},\vec{P}^{k}})\leq
n\phi(s|W\|\overline{W}).$ (28)

Since the information quantity $\phi(s|P\|\overline{P})$ satisfies the
information processing inequality, we have

$\displaystyle({\rm E}_{Q_{W,\vec{P}^{n}}}(1-f_{n}))^{1-s}({\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n}))^{s}$ $\displaystyle\leq$
$\displaystyle({\rm E}_{Q_{W,\vec{P}^{n}}}(1-f_{n}))^{1-s}({\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n}))^{s}+({\rm
E}_{Q_{W,\vec{P}^{n}}}f_{n})^{1-s}({\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}f_{n})^{s}$ $\displaystyle\leq$
$\displaystyle e^{\phi(s|Q_{W,\vec{P}^{n}}\|Q_{\overline{W},\vec{P}^{n}})}$
$\displaystyle\leq$ $\displaystyle e^{n\phi(s|W\|\overline{W})},$

for $s\leq 0$. Taking the logarithm, we obtain

$\displaystyle(1-s)\log{\rm E}_{Q_{W,\vec{P}^{n}}}(1-f_{n})\leq-s\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})+n\phi(s|W\|\overline{W}).$ (29)

That is,

$\displaystyle\frac{-1}{n}\log{\rm
E}_{Q_{W,\vec{P}^{n}}}(1-f_{n})\geq\frac{-s\frac{-1}{n}\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})-\phi(s|W\|\overline{W})}{1-s}.$

When $\varliminf_{n\rightarrow\infty}\frac{-\log{\rm
E}_{{\overline{P}}^{n}}(1-f_{n})}{n}\geq r$, the inequality

$\displaystyle
B_{e}^{*}(r|W\|\overline{W})\geq\varliminf_{n\rightarrow\infty}\frac{-1}{n}\log{\rm
E}_{Q_{W,\vec{P}^{n}}}(1-f_{n})\geq\frac{-sr-\phi(s|W\|\overline{W})}{1-s}$

holds. Taking the supremum, we obtain

$\displaystyle B_{e}^{*}(r|W\|\overline{W})\geq\sup_{s\leq
0}\frac{-sr-\phi(s|W\|\overline{W})}{1-s}.$

From conditions (11) and (26), there exists a small real number $\epsilon>0$
such that $r>\frac{\phi(-\epsilon|W\|\overline{W})}{-\epsilon}$. Thus,

$\displaystyle\sup_{s\leq
0}\frac{-sr-\phi(s|W\|\overline{W})}{1-s}\geq\frac{\epsilon
r-\phi(-\epsilon|W\|\overline{W})}{1+\epsilon}>0.$

Therefore, we obtain (25).

###### Remark 2

The technique of the strong converse part except for (28) was developed by
Nagaoka [19]. Hence, deriving (28) can be regarded as the main contribution in
this section of the present paper.

Proof of Lemma 1:

It is sufficient for a proof of (11) to show that the uniformity of the
convergence
$\frac{\phi(-\epsilon|W_{x}\|\overline{W}_{x})}{\epsilon}-D(W_{x}\|\overline{W}_{x})\to
0$ concerning $x\in{\cal X}$. Now, we choose $\epsilon>0$ satisfying condition
(13). Then, there exists $s\in[-\epsilon,0]$ such that
$\frac{\phi(-\epsilon|W_{x}\|\overline{W}_{x})}{\epsilon}-D(W_{x}\|\overline{W}_{x})=\frac{1}{2}\epsilon\phi(s|W_{x}\|\overline{W}_{x})\leq\frac{C_{1}}{2}\epsilon$.
Therefore, the condition (11) holds.

##  VII Proof of the Hoeffding bound: (15)

In this section, we prove the Hoeffding bound: (15). Since the inequality

$\displaystyle B_{e}(r|W\|\overline{W})\geq\sup_{x\in{\cal X}}\sup_{0\leq
s\leq 1}\frac{-sr-\phi(s|W_{x}\|\overline{W}_{x})}{1-s}=\sup_{x\in{\cal
X}}\min_{Q:D(Q\|\overline{W}_{x})\leq r}D(Q\|W_{x})$

is trivial, we prove the opposite inequality. In the following proof, the
geometric characterization Fig. 1 and the weak and the strong converse parts
are essential. Equation (6) guarantees that

$\displaystyle\sup_{x\in{\cal X}}\min_{Q:D(Q\|\overline{W}_{x})\leq
r}D(Q\|W_{x})=\sup_{x\in{\cal
X}}\min_{s\in[0,1]:D(P_{s,W_{x},\overline{W}_{x}}\|\overline{W}_{x})\leq
r}D(P_{s,W_{x},\overline{W}_{x}}\|W_{x}).$

For this purpose, for arbitrary $\epsilon>0$, we choose a channel
$V:V_{x}=P_{s(x),W_{x},\overline{W}_{x}}$ by

$\displaystyle s(x):=\mathop{\rm
argmin}_{s\in[0,1]:D(P_{s,W_{x},\overline{W}_{x}}\|\overline{W}_{x})\leq
r}D(P_{s,W_{x},\overline{W}_{x}}\|W_{x}).$

Assume that a sequence $\\{(\vec{P}^{n},f_{n})\\}$ satisfies

$\displaystyle\varlimsup_{n\to\infty}\frac{-1}{n}\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})=r.$

By substituting $V$ into $W$, the strong converse part of the Stein bound:(25)
implies that

$\displaystyle\lim{\rm E}_{Q_{V,\vec{P}^{n}}}(1-f_{n})=0.$

The condition (13) can be checked by the following relations:

$\displaystyle\frac{d\phi(t|P_{s(x),W_{x},\overline{W}_{x}}\|\overline{W}_{x})}{dt}$
$\displaystyle=(1-s(x))\phi^{\prime}(s(x)(1-t)+t|W_{x}\|\overline{W}_{x})$
(30)
$\displaystyle\frac{d^{2}\phi(t|P_{s(x),W_{x},\overline{W}_{x}}\|\overline{W}_{x})}{dt^{2}}$
$\displaystyle=(1-s(x))^{2}\phi^{\prime\prime}(s(x)(1-t)+t|W_{x}\|\overline{W}_{x}).$
(31)

Thus, by substituting $V$ and $W$ into $W$ and $\overline{W}$, the relation
(24) implies that

$\displaystyle\varlimsup_{n\to\infty}-\frac{1}{n}\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})\leq\sup_{x\in{\cal
X}}D(V_{x}\|W_{x}).$

Similar to (30) and (31), we can check the condition (13).

From the construction of $V$, we obtain

$\displaystyle\varlimsup_{n\to\infty}-\frac{1}{n}\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})\leq\max_{x}\min_{Q:D(Q\|\overline{W}_{x})\leq
r-\epsilon}D(Q\|W_{x}).$

The uniform continuity guarantees that

$\displaystyle\varlimsup_{n\to\infty}-\frac{1}{n}\log{\rm
E}_{Q_{\overline{W},\vec{P}^{n}}}(1-f_{n})\leq\max_{x}\min_{Q:D(Q\|\overline{W}_{x})\leq
r}D(Q\|W_{x}).$

Now, we show the uniformity of the function $r\mapsto\sup_{0\leq s\leq
1}\frac{-sr-\phi(s|W_{x}\|\overline{W}_{x})}{1-s}$ concerning $x$. As
mentioned in p. 82 of Hayashi[11], the relation

$\displaystyle\frac{d}{dr}\sup_{0\leq s\leq
1}\frac{-sr-\phi(s|W_{x}\|\overline{W}_{x})}{1-s}=\frac{s_{r}}{s_{r}-1}$

holds, where

$\displaystyle s_{r}:=\mathop{\rm argmax}_{0\leq s\leq
1}\frac{-sr-\phi(s|W_{x}\|\overline{W}_{x})}{1-s}.$

Since

$\displaystyle\frac{d}{dr}\left.\frac{-sr-\phi(s|W_{x}\|\overline{W}_{x})}{1-s}\right|_{s=s_{r}}=0,$

we have

$\displaystyle
r=(s_{r}-1)\phi^{\prime}(s_{r}|W_{x}\|\overline{W}_{x})-\phi(s_{r}|W_{x}\|\overline{W}_{x}).$

Since $-\phi(s_{r}|W_{x}\|\overline{W}_{x})\geq 0$, $(s_{r}-1)\leq 0$, and
$\phi^{\prime\prime}(s|W_{x}\|\overline{W}_{x})\geq 0$,

$\displaystyle
r\geq(s_{r}-1)\phi^{\prime}(s_{r}|W_{x}\|\overline{W}_{x})\geq(s_{r}-1)\phi^{\prime}(1|W_{x}\|\overline{W}_{x})=(1-s_{r})D(\overline{W}_{x}\|W_{x}).$

Thus,

$\displaystyle\frac{r}{D(\overline{W}_{x}\|W_{x})}\geq(1-s_{r}).$

Hence,

$\displaystyle|\frac{s_{r}}{s_{r}-1}|\leq\frac{1}{1-s_{r}}\leq\frac{D(\overline{W}_{x}\|W_{x})}{r}\leq\frac{\sup_{x}D(\overline{W}_{x}\|W_{x})}{r}.$

Therefore, the function $r\mapsto\sup_{0\leq s\leq
1}\frac{-sr-\phi(s|W_{x}\|\overline{W}_{x})}{1-s}$ is uniform continuous with
respect to $x$.

##  VIII Proof of the Han-Kobayashi bound: (17)

The inequality

$\displaystyle B_{e}(r|W\|\overline{W})\geq\sup_{s\leq
0}\frac{-sr-\phi(s|W\|\overline{W})}{1-s}.$ (32)

has been shown in Section VI, and the inequality

$\displaystyle B_{e}(r|W\|\overline{W})\leq\inf_{P\in{\cal P}^{2}({\cal
X})}\sup_{s\leq 0}\frac{-sr-\phi(s|W\|\overline{W}|P)}{1-s}$

can be easily check by considering the input $P$. Therefore, it is sufficient
to show the inequality

$\displaystyle\inf_{P\in{\cal P}^{2}({\cal X})}\sup_{s\leq
0}\frac{-sr-\phi(s|W\|\overline{W}|P)}{1-s}\leq\sup_{s\leq
0}\frac{-sr-\phi(s|W\|\overline{W})}{1-s}=\sup_{s\leq 0}\inf_{P\in{\cal
P}^{2}({\cal X})}\frac{-sr-\phi(s|W\|\overline{W}|P)}{1-s}.$ (33)

This relation seems to be guaranteed by the mini-max theorem (Chap. VI Prop.
2.3 of [5]). However, the function $\frac{-sr-\phi(s|W\|\overline{W}|P)}{1-s}$
is not necessarily concave concerning $s$ while it is convex concerning $P$.
Hence, this relation cannot be guaranteed by the mini-max theorem.

Now, we prove this inequality when the maximum $\max_{s\leq
0}\frac{-sr-\phi(s|W\|\overline{W})}{1-s}$ exists. Since
$\phi(s|W_{x}\|\overline{W}_{x})$ is convex concerning $s$,
$\phi(s|W\|\overline{W})$ is also convex concerning $s$. Then, we can define

$\displaystyle\partial^{+}\phi(s|W\|\overline{W}):=\lim_{\epsilon\to+0}\frac{\phi(s+\epsilon|W\|\overline{W})-\phi(s|W\|\overline{W})}{\epsilon}$
$\displaystyle\partial^{-}\phi(s|W\|\overline{W}):=\lim_{\epsilon\to+0}\frac{\phi(s|W\|\overline{W})-\phi(s-\epsilon|W\|\overline{W})}{\epsilon}.$

Hence, the real number $s_{r}:=\mathop{\rm argmax}_{s\leq
0}\frac{-sr-\phi(s|W\|\overline{W})}{1-s}$ satisfies that

$\displaystyle(1-s_{r})\partial^{-}\phi(s_{r}|W\|\overline{W})+\phi(s_{r}|W\|\overline{W})\leq-r\leq(1-s_{r})\partial^{+}\phi(s_{r}|W\|\overline{W})+\phi(s_{r}|W\|\overline{W}).$

That is, there exists $\lambda\in[0,1]$ such that

$\displaystyle-r=(1-s_{r})(\lambda\partial^{+}\phi(s_{r}|W\|\overline{W})+(1-\lambda)\partial^{-}\phi(s_{r}|W\|\overline{W}))+\phi(s_{r}|W\|\overline{W}).$
(34)

For an arbitrary real number $1>\epsilon>0$, there exists $1>\delta>0$ such
that

$\displaystyle\frac{\phi(s+\delta|W\|\overline{W})-\phi(s|W\|\overline{W})}{\delta}$
$\displaystyle\leq\partial^{+}\phi(s|W\|\overline{W})+\epsilon$ (35)
$\displaystyle\frac{\phi(s|W\|\overline{W})-\phi(s-\delta|W\|\overline{W})}{\delta}$
$\displaystyle\geq\partial^{-}\phi(s|W\|\overline{W})-\epsilon.$ (36)

Then, we choose $x^{+},x^{-}\in{\cal X}$ such that

$\displaystyle\phi(s_{r}+\lambda\delta|W\|\overline{W})-\delta\epsilon\leq\phi(s_{r}+\lambda\delta|W_{x^{+}}\|\overline{W}_{x^{+}})\leq\phi(s_{r}+\lambda\delta|W\|\overline{W})$
(37)
$\displaystyle\phi(s_{r}-(1-\lambda)\delta|W\|\overline{W})-\delta\epsilon\leq\phi(s_{r}-(1-\lambda)\delta|W_{x^{-}}\|\overline{W}_{x^{-}})\leq\phi(s_{r}-(1-\lambda)\delta|W\|\overline{W}).$
(38)

Thus, (37) implies that

$\displaystyle\frac{\phi(s_{r}+\lambda\delta|W_{x^{+}}\|\overline{W}_{x^{+}})-\phi(s_{r}-(1-\lambda)\delta|W_{x^{+}}\|\overline{W}_{x^{+}})}{\delta}$
$\displaystyle\geq$
$\displaystyle\frac{\phi(s_{r}+\lambda\delta|W\|\overline{W})-\delta\epsilon-\phi(s_{r}-(1-\lambda)\delta|W\|\overline{W})}{\delta}$
$\displaystyle\geq$
$\displaystyle\frac{\phi(s_{r}+\lambda\delta|W\|\overline{W})-\phi(s_{r}+|W\|\overline{W})+\phi(s_{r}+|W\|\overline{W})-\phi(s_{r}-(1-\lambda)\delta|W\|\overline{W})-\delta\epsilon}{\delta}$
$\displaystyle\geq$
$\displaystyle\frac{\lambda\delta\partial^{+}\phi(s_{r}|W\|\overline{W})+(1-\lambda)\delta(\partial^{-}\phi(s_{r}+|W\|\overline{W})-\epsilon)-\delta\epsilon}{\delta}$
$\displaystyle=$
$\displaystyle\lambda\partial^{+}\phi(s_{r}|W\|\overline{W})+(1-\lambda)\partial^{-}\phi(s_{r}+|W\|\overline{W})-\epsilon.$
(39)

Similarly, (38) implies that

$\displaystyle\frac{\phi(s_{r}+\lambda\delta|W_{x^{-}}\|\overline{W}_{x^{-}})-\phi(s_{r}-(1-\lambda)\delta|W_{x^{-}}\|\overline{W}_{x^{-}})}{\delta}$
$\displaystyle\leq$
$\displaystyle\lambda\partial^{+}\phi(s_{r}|W\|\overline{W})+(1-\lambda)\partial^{-}\phi(s_{r}+|W\|\overline{W})+\epsilon.$
(40)

Therefore, there exists a real number $\lambda^{\prime}\in[0,1]$ such that

$\displaystyle\left|\frac{\varphi(s_{r}+\lambda\delta|\lambda^{\prime})-\varphi(s_{r}-(1-\lambda)\delta|\lambda^{\prime})}{\delta}-(\lambda\partial^{+}\phi(s_{r}|W\|\overline{W})+(1-\lambda)\partial^{-}\phi(s_{r}+|W\|\overline{W}))\right|$
$\displaystyle\leq$ $\displaystyle\epsilon.$ (41)

where

$\displaystyle\varphi(s|\lambda^{\prime}):=\lambda^{\prime}\phi(s|W_{x^{+}}\|\overline{W}_{x^{+}})+(1-\lambda^{\prime})\phi(s|W_{x^{-}}\|\overline{W}_{x^{-}}).$

Thus, there exists
$\overline{s}_{r}\in[s_{r}-(1-\lambda)\delta,s_{r}+\lambda\delta]$ such that

$\displaystyle\left|\varphi^{\prime}(\overline{s}_{r}|\lambda^{\prime})-(\lambda\partial^{+}\phi(s_{r}|W\|\overline{W})+(1-\lambda)\partial^{-}\phi(s_{r}|W\|\overline{W}))\right|\leq\epsilon.$
(42)

The relation (41) also implies that

$\displaystyle 0\leq$
$\displaystyle\varphi(s_{r}-(1-\lambda)\delta|\lambda^{\prime})-\varphi(\overline{s}_{r}|\lambda^{\prime})\leq\varphi(s_{r}-(1-\lambda)\delta|\lambda^{\prime})-\varphi(s_{r}+\lambda\delta|\lambda^{\prime})$
$\displaystyle\leq$
$\displaystyle[\epsilon-((\lambda\partial^{+}\phi(s_{r}|W\|\overline{W})+(1-\lambda)\partial^{-}\phi(s_{r}|W\|\overline{W}))]\delta$
$\displaystyle\leq$
$\displaystyle(\epsilon-\partial^{-}\phi(s_{r}|W\|\overline{W}))\delta.$ (43)

Since

$\displaystyle\phi(s_{r}-(1-\lambda)\delta|W_{x^{+}}\|\overline{W}_{x^{+}})\geq\phi(s_{r}+\lambda\delta|W_{x^{+}}\|\overline{W}_{x^{+}}),$

relations (36) and (37) guarantee that

$\displaystyle 0\leq$
$\displaystyle\phi(s_{r}-(1-\lambda)\delta|W\|\overline{W})-\phi(s_{r}-(1-\lambda)\delta|W_{x^{+}}\|\overline{W}_{x^{+}})$
$\displaystyle\leq$
$\displaystyle\phi(s_{r}-(1-\lambda)\delta|W\|\overline{W})-\phi(s_{r}+\lambda\delta|W\|\overline{W})+\phi(s_{r}+\lambda\delta|W\|\overline{W})-\phi(s_{r}+\lambda\delta|W_{x^{+}}\|\overline{W}_{x^{+}})$
$\displaystyle\leq$
$\displaystyle(\epsilon-\partial^{-}\phi(s_{r}|W\|\overline{W}))(s_{r}+\lambda\delta-\overline{s}_{r})+\delta\epsilon$
$\displaystyle\leq$
$\displaystyle(\epsilon-\partial^{-}\phi(s_{r}|W\|\overline{W}))\delta+\delta\epsilon=(2\epsilon-\partial^{-}\phi(s_{r}|W\|\overline{W}))\delta.$

Therefore,

$\displaystyle 0\leq$
$\displaystyle\phi(s_{r}-(1-\lambda)\delta|W\|\overline{W})-\varphi(s_{r}-(1-\lambda)\delta|\lambda^{\prime})$
$\displaystyle\leq$
$\displaystyle\lambda^{\prime}(\phi(s_{r}-(1-\lambda)\delta|W\|\overline{W})-\phi(s_{r}-(1-\lambda)\delta|W_{x^{+}}\|\overline{W}_{x^{+}}))+(1-\lambda^{\prime})(\phi(s_{r}-(1-\lambda)\delta|W\|\overline{W})-\phi(s_{r}-(1-\lambda)\delta|W_{x^{-}}\|\overline{W}_{x^{-}}))$
$\displaystyle\leq$
$\displaystyle\lambda^{\prime}(\epsilon-\partial^{-}\phi(s_{r}|W\|\overline{W}))\delta+(1-\lambda^{\prime})\delta\epsilon\leq(\epsilon-\partial^{-}\phi(s_{r}|W\|\overline{W}))\delta.$
(44)

Since (36) implies that

$\displaystyle\phi(s_{r}-(1-\lambda)\delta|W\|\overline{W})-\phi(s_{r}|W\|\overline{W})\leq(\epsilon-\partial^{-}\phi(s_{r}|W\|\overline{W}))\delta,$

relations (43) and (44) guarantee that

$\displaystyle|\varphi(\overline{s}_{r}|\lambda^{\prime})-\phi(s_{r}|W\|\overline{W})|$
$\displaystyle\leq$
$\displaystyle|\varphi(\overline{s}_{r}|\lambda^{\prime})-\varphi(s_{r}-(1-\lambda)\delta|\lambda^{\prime})|+|\varphi(s_{r}-(1-\lambda)\delta|\lambda^{\prime})-\phi(s_{r}-(1-\lambda)\delta|W\|\overline{W})|+|\phi(s_{r}-(1-\lambda)\delta|W\|\overline{W})-\phi(s_{r}|W\|\overline{W})|$
$\displaystyle\leq$
$\displaystyle(4\epsilon-3\partial^{-}\phi(s_{r}|W\|\overline{W}))\delta\leq
C_{2}\delta,$ (45)

where

$\displaystyle C_{2}:=4-3\partial^{-}\phi(s_{r}|W\|\overline{W}))\geq
4\epsilon-3\partial^{-}\phi(s_{r}|W\|\overline{W}).$

Note that the constant $C_{2}$ does not depend on $\epsilon$ or $\delta$.

We choose a real number
$\overline{r}:=(1-\overline{s}_{r})\varphi(\overline{s}_{r}|\lambda^{\prime})+\varphi^{\prime}(\overline{s}_{r}|\lambda^{\prime})$.
Then, (45), (42), and the inequality $|s_{r}-\overline{s}_{r}|\leq\delta$
imply that

$\displaystyle|\overline{r}-r|$ $\displaystyle\leq$
$\displaystyle|(1-\overline{s}_{r})\varphi(\overline{s}_{r}|\lambda^{\prime})-(1-s_{r})\phi(s_{r}|W\|\overline{W}))|+|\varphi^{\prime}(\overline{s}_{r}|\lambda^{\prime})-(\lambda\partial^{+}\phi(s_{r}|W\|\overline{W})+(1-\lambda)\partial^{-}\phi(s_{r}+|W\|\overline{W}))|$
$\displaystyle\leq$
$\displaystyle|(1-\overline{s}_{r})(\varphi(\overline{s}_{r}|\lambda^{\prime})-\phi(s_{r}|W\|\overline{W}))|+|\phi(s_{r}|W\|\overline{W})(s_{r}-\overline{s}_{r})|+|\varphi^{\prime}(\overline{s}_{r}|\lambda^{\prime})-(\lambda\partial^{+}\phi(s_{r}|W\|\overline{W})+(1-\lambda)\partial^{-}\phi(s_{r}+|W\|\overline{W}))|$
$\displaystyle\leq$
$\displaystyle(1-\overline{s}_{r})C_{2}\delta+|\phi(s_{r}|W\|\overline{W})|\delta+\epsilon\leq
C_{3}\delta+\epsilon,$ (46)

where

$\displaystyle C_{3}:=$
$\displaystyle(2-s_{r})C_{2}+|\phi(s_{r}|W\|\overline{W})|$
$\displaystyle\geq$
$\displaystyle(1-s_{r}+(1-\lambda)\delta)C_{2}+|\phi(s_{r}|W\|\overline{W})|$
$\displaystyle\geq$
$\displaystyle(1-\overline{s}_{r})C_{2}+|\phi(s_{r}|W\|\overline{W})|.$

Note that the constant $C_{3}$ does not depend on $\epsilon$ or $\delta$. The
function $\frac{-s\overline{r}-\varphi(s|\lambda^{\prime})}{1-s}$ takes the
maximum at $s=\overline{s}_{r}$. Using (45) and (46), we can check that this
maximum is approximated by the value
$\frac{-s_{r}r-\phi(s_{r}||W\|\overline{W})}{1-s_{r}}$ as

$\displaystyle|\frac{-\overline{s}_{r}\overline{r}-\varphi(\overline{s}_{r}|\lambda^{\prime})}{1-\overline{s}_{r}}-\frac{-s_{r}r-\phi(s_{r}|W\|\overline{W})}{1-s_{r}}|$
$\displaystyle\leq$
$\displaystyle|\frac{-\overline{s}_{r}\overline{r}-\varphi(\overline{s}_{r}|\lambda^{\prime})}{1-\overline{s}_{r}}-\frac{-s_{r}r-\phi(s_{r}|W\|\overline{W})}{1-\overline{s}_{r}}|+|\frac{-s_{r}r-\phi(s_{r}|W\|\overline{W})}{1-\overline{s}_{r}}-\frac{-s_{r}r-\phi(s_{r}|W\|\overline{W})}{1-s_{r}}|$
$\displaystyle\leq$
$\displaystyle|\frac{\overline{s}_{r}\overline{r}-s_{r}r}{1-\overline{s}_{r}}|+|\frac{\varphi(\overline{s}_{r}|\lambda^{\prime})-\phi(s_{r}|W\|\overline{W})}{1-\overline{s}_{r}}|+|\frac{-s_{r}r-\phi(s_{r}|W\|\overline{W})(s_{r}-\overline{s}_{r})}{(1-\overline{s}_{r})(1-s_{r})}$
$\displaystyle\leq$
$\displaystyle\frac{|(\overline{s}_{r}(\overline{r}-r)|+|r(\overline{s}_{r}-s_{r})|}{1-\overline{s}_{r}}+|\frac{\varphi(\overline{s}_{r}|\lambda^{\prime})-\phi(s_{r}|W\|\overline{W})}{1-\overline{s}_{r}}|+|\frac{-s_{r}r-\phi(s_{r}|W\|\overline{W})}{(1-s_{r}+1)(1-s_{r})}|\delta$
$\displaystyle\leq$
$\displaystyle\frac{(-s_{r}+\delta)(C_{3}\delta+\epsilon)+r\delta}{2-s_{r}}+|\frac{C_{2}\epsilon}{2-s_{r}}|+|\frac{-s_{r}r-\phi(s_{r}|W\|\overline{W})}{(2-s_{r})(1-s_{r})}|\delta$
$\displaystyle\leq$ $\displaystyle C_{4}\epsilon+C_{5}\delta,$ (47)

where we choose $C_{4}$ and $C_{5}$ as follows.

$\displaystyle C_{4}:=$
$\displaystyle\frac{-s_{r}+1}{2-s_{r}}+|\frac{C_{2}}{2-s_{r}}|$
$\displaystyle\geq$
$\displaystyle\frac{-s_{r}+\delta}{2-s_{r}}+|\frac{C_{2}}{2-s_{r}}|$
$\displaystyle C_{5}:=$
$\displaystyle\frac{(-s_{r}+1)C_{3}+r\delta}{2-s_{r}}+|\frac{-s_{r}r-\phi(s_{r}|W\|\overline{W})}{(2-s_{r})(1-s_{r})}|$
$\displaystyle\geq$
$\displaystyle\frac{(-s_{r}+\delta)C_{3}+r\delta}{2-s_{r}}+|\frac{-s_{r}r-\phi(s_{r}|W\|\overline{W})}{(2-s_{r})(1-s_{r})}|.$

Note that the constants $C_{4}$ and $C_{5}$ do not depend on $\delta$ or
$\epsilon$. Since

$\displaystyle|\frac{-sr-\varphi(s|\lambda^{\prime})}{1-s}-\frac{-s\overline{r}-\varphi(s|\lambda^{\prime})}{1-s}|\leq\frac{-s}{1-s}|r-\overline{r}|\leq|r-\overline{r}|,$

(46) implies that

$\displaystyle|\max_{s\leq
0}\frac{-sr-\varphi(s|\lambda^{\prime})}{1-s}-\max_{s\leq
0}\frac{-s\overline{r}-\varphi(s|\lambda^{\prime})}{1-s}|\leq|r-\overline{r}|\leq
C_{3}\delta+\epsilon.$ (48)

Since $\varphi(s|\lambda^{\prime})\leq\phi(s|W\|\overline{W})$, (48) and (47)
guarantee that

$\displaystyle 0\leq\max_{s\leq
0}\frac{-sr-\varphi(s|\lambda^{\prime})}{1-s}-\frac{-s_{r}r-\phi(s_{r}|W\|\overline{W})}{1-s_{r}}\leq(C_{4}+1)\epsilon+(C_{3}+C_{5})\delta.$
(49)

We define the distribution $P_{\lambda^{\prime}}\in{\cal P}^{2}({\cal X})$ by

$\displaystyle P_{\lambda^{\prime}}(x^{+})=\lambda^{\prime},\quad
P_{\lambda^{\prime}}(x^{-})=1-\lambda^{\prime}.$

Since the function $x\to\log x$ is concave, the inequality

$\displaystyle\varphi(s|\lambda^{\prime})\leq\phi(s|W\|\overline{W}|P_{\lambda^{\prime}})$
(50)

holds. Hence, (49) and (50) imply that

$\displaystyle 0\leq$ $\displaystyle\inf_{P\in{\cal P}^{2}({\cal
X})}\max_{s\leq
0}\frac{-sr-\phi(s|W\|\overline{W}|P)}{1-s}-\frac{-s_{r}r-\phi(s_{r}|W\|\overline{W})}{1-s_{r}}$
$\displaystyle\leq$ $\displaystyle\max_{s\leq
0}\frac{-sr-\phi(s|W\|\overline{W}|P_{\lambda^{\prime}})}{1-s}-\frac{-s_{r}r-\phi(s_{r}|W\|\overline{W})}{1-s_{r}}\leq(C_{4}+1)\epsilon+(C_{3}+C_{5})\delta.$

We take the limit $\delta\to+0$. After this limit, we take the limit
$\epsilon\to+0$. Then, we obtain (33).

Next, we prove the inequality (33) when the maximum $\max_{s\leq
0}\frac{-sr-\phi(s|W\|\overline{W})}{1-s}$ does not exist. The real number
$R:=\lim_{s\to-\infty}\frac{\phi(s|W\|\overline{W})}{s}$ satisfies $r\geq-R$.
Thus,

$\displaystyle\sup_{s\leq 0}\frac{-sr-\phi(s_{r}|W\|\overline{W})}{1-s}=r+R.$

For any $\epsilon>0$, there exists $s_{0}<0$ such that any $s<s_{0}$ satisfies
that

$\displaystyle
R\leq\frac{\phi(s_{0}|W\|\overline{W})-\phi(s|W\|\overline{W})}{s_{0}-s}\leq
R+\epsilon.$

We choose $x_{0}$ such that

$\displaystyle\phi(s_{0}-1|W\|\overline{W})-\epsilon\leq\phi(s_{0}-1|W_{x_{0}}\|\overline{W}_{x_{0}})\leq\phi(s_{0}-1|W\|\overline{W}).$

Thus,

$\displaystyle\phi(s_{0}|W_{x_{0}}\|\overline{W}_{x_{0}})-\phi(s_{0}-1|W_{x_{0}}\|\overline{W}_{x_{0}})\leq\phi(s_{0}|W\|\overline{W})-\phi(s_{0}-1|W\|\overline{W})+\epsilon\leq
R+2\epsilon.$

Hence, for any $s<s_{0}$,

$\displaystyle\frac{\phi(s_{0}|W_{x_{0}}\|\overline{W}_{x_{0}})-\phi(s|W_{x_{0}}\|\overline{W}_{x_{0}})}{s_{0}-s}$
$\displaystyle\leq$
$\displaystyle\phi(s_{0}|W_{x_{0}}\|\overline{W}_{x_{0}})-\phi(s_{0}-1|W_{x_{0}}\|\overline{W}_{x_{0}})$
$\displaystyle\leq$
$\displaystyle\phi(s_{0}|W\|\overline{W})-\phi(s_{0}-1|W\|\overline{W})+\epsilon\leq
R+2\epsilon.$

Thus,

$\displaystyle-r\leq
R\leq\lim_{s\to-\infty}\frac{\phi(s|W_{x_{0}}\|\overline{W}_{x_{0}})}{s}\leq
R+2\epsilon.$

Therefore,

$\displaystyle\sup_{s\leq
0}\frac{-sr-\phi(s_{r}|W_{x_{0}}\|\overline{W}_{x_{0}})}{1-s}\leq
r+R+2\epsilon.$

Taking $\epsilon\to 0$, we obtain (33).

##  IX Concluding remarks and future study

We have obtained a general asymptotic formula for the discrimination of two
classical channels with adaptive improvement concerning the several asymptotic
formulations. We have proved that any adaptive method does not improve the
asymptotic performance. That is, the non-adaptive method attains the optimum
performance in these asymptotic formulations. Applying the obtained result to
the discrimination of two quantum states by one-way LOCC, we have shown that
one-way communication does not improve the asymptotic performance in these
senses.

On the other hand, as shown in Section 3.5 of Hayashi[11], we cannot improve
the asymptotic performance of the Stein bound even if we extend the class of
our measurement to the separable POVM in the $n$-partite system. Hence, two-
way LOCC does not improve the Stein bound. However, other asymptotic
performances in two-way LOCC and separable POVM have not been solved.
Therefore, it is an interesting problem to solve whether two-way LOCC improves
the asymptotic performance for other than the Stein’s bound.

Furthermore, the discrimination of two quantum channels (TP-CP maps) is an
interesting related topic. An open problem remains as to whether choosing
input quantum states adaptively improves the discrimination performance in an
asymptotic framework. The solution to this problem will be sought in a future
study.

## Acknowledgments

The author would like to thank Professor Emilio Bagan, Professor Ramon Munoz
Tapia, and Dr. John Calsamiglia for their interesting discussions. The present
study was supported in part by MEXT through a Grant-in-Aid for Scientific
Research on Priority Area “Deepening and Expansion of Statistical Mechanical
Informatics (DEX-SMI),” No. 18079014.

## References

  * [1] K.M.R. Audenaert, J. Calsamiglia, R. Munoz-Tapia, E. Bagan, Ll. Masanes, A. Acin and F. Verstraete, “Discriminating States: The Quantum Chernoff Bound,” Phys. Rev. Lett., 98, 160501 (2007).
  * [2] R.E. Blahut, “Hypothesis Testing and Information Theory,” IEEE Trans. Infor. Theory, 20, 405–417 (1974).
  * [3] H. Chernoff, “A Measure of Asymptotic Efficiency for Tests of a Hypothesis based on the Sum of Observations,” Ann. Math. Stat., 23, 493-507 (1952).
  * [4] I. Csiszár and G. Longo, “On the error exponent for source coding and testing simple hypotheses,” Studia Sci. Math. Hungarica, 6, 181–191 (1971).
  * [5] I. Ekeland and R. Téman, Convex Analysis and Variational Problems, (North-Holland, 1976); (SIAM, 1999).
  * [6] V.V. Fedorov, Theory of Optimal Experiments, Academic Press (1972).
  * [7] A. Fujiwara, “Strong consistency and asymptotic efficiency for adaptive quantum estimation problems,” J. Phys. A: Math. Gen., 39, No 40, 12489-12504, (2006).
  * [8] T.S. Han, “Hypothesis testing with the general source,” IEEE Trans. Infor. Theory, 46, 2415–2427, (2000).
  * [9] T. S. Han: Information-Spectrum Methods in Information Theory, (Springer-Verlag, New York, 2002) (Originally published by Baifukan 1998 in Japanese)
  * [10] T. S. Han and K. Kobayashi, “The strong converse theorem for hypothesis testing,” IEEE Trans. Infor. Theory, 35, 178-180 (1989).
  * [11] M. Hayashi, Quantum Information: An Introduction, Springer, Berlin (2006). (Originally published by Saiensu-sha 2004 in Japanese)
  * [12] M. Hayashi, “Error Exponent in Asymmetric Quantum Hypothesis Testing and Its Application to Classical-Quantum Channel coding,” Phys. Rev. A, 76, 062301 (2007).
  * [13] M. Hayashi and K. Matsumoto, “Statistical model with measurement degree of freedom and quantum physics,” Surikaiseki Kenkyusho Kokyuroku, 1055, 96–110, (1998). (In Japanese) (Its English translation is also appeared as Chapter 13 of Asymptotic Theory of Quantum Statistical Inference, M. Hayashi eds.)
  * [14] M. Hayashi and K. Matsumoto, “Two Kinds of Bahadur Type Bound in Adaptive Experimental Design,” IEICE Trans., J83-A, 629-638 (2000). (In Japanese)
  * [15] F. Hiai and D. Petz, “The proper formula for relative entropy and its asymptotics in quantum probability,” Comm. Math. Phys., 143, 99–114, (1991).
  * [16] W. Hoeffding, “Asymptotically optimal test for multinomial distributions,” Ann. Math. Stat., 36, 369-401 (1965).
  * [17] T. Ogawa and M. Hayashi, “On Error Exponents in Quantum Hypothesis Testing,” IEEE Trans. Infor. Theory, 50, 1368 –1372 (2004).
  * [18] T. Ogawa and H. Nagaoka, “Strong converse and Stein’s lemma in quantum hypothesis testing,” IEEE Trans. Infor. Theory, 46, 2428–2433 (2000);
  * [19] H. Nagaoka, “Strong converse theorems in quantum information theory,” Proc. ERATO Conference on Quantum Information Science (EQIS) 2001, 33 (2001). It is also appeared as Chapter 4 of Asymptotic Theory of Quantum Statistical Inference, M. Hayashi eds.)
  * [20] H. Nagaoka, “The Converse Part of The Theorem for Quantum Hoeffding Bound”, arxiv.org E-print quant-ph/0611289 (2006).
  * [21] H. Nagaoka and M. Hayashi, “An information-spectrum approach to classical and quantum hypothesis testing,” IEEE Trans. Infor. Theory, 53, 534-549 (2007).
  * [22] K. Nakagawa and F. Kanaya, “On the converse theorem in statistical hypothesis testing,” IEEE Trans. Infor. Theory, 39, Issue 2, 623 - 628 (1993).
  * [23] M. Nussbaum and A. Szkoła, “A lower bound of Chernoff type in quantum hypothesis testing”, arxiv.org E-print quant-ph/0607216 (2006).
  * [24] M. Nussbaum and A. Szkoła, “The Chernoff lower bound in quantum hypothesis testing”, Preprint No. 69/2006, MPI MiS Leipzig.


# Exact Results for Random Two-way Selections

Bin Zhoua,b<EMAIL_ADDRESS>Shu-Jia Qinc Xiao-Pu Hand Zhe Hea Jia-
Rong Xiea Bing-Hong Wanga,e a Department of Modern Physics, University of
Science and Technology of China, Hefei, 230026, China
b Jiangsu University of Science and Technology, Zhenjiang, Jiangsu 212003,
China
c State Key Lab of Robotics, Shenyang Institute of Automation, Chinese Academy
of Sciences, Shenyang, 110016, China
d Institute of Information Economy and Alibaba Business College, Hangzhou
Normal University, Hangzhou, 310036, China
e The Research Center for Complex System Science, University of Shanghai for
Science and Technology, Shanghai, 200093 China

###### Abstract

Two-way selections play an important role in human social life. In this paper,
we analyze the minimum model of random two-way selections system and provide
its exact results on the matching ratio. Defining two basic relative ratios:
$\eta$ for the ratio of selection quantities from both sides, and $\xi$ for
the ratio of the total number of states to the smaller number of two sides, we
find the matching rate $P$ of two-way selections trends toward an inverse
proportion to both $\eta$ and $\xi$, in agreement with the numerical
simulations. We also surprisingly notice that, most of the empirical data of
the matchmaking fairs, the typical real-world two-way selections, are
completely included in the range predicted by our model. More interestingly,
by the fitting of empirical data, we find that the average number of
characters in real-world human sexual chosen is about 15, which is generally
in agreement with daily experiences, implying our model would be useful for
the estimation on the main factors of affecting the results of two-way
selections.

###### pacs:

89.75.-k, 89. 65.Ef, 05.45.-a

##  I Introduction

Two-way selections between people are very common in daily life, such as the
marriage selections between men and women, the selections between seekers and
recruiters, and trades between buyers and sellers. In a sense, two-way
selections can be regarded as the base in the build of many social
relationships. Generally, the participants in a two-way selection process
usually consider many characters of the people in the other side. For
instance, in the human marriage selections, her/his looks, personality,
wealth, sense of humor, and so on, are usually in the considerations. These
characters, which generally can not clearly be distinguished and are difficult
to be estimated through traditional methods such as psychological test and
social survey, deeply affect the result of selection. Furthermore, two-way
selections are usually affected by many factors, such as, the size of members
on the two sides and the corresponding ratio. For example, the supply-demand
ratio on market would deeply influence on the prices and business practices.
Therefore, it would be significant to study the basic laws dominating the two-
way selections, including the factors affecting the matching rate and the
method for estimating the total number of characters affecting the selection.
The basic laws may be useful for several social services such as the
prediction of friendships and social relations1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ;
9 , seeking marital partners, and so on.

In this paper, we propose a minimum model for two-way selections to
investigate the factors influencing on the matching rate. Based on our model,
we also find an efficient way to estimate the total number of characters
affecting the two-way selections from empirical data.

##  II The Model and Results

Generally speaking, two-way selections have at least two parts of members, and
the condition of successful matching is usually that the two sides of pairing
satisfy the characters for each other. The minimum model of random two-way
selections can be described as follows: i). The systems has two types of
agents, $A$ and $B$, respectively with the total number $k_{1}$ and $k_{2}$.
ii). Each agent (the $i$-th agent, say), either in type A or type B, has a own
character signed by $C_{Ai}$ ($i\in A$) or $C_{Bi}$ ($i\in B$). At the same
time, the character which each agent want to select is signed by $S_{Ai}$ or
$S_{Bi}$. Therefore, describing the state of each agent $Ai$ or $Bi$ requires
two characters which are independently chosen from $n$ kinds of characters
following the uniform distribution. iii). The condition of successful match of
two agents ($i\in A$ and $j\in B$) is $C_{Ai}=S_{Bj}$ and $S_{Ai}=C_{Bj}$.

For given $k_{1}$, $k_{2}$, and $n$, the total number of matching pairs $E$
can be written out according to the rules above:

$\displaystyle
E\left(k_{1},k_{2},n\right)=k_{1}\sum\limits_{i=0}^{k_{1}}\left[\sum\limits_{j=i+1}^{k_{2}}C_{k_{1}-1}^{i}C_{k_{2}}^{j}\left(\frac{1}{n^{2}}\right)^{i+j}\left(\frac{n^{2}-1}{n^{2}}\right)^{k_{1}+k_{2}-i-j-1}\right]+k_{2}\sum\limits_{j=0}^{k_{2}}\left[\sum\limits_{i=j}^{k_{1}}C_{k_{1}}^{i+1}C_{k_{2}-1}^{j-1}\left(\frac{1}{n^{2}}\right)^{i+j}\left(\frac{n^{2}-1}{n^{2}}\right)^{k_{1}+k_{2}-i-j-1}\right].$
(1)

According to :

$\lim_{k\rightarrow\infty}C_{k}^{i}x^{i}(1-x)^{k-i}=\frac{e^{-\lambda}\lambda^{i}}{i!},\quad\sum\limits_{i=0}^{\infty}\frac{x^{i}}{(i!)^{2}}=\text{BesselI}(0,2\sqrt{x}),\quad\sum\limits_{i=0}^{\infty}\frac{x^{i}}{(i!)(i-1)!}=\sqrt{x}\text{BesselI}(1,2\sqrt{x}),$
(2)

where $\lambda=xk$, $\text{BesselI}(0,2\sqrt{x})$ and
$\text{BesselI}(1,2\sqrt{x})$ are Bessel functions of the amount of virtual
cases. From Eq.(1) we obtain

$\displaystyle E\approx
k_{1}\left[1-e^{-\lambda_{1}-\lambda_{2}}\left(\text{BesselI}\left(0,2\sqrt{\lambda_{1}\lambda_{2}}\right)+\sqrt{\frac{\lambda_{1}}{\lambda_{2}}}\text{BesselI}\left(1,2\sqrt{\lambda_{1}\lambda_{2}}\right)\right)\right],$
(3)

where $\lambda_{1}=k_{1}/n^{2}$, $\lambda_{2}=k_{2}/n^{2}$.

Due to the symmetry of k1 and k2 in Eq.(1) , it is enough to study the range
$k_{1}\leqslant k_{2}$. We discuss Eq.(1) under three conditions of different
relative magnitude of $k_{1}$,$k_{2}$ and $n^{2}$. When $k_{1}\leqslant
k_{2}\ll n^{2}$, resulting in $\lambda_{1}\rightarrow 0,\lambda_{2}\rightarrow
0$, we only need to calculate the zeroth power term and the first power term
of Eq.(3). We obtain

$E\approx\frac{1}{n^{2}}k_{1}k_{2}.$ (4)

When $k_{1}\leqslant n^{2}\ll k_{2}$ or $n^{2}\ll k_{1}\leqslant k_{2}$,
according to

$\lim_{x\rightarrow\infty}\text{BesselI}(0,2x)=\lim_{x\rightarrow\infty}\text{BesselI}(1,2x)=\frac{e^{2x}}{2\sqrt{\pi
x}},$ (5)

from Eq.(3) we obtain

$\displaystyle E\approx
k_{1}-k_{1}\left[\frac{e^{-(\sqrt{\lambda_{1}}-\sqrt{\lambda_{2}})^{2}}}{\sqrt{\pi\sqrt{\lambda_{1}\lambda_{2}}}}\right].$
(6)

Because Eq.(6) is obtained under the condition of $k_{1}\leqslant n^{2}\ll
k_{2}$ or $n^{2}\ll k_{1}\leqslant k_{2}$, $k_{2}$ is very large, from Eq.(6)
we can obtain

$E\approx k_{1}.$ (7)

We defined that

$\displaystyle\eta=\frac{k_{2}}{k_{1}},\quad\xi=\frac{n^{2}}{k_{1}},\quad
P=\frac{2E}{k_{1}+k_{2}}.$ (8)

Therefore, $\eta$ represents the ratio between $k_{2}$ and $k_{1}$; $\xi$
represents the ratio between $n^{2}$ and $k_{1}$; $P$ represents the
probability of the agents which successfully match. The Eq.(3) is transformed
into

$\displaystyle
P=\frac{2}{1+\eta}\left[1-e^{-\frac{1}{\xi}-\frac{\eta}{\xi}}\left(\text{BesselI}\left(0,\frac{2\sqrt{\eta}}{\xi}\right)+\frac{1}{\sqrt{\eta}}\text{BesselI}\left(1,\frac{2\sqrt{\eta}}{\xi}\right)\right)\right].$
(9)

The Eq.(4) can written as:

$\displaystyle
P\approx\frac{2\eta}{\xi(\eta+1)}\quad\quad\quad(1\leqslant\eta\ll\xi).$ (10)

The Eq.(7) can written as:

$\displaystyle
P\approx\frac{2}{\eta+1}\quad\quad\quad\quad\,(1\leqslant\xi\ll\eta\quad
or\quad\xi\ll 1\leqslant\eta).$ (11)

Figure 1: (Color online) The comparison between analytical predictions and the
simulation results. In the two sub-figures, the parameter $k_{1}=100$; $\eta$
is assigned values from $1$ to $1000$; $\xi$ is assigned values from $0.1$ to
$1000$. (a) shows analytical predictions of Eq.(1); (b) shows the simulation
results.
Figure 2: (Color online) The comparison between analytical predictions and the
simulation results in the log-log plots. In the four sub-figures, the
parameter $k_{1}=100$; the squares indicate the simulation data; the solid
lines indicate analytical predictions. (a), $\eta=2$; $\xi$ is assigned values
from $100$ to $1000$; the solid line is obtained from Eq.(10). (b), $\xi=2$;
$\eta$ is assigned values from $10$ to $1000$; the solid line is obtained from
Eq.(11). (c), $\eta=1$; $\xi$ is assigned values from $10$ to $100$; the solid
line is obtained from Eq.(12). (d), $\xi=0.1$; $\eta$ is assigned values from
$10$ to $1000$; the solid line is obtained from Eq.(11).

Fig 1.(a) and Fig 1.(b) show the comparison between analytical predictions of
Eq.(1) and the simulation results. Fig 2.(a) shows the comparison between
analytical predictions of Eq.(10) and the simulation results under condition
$1\leqslant\eta\ll\xi$ and displays a power-law distribution with the exponent
$-1$ between $P$ and $\xi$. Fig 2.(b) shows the comparison between analytical
predictions of Eq.(11) and the simulation results under condition
$1\leqslant\xi\ll\eta$ and displays a power-law distribution with the exponent
$-1$ between $P$ and $\eta$; Fig 2.(d) shows the comparison between analytical
predictions of Eq.(11) and the simulation results under condition $\xi\ll
1\leqslant\eta$ and displays the same power-law distribution to Fig 2.b. The
above analytical predictions and simulation results are consistent with each
other. It is that to say all analytical results are reliable.

Consider a special case $k_{1}=k_{2}=k$, resulting in $\eta=1$. On the one
hand, from Eq.(10) we obtain

$P\approx\frac{1}{\xi}.$ (12)

The relation between $P$ and $\xi$ approximate to power law with the exponent
$-1$,and this case is well shown in Fig 2.(c); from Eq.(11) we obtain
$P\approx 1$, it means that almost all of agents can match successfully under
condition $\xi\ll 1\leqslant\eta$. On the other hand, according to
$k_{1}=k_{2}=k$, resulting in $\lambda_{1}=\lambda_{2}$, from Eq.(6) we obtain

$E\approx k-\sqrt{\frac{n^{2}}{\pi}}\sqrt{k}.$ (13)

The second term of Eq.(13) is the number of the agents which can not
successfully match in type A or type B. The larger $k$ is, The smaller
$\sqrt{n^{2}/\pi}\sqrt{k}/k$ is. In reality, It’s a result of fluctuation.
There are $n^{2}$ kinds of the states that a agent maybe have in the model. In
theory, the expected times of each state appearing is $k/n^{2}$. However, due
to the fluctuations, almost all frequencies of every states appearing deviate
around $k/n^{2}$. As a result, some agents can not successfully match. The
number of times that each state may appear obeys the binomial distribution.
The fluctuation is close related to the standard deviation, according to the
binomial theorem and standard deviation formula, we can obtain that the
standard deviation equals to $\sqrt{k(1-1/n^{2})/n^{2}}$, which is directly
proportional to $\sqrt{k}$. Thus, the number of the agents which can not
successfully match is also proportional to $\sqrt{k}$. It explains the
relationship between the second item of Eq.(13) and $\sqrt{k}$. From Eq.(13),
we know that the proportionality coefficient is $\sqrt{n^{2}/\pi}$.

Figure 3: (Color online) The relationship between the experimental evidence
and analytical predictions in the log-log plots. The red curve and the olive
curve are obtained from Eq.(9), and The parameters of red curve are $\eta=1$,
$n=15$; The parameters of olive curve are $\eta=356.67$, $n=15$. The round
dots represent the empirical data in APPENDIX A. The $\xi_{max}$ represent the
maximum value $225$ of $\xi$.

Finally, we validate our model in the experimental evidence way. The marriage
selections between men and women is a typical real-world two-way selections
system. Here we collect eighty-two news of real-world matchmaking fairs from
the Internet (see APPENDIX A). But the information of our data are incomplete.
Only the numbers of participants and matching pairs are recorded. The numbers
of men and women joined are omitted. So parameter $\eta$ can not be determined
exactly, but can only be restricted at a range. And $n$ is a internal
parameter need to be measured. We deal with the data and measure $n$ below.

We first consider the parameter $\eta$. Because $k_{1}\leqslant k_{2}$, the
minimum value of $\eta$ is $\eta_{min}=1$. For each set of data, there is a
maximal value. Take the first set of data in TABLE I for example, there are
$13$ participants and $3$ couples matched, thus $k_{1,1}\geqslant 3$,
according to Eq.(8), $\eta\leqslant\eta_{max,1}=(13-3)/3$. And we define two
signs: $\eta_{max,min}=\min_{i=1}^{82}\eta_{max,i}=2$,
$\eta_{max,max}=\max_{i=1}^{82}\eta_{max,i}=365.67$ by calculating eighty-two
sets of data in TABLE I. We estimate $n$ by minimizing

$\sum_{i=1}^{82}(P_{data,i}-P_{analysis,i})^{2}$ (14)

in which $P_{data}$ comes from the experimental data and $P_{analysis}$
calculated from Eq.9. Firstly, we take $\eta=\eta_{min}=1$, and n ranges from
$1$ to $10^{4}$ with a step size of 1, by calculating Eq.(14), we find that
when $n=17$, Eq.(14) is minimal. Then we take $\eta=\eta_{max,min}=2$, the
same to way, we minimize Eq.(14) and find $n=13$. In the Eq.(8), $n^{2}$ and
$\eta$ are inversely proportional relationship ,therefore, we define
$n_{max}=17$ and $n_{min}=13$, and $n$ belongs to $[13,17]$. Finally we
estimate $n$ by $n=(n_{max}+n_{min})/2=15$ and fix it.

Fig 3 shows the relationship between the experimental evidence and analytical
predictions of our model. The red curve and olive curve are obtained from
Eq.(9). The parameters of red curve are $\eta=1$, $n=15$; the parameters of
olive curve are $\eta=356.667$, $n=15$. From the Eq.(8), when $k_{1}$ is equal
to the minimum $1$, the $\xi$ take the maximum value $225$. The error bar of
ordinate $P$ of round dots represents the range of empirical data $P$ in TABLE
I. Because $k_{1}$ is unknown and $\xi$ is undetermined, we can only obtain
$k_{1,min,i}=E_{i}\leqslant k_{1,i}\leqslant k_{1,max,i}=(k_{1}+k_{2})/2$ and
$15^{2}/k_{1,max,i}\leqslant\xi_{i}\leqslant 15^{2}/k_{1,min,i}$. Therefore,
the rang of abscissa $\xi$ of round dots is relatively wide and the middle
points take $\xi_{i}=(15^{2}/k_{1,max,i}+15^{2}/k_{1,min,i})/2$.

We can see from Fig.3 that when $\xi$ is relatively small, corresponding
$k_{1}$ relatively big, all empirical data are enclosed in between the the two
curves; when $\xi$ is relatively big, corresponding $k_{1}$ relatively small,
some empirical data are enclosed in between the two curves, however others
empirical data lie the red curve above and the trend of the empirical data is
opposite to the analytical predictions. We have two reasons to explain them:
one the one hand, organizers of some matchmaking fairs select less guests who
meet their requirements to participate the matchmaking fairs from a lot of
people who enter name and want to participate the matchmaking fairs. In this
case, each guest is easier to find the right opposite sex who can match for
each other; one the other hand, when the number of guests is small in a
matchmaking fair, they know that it is very difficult to find the right
opposite sex who can match for each other, so they are not to find the right
opposite sex but tend to choose a basically mutually acceptable opposite sex.
In this psychological effect, each guest is also easier to find the opposite
sex to pair. The two reasons above cause that the fewer the guests are, the
higher the probability $p$ is. From the above analysis, the experimental data
can be well explained by the model.

##  III Conclusions

In summary, we provide the exact solution for random two-way selections
system. The dynamics mechanism of a model is established and the analytical
result is obtained. In several different conditions, we obtain the
approximative and compact analytical results which agree with the simulation
results. In the model, the parameter $n$ is the total number of the characters
from which each agent can chose and directly determine the probability of
successful match. Therefore, $n$ is a very important parameter for random two-
way selections system. We propose a method to estimate the value of $n$ by
fitting empirical data. In this paper, the typical experimental data is
collected by the Internet and the range of parameter $n$ is estimated by the
method we proposed. We find that the average of $n$ is $15$, which is in
agreement with daily experiences, and that most of the experimental evidence
data fall into the range predicted by our model. So the method would be useful
to estimate the parameter $n$, and such simple model indeed catch the core of
random two-way selections system in reality and would be valuable to the real
life and several online social services.

###### Acknowledgements.

This work was funded by the National Important Research Project (Grant No.
91024026), the National Natural Science Foundation of China (No. 11205040,
11105024, 11275186), the Major Important Project Fund for Anhui University
Nature Science Research (Grant No. KJ2011ZD07) and the Specialized Research
Fund for the Doctoral Program of Higher Education of China (Grant No.
20093402110032).

##  Appendix A Empirical Data of Matchmaking Fairs

We collect 82 online news of real-world matchmaking fairs and record the
number of guests and matching pairs. Due to some of news did not report exact
numbers, we suppose each of these uncertain numbers has 10% possible ranges.
The reports of these uncertain numbers generally have three types: nearly $x$,
about $x$, and over $x$ (here $x$ is the number). For “’nearly $x$”, we set
the possible range is $0.95x\pm 0.05x$, and $1.00x\pm 0.05x$ for “about $x$”,
and $1.05x\pm 0.05x$ for “over $x$”. All of these information is shown in
Table 1.

## References

  * (1) L. Lü, T. Zhou, Link prediction in complex networks: A survey. Physica A 390, (2011) 1150.
  * (2) R. Guimer, M. Sales-Pardo, Missing and spurious interactions and the reconstruction of complex networks, Proc. Nat. Acad. Sci. USA,106 (2009) 22073.
  * (3) L. Lü, M. Medo, C.-H. Yeung, Y.-C. Zhang, Z.-K. Zhang, T. Zhou, Recommender systems, Phys. Rep., 519 (2012) 1.
  * (4) C.-J. Zhang, A. Zeng, Behavior patterns of online users and the effect on information filtering, Physica A, 391 (2012) 1822.
  * (5) J.-L. Guillaume, M. Latapy, Bipartite structure of all complex networks, Inform. Proc. Lett., 90 (2004) 215.
  * (6) M.-S. Shang, L. Lü, Y.-C. Zhang, T. Zhou, Empirical analysis of web-based user-object bipartite networks, EuoPhys. Lett., 90 (2010) 48006.
  * (7) R. Guimer, M. Sales-Pardo, L. Amaral, A Nunes, Module identification in bipartite and directed networks, Phys. Rev. E., 76 (2007) 036102.
  * (8) Y.-B. Zhou, L. Lü, M. Li, Quantifying the influence of scientists and their publications: distinguishing between prestige and popularity, New J. Phys., 14 (2012) 033033.
  * (9) L. Li, Z. Yang, L. Liu, M. Kitsuregawa, Query-url bipartite based approach to personalized query recommendation, Proceedings of the 23rd national conference on Artificial intelligence. (2008) 1189.

Table 1: The data of matchmaking fairs

Website of the reports of matchmaking fairs Original descriptions The total of
joined people: $k_{1}+k_{2}$ The total number of matched pairs $E$ Matching
ratio $P$ http://www.cdb.org.cn/newsview.php?id=6359 13 joined; 3 matched $13$
$3$ $0.4615$ http://sd.people.com.cn/n/2012/0827/c183718-17407663.html 18
joined; 6 matched $18$ $6$ $0.6667$
http://news.carnoc.com/list/183/183765.html 20 joined; 1 matched $20$ $1$
$0.1000$ http://bbs.tiexue.net/post2_5756757_1.html 21 joined; 6 matched $21$
$6$ $0.5714$ http://www.shxb.net/html/20110516/20110516_278862.shtml 25
joined; 5 matched $25$ $5$ $0.4000$ http://news.qq.com/a/20100511/000472.htm
26 joined; 3 matched $26$ $3$ $0.2308$
http://bbs.ganxianw.com/thread-46316-1-1.html 26 joined; 4 matched $26$ $4$
$0.3077$ http://www.wzrb.com.cn/article321273show.html 30 joined; 2 matched
$30$ $2$ $0.1333$
http://www.wccdaily.com.cn/epaper/hxdsb/html/2012-05/14/content_448239.htm 32
joined; 4 matched $32$ $4$ $0.2500$
http://wbnews.sxrb.com/news/ty/1372966.html 36 joined; 6 matched $36$ $6$
$0.3333$
http://www.nbmz.gov.cn/view.aspx?id=16595&AspxAutoDetectCookieSupport=1 36
joined; 6 matched $36$ $6$ $0.3333$
http://nb.people.com.cn/GB/200892/16491824.html 38 joined; 6 matched $38$ $6$
$0.3158$ http://cq.cqwb.com.cn/NewsFiles/201203/25/921397.shtml 40 joined; 8
matched $40$ $8$ $0.4000$
http://www.sc.chinanews.com.cn/my/data/html/201212/32619.html over 40 joined;
3 matched $42\pm 2$ $3$ $0.1432\pm 0.0068$
http://www.16466.com/info_detail.htm?id=36526 over 50 joined; 3 matched $53\pm
3$ $3$ $0.1136\pm 0.0064$
http://www.ncnews.com.cn/ncxw/shxw/t20121112_943114.htm about 60 joined; 5
matched $60\pm 3$ $5$ $0.1671\pm 0.0084$
http://news.wzsee.com/2012/0502/130061.html over 60 joined; 4 matched $63\pm
3$ $4$ $0.1273\pm 0.0061$ http://news.hexun.com/2012-08-27/145162214.html over
60 joined; 5 matched $63\pm 3$ $5$ $0.1591\pm 0.0076$
http://www.douban.com/group/topic/28145139/ over 60 joined; about 10 matched
$63\pm 3$ $10\pm 1$ $0.3197\pm 0.0470$
http://zhuanti.10yan.com/zt/other/sdcms/html/xqj2012/xiangqindongtai/1377.html
72 joined; 11 matched $72$ $11$ $0.3056$
http://www.wlmqwb.com/3229/syzt/hdzt/seven/201007/t20100719_1287834.shtml 80
joined; 5 matched $80$ $5$ $0.1250$
http://www.dpcm.cn/html/news/shehui/20121211/8a485b96f289e038.htm 80 joined;
10 matched $80$ $10$ $0.2500$ http://www.zhaogejia.com/News/Show/166 80
joined; 13 matched $80$ $13$ $0.3250$
http://cq.cqnews.net/shxw/shwx/200909/t20090928_3635782.htm 80 joined; 18
matched $80$ $18$ $0.4500$
http://a.jiaodong.net/jiaoyou/detail/?/20120717134715.htm nearly 100 joined; 5
matched $95\pm 5$ $5$ $0.1056\pm 0.0056$
http://www.dllake.com/testurl/news/news.asp?id=1874 99 joined; 8 matched $99$
$8$ $0.1616$
http://fj.qq.com/a/20120413/000073.htm?pgv_ref=aio2012&ptlang=2052 100 joined;
5 matched $100$ $5$ $0.1000$
http://epaper.lnd.com.cn/html/bdcb/20110118/bdcb635730.html about 100 joined;
7 matched $100\pm 5$ $7$ $0.1404\pm 0.0070$
http://news.zh853.com/NewsShow-22166.html over 100 joined; 16 matched $110\pm
10$ $16$ $0.2933\pm 0.0267$
http://news.163.com/11/1123/08/7JHJ4PP100014AED.html 150 joined; 7 matched
$150$ $7$ $0.0933$ http://news.xinmin.cn/rollnews/2011/05/03/10539635.html
nearly 200 joined; 8 matched $190\pm 10$ $8$ $0.0844\pm 0.0044$
http://www.0523qq.com/forum.php?mod=viewthread&tid=2779 nearly 200 joined; 22
matched $190\pm 10$ $22$ $0.2322\pm 0.0122$
http://news.ycw.gov.cn/html/2012-04/28/content_15150376.htm about 200 joined;
4 matched $200\pm 10$ $4$ $0.0401\pm 0.0020$
http://epaper.lnd.com.cn/html/bdcb/20110118/bdcb635730.html 206 joined; 10
matched $206$ $10$ $0.0971$
http://www.cqwb.com.cn/NewsFiles/201005/30/20102930062910354716.shtml over 200
joined; 7 matched $210\pm 10$ $7$ $0.0668\pm 0.0032$
http://bddsb.bandao.cn/data/20120827/html/53/content_2.html over 200 joined; 8
matched $210\pm 10$ $8$ $0.0764\pm 0.0036$
http://www.zhaogejia.com/News/Show/150 over 200 joined; 38 matched $210\pm 10$
$38$ $0.3627\pm 0.0173$ http://3g.3xgd.com/news/play.asp?NewsID=80975 216
joined; 19 matched $216$ $19$ $0.1759$
http://wed.cnhan.com/hjb/2012-12-03/3900.html over 240 joined; 22 matched
$252\pm 12$ $22$ $0.1750\pm 0.0083$
http://xt.fangyuan365.com/article/List.asp?ID=8708 about 258 joined; over 10
matched $258\pm 13$ $11\pm 1$ $0.0859\pm 0.0121$
http://cq.cqnews.net/shxw/2012-11/12/content_21432170.htm nearly 300 joined; 4
matched $285\pm 15$ $4$ $0.0282\pm 0.0014$
http://xt.fangyuan365.com/article/List.asp?ID=11694 about 300 joined; 8
matched $300\pm 15$ $8$ $0.0535\pm 0.0027$
http://roll.sohu.com/20120625/n346389451.shtml over 300 joined; over 10
matched $315\pm 15$ $11\pm 1$ $0.0703\pm 0.0097$
http://www.ijxjj.com/article/article_12773.html over 300 joined; 32 matched
$315\pm 15$ $32$ $0.2036\pm 0.0097$
http://news.xinmin.cn/shehui/2013/02/16/18638248_2.html 400 joined ; nearly 20
matched $400$ $19\pm 1$ $0.0950\pm 0.0050$
http://www.sz120.com/xwdt/ynxw/22205/ over 500 joined; 3 matched $525\pm 25$
$3$ $0.0115\pm 0.0005$
http://www.sc.xinhuanet.com/content/2012-02/06/content_24649397.htm over 500
joined; 8 matched $525\pm 25$ $8$ $0.0306\pm 0.0015$
http://dqnews.zjol.com.cn/dqnews/system/2010/08/17/012525402.shtml over 500
joined; over 10 matched $525\pm 25$ $11\pm 1$ $0.0422\pm 0.0058$
http://cheshang.16888.com/newsinfo/2011/1115/141264.html nearly 600 joined;
nearly 40 matched $570\pm 30$ $38\pm 2$ $0.1341\pm 0.0141$
http://bbs.heze.cc/thread-842865-1-1.html over 600 joined; over 78 matched
$630\pm 30$ $78$ $0.2482\pm 0.0118$ http://www.8hy.org/hyjy/hy6240/1 nearly
800 joined; 58 matched $760\pm 40$ $58$ $0.1531\pm 0.0081$
http://www.cdrb.com.cn/html/2012-04/03/content_1546492.htm over 800 joined;
over 20 matched $840\pm 40$ $21\pm 1$ $0.0502\pm 0.0047$
http://heilongjiang.dbw.cn/system/2013/02/16/054584150.shtml nearly 1000
joined; about 20 matched $950\pm 50$ $20\pm 1$ $0.0423\pm 0.0043$
http://www.e0734.com/2012/0502/90707.html nearly 1000 joined; 58 matched
$950\pm 50$ $58$ $0.1224\pm 0.0064$
http://sz.tznews.cn/tzwb/html/2012-07/09/content_71285.htm nearly 1000 joined;
64 matched $950\pm 50$ $64$ $0.1351\pm 0.0071$
http://www.xtrb.cn/epaper/ncwb/html/2011-08/09/content_275667.htm about 1000
joined; 12 matched $1000\pm 50$ $12$ $0.0241\pm 0.0012$
http://www.hukou365.com/cwbbs/forum/showtopic_tree.jsp?rootid=194730 about
1000 joined; 15 matched $1000\pm 50$ $15$ $0.0301\pm 0.0015$
http://news.163.com/10/0329/03/62TPSMMO000146BB.html about 1000 joined; nearly
100 matched $1000\pm 50$ $95\pm 5$ $0.1910\pm 0.0196$
http://www.chinajilin.com.cn/content/2009-02/15/content_1495554.htm over 1000
joined; 3 matched $1050\pm 50$ $3$ $0.0057\pm 0.0003$
http://sy.house.sina.com.cn/news/2011-12-27/114483993.shtml over 1000 joined;
4 matched $1050\pm 50$ $4$ $0.0076\pm 0.0004$
http://news.dayoo.com/guangzhou/201205/02/73437_23554932.htm over 1500 joined;
48 matched $1575\pm 75$ $48$ $0.0611\pm 0.0029$
http://cq.qq.com/a/20090824/000190.htm over 1500 joined; over 100 matched
$1575\pm 75$ $105\pm 5$ $0.1339\pm 0.0127$
http://news.qq.com/a/20111228/000342.htm over 1600 joined; 31 matched $1680\pm
80$ $31$ $0.0370\pm 0.0018$
http://www.efu.com.cn/data/2011/2011-08-09/389729.shtml over 2000 joined;
nearly 100 matched $2100\pm 100$ $95\pm 5$ $0.0909\pm 0.0091$
http://ent.163.com/12/1203/13/8HQ885MN00032DGD.html over 2000 joined; over 113
matched $2100\pm 100$ $119\pm 6$ $0.1139\pm 0.0111$
http://www.subaonet.com/html/society/2010426/3C95FFIB98JI5FC.html nearly 3000
joined; nearly 100 matched $2850\pm 150$ $95\pm 5$ $0.0670\pm 0.0070$
http://wb.sznews.com/html/2011-11/07/content_1812730.htm about 3000 joined;
186 $3000\pm 150$ $186$ $0.1243\pm 0.0062$
http://heilongjiang.dbw.cn/system/2012/04/23/053819817.shtml over 3000 joined;
over 200 matched $3150\pm 150$ $210\pm 10$ $0.1339\pm 0.0127$
http://news.cnnb.com.cn/system/2011/10/31/007128083.shtml over 4000 joined;
over 500 matched $4200\pm 200$ $525\pm 25$ $0.2511\pm 0.0239$
http://www.people.com.cn/GB/paper447/17168/1505082.html nearly 5000 joined;
108 matched $4750\pm 250$ $108$ $0.0456\pm 0.0024$
http://news.timedg.com/2012-04/16/content_9577975.htm over 5000 joined; 218
matched $5250\pm 250$ $218$ $0.0832\pm 0.0040$
http://www.gddgart.com/artcenter/html3asp/town3ship/dq2012714_2357.asp over
5000 joined; 231 matched $5250\pm 250$ $231$ $0.0882\pm 0.0042$
http://epaper.oeeee.com/I/html/2012-11/12/content_1751538.htm over 5000
joined; 237 matched $5250\pm 250$ $237$ $0.0905\pm 0.0043$
http://news.hsw.cn/system/2010/06/28/050547974.shtml over 6000 joined; over
270 matched $6300\pm 300$ $284\pm 14$ $0.0906\pm 0.0088$
http://fj.sina.com.cn/news/s/2012-08-24/07186785.html nearly 10000 joined; 28
matched $9500\pm 500$ $28$ $0.0059\pm 0.0003$
http://net.chinabyte.com/164/12210164.shtml nearly 10000 joined; about 100
matched $9500\pm 500$ $100\pm 5$ $0.0212\pm 0.0022$
http://epaper.hljnews.cn/shb/html/2008-05/26/content_199685.htm nearly 10000
joined; nearly 2000 matched $9500\pm 500$ $1900\pm 100$ $0.4022\pm 0.0422$
http://www.estour.gov.cn/news/lvyouxinwen/2011/815/1181583840H7H40DE3ADE501J93BG9.shtml
over 10000 joined; about 400 matched $10500\pm 500$ $400\pm 20$ $0.0766\pm
0.0075$ http://www.048100.com.cn/news/bdxw/2009-04-20/617.html over 10000
joined; over 1000 matched $10500\pm 500$ $1050\pm 50$ $0.2009\pm 0.0191$
http://www.estour.gov.cn/news/lvyouxinwen/2011/815/1181583840H7H40DE3ADE501J93BG9.shtml
about 16000 joined; over 700 matched $16000\pm 800$ $735\pm 35$ $0.0923\pm
0.0090$
http://www.estour.gov.cn/news/lvyouxinwen/2011/815/1181583840H7H40DE3ADE501J93BG9.shtml
over 16000 joined; over 600 matched $16800\pm 800$ $630\pm 30$ $0.0753\pm
0.0072$ http://zjnews.zjol.com.cn/05zjnews/system/2009/03/30/015385573.shtml
over 50000 joined; over 3000 matched $52500\pm 2500$ $3150\pm 150$ $0.1206\pm
0.0115$