Xu X B, et al. Sci China Inf Sci November 2013 Vol. 56 110905:4
where σ
2
B
= Y (1 − Y ) is the variance of the binomial random variable η(u). Chebysev’s inequality can be
used to estimate the accuracy of
ˆ
Y
MC
, that is, the probability that |
ˆ
Y
MC
− Y | <ε
MC
is bounded by [2]
P {|
ˆ
Y
MC
− Y | <ε
MC
} 1 −
σ
2
B
Nε
2
MC
. (8)
Since σ
2
B
is not known exactly, it can be estimated with the standard unbiased variance estimation
formula
σ
2
B
=
ˆ
Y
MC
(1 −
ˆ
Y
MC
). (9)
Let α>0 be a confidence level at which
ˆ
Y
MC
is restricted within ε
MC
of true value Y and let
P {|
ˆ
Y
MC
− Y | <ε
MC
} 1 −
σ
2
B
Nε
2
MC
= α. (10)
Then corresponding sample size N is determined by
N =
σ
2
B
(1 − α)ε
2
MC
. (11)
Obviously, when the variance σ
2
B
is quite large or the small estimation error ε
MC
is required, a large
number of simulations are required to have a valuable estimation. Many variance reduction techniques
such as importance sampling, control variates, and stratified sampling have been developed to overcome
the drawback of PMC. However, according to (8), if α tends to 100% which means a complete guarantee,
then N must be infinity. So, it is impossible that PMC or any other advanced methods offer estimation
errors with a 100% confidence level. Moreover, any result of once estimation is not very accurate or
certain, while the mean of many times estimation may be more accurate. Therefore, the necessary
computational burden cannot be mitigated. In following section, based on TBM, a novel method is
presented to estimate parametric yield according to the definition in (3), which can offer an approximate
value of yield with a deterministic estimation error i.e., confidence level =100%.
3 Evidence-based parameter representation and CDF approximation
The TBM is a model for representing quantified beliefs held by an individual in the truth of a proposition
related to a given problem [11], such as the evidence-based representation for the values of circuit com-
ponent parameters. The TBM identifies two states of belief, namely, the creedal state and pignistic state
(credo is the Latin word meaning “to believe” whereas pignus is the Latin word for “bet” [12]). Beliefs
included in the creedal state are quantified by belief functions, i.e., the bodies of evidence and remain
until they are needed to support decisions. When needed for decision-making, these beliefs are trans-
ferred from the credal state to a betting frame defined by a pignistic state where a pignistic probability
distribution is induced on the elements of the frame. This process is called pignistic transforms [11]. In
the case of frames built on the set of real numbers, the beliefs held in the credal state are represented by
a basic belief density (BBD); a credal variable can then be defined as a real-valued variable characterized
by the BBD [13].
This section suggests an approach for obtaining pignistic cumulative distribution of performance func-
tion output to approximate its true cumulative distribution function (CDF) for yield estimation. Firstly,
treating input parameters of performance function as credal variables, the suggested approach constructs
a random set for these parameters defined on a continuous frame of real numbers, which represents an
interval evidence structure on the tolerance range of each parameter. Secondly, the corresponding ran-
dom set of the function output is obtained by extension principle of random set. Thirdly, the random
set of function output in the credal state can be transformed to a pignistic state where it is represented
by the pignistic cumulative distribution. It can be used to approximately estimate yield according to
circuit response specifications. An outline of this process is shown in Figure 1. Additional details on the
theoretical aspects of Dempster-Shafer theory, TBM, and the extension of both to spaces of real numbers,
can be found in [11,13,14] respectively.