System and method for estimating probabilities of events

Abstract

A dual adaptive importance-sampling system and method is provided that can estimate the probability of events by combining dual complementary importance-sampling simulations. The present invention exploits the ability to determine an optimal biased pdf using an iterative procedure that requires relatively little a priori knowledge of how to bias. Hence, the present invention is particularly suited for evaluating the BERs and/or WERs of coded communication and storage systems, and is generally applicable to arbitrarily chosen codes. When applied to coded communication and storage systems, the present invention provides a versatile technique for the fast and accurate estimation of BERs and WERs of FEC codes down to values of 10 −20 or lower.

1 . A method of estimating the probability of occurrence of an event (E), comprising: 
 performing an adaptive unconstrained estimation of an optimal biased distribution of a multi-dimensional random variable (z) defined on a sample space (Γ);    performing an importance-sampling (IS) simulation using the optimal biased distribution for z to yield a first result;    performing an adaptive constrained estimation of an optimal biased distribution for z over regions of Γ where E occurs;    performing an IS simulation using the optimal biased distribution for z, over regions of Γ where E occurs, to yield a second result; and    estimating the probability of the occurrence of E based on the first and second results.    
   
   
       2 . The method of  claim 1 , wherein the constrained and unconstrained estimations are performed iteratively.  
   
   
       3 . The method of  claim 1 , wherein the event comprises a word error rate for a forward error correcting (FEC) code.  
   
   
       4 . The method of  claim 3 , wherein the FEC code comprises a LDPC code.  
   
   
       5 . The method of  claim 1 , wherein the event comprises a bit error rate for a forward error correcting (FEC) code.  
   
   
       6 . The method of  claim 5 , wherein the FEC code comprises a LDPC code.  
   
   
       7 . The method of  claim 1 , wherein the steps of performing an adaptive unconstrained estimation of an optimal biased distribution for z and performing an IS simulation using the optimal biased distribution for z to yield a first result comprise: 
 performing adaptive unconstrained Metropolis simulations to iteratively estimate the optimal biased distribution for z; and    performing an IS simulation using the optimal biased distribution for z and an unconstrained Metropolis random walk to yield the first result.    
   
   
       8 . The method of  claim 7 , wherein the steps of performing an adaptive constrained estimation of an optimal biased distribution for z over regions of Γ where E occurs and performing an IS simulation using the optimal biased distribution for z over regions of Γ where E occurs to yield a second result comprise: 
 performing adaptive constrained Metropolis simulations to iteratively estimate the optimal biased distribution for z over regions of Γ where E occurs; and    performing an IS simulation using the optimal biased distribution for z over regions of Γ where E occurs and a constrained Metropolis random walk to yield the second result.    
   
   
       9 . The method of  claim 1 , wherein the probability of the occurrence of E based on the first and second results is estimated by: 
 scaling the second result to fit the first result to yield a scaling factor; and    estimating the probability of the occurrence of E based on the scaling factor.    
   
   
       10 . A method of estimating the probability of occurrence of an event (E), given a known probability distribution (ρ(z)) of a multi-dimensional random variable (z) defined on a sample space (Γ), comprising: 
 determining a scalar mapping (V) from the multi-dimensional sample space to a single-dimensional space;    defining bins that partition a first range of values of V (Γ V   u ), such that values of V not in the range of values Γ V   u  have a negligible probability of occurrence;    performing adaptive unconstrained Metropolis simulations to iteratively estimate an optimal biased distribution for z;    performing an importance-sampling (IS) simulation using the optimal biased distribution for z and an unconstrained Metropolis random walk to yield a first result;    defining bins that partition a second range of values of V (Γ V   c ), such that values of V not in the range of values Γ V   c  have a negligible contribution to the probability of occurrence of E;    performing adaptive constrained Metropolis simulations to iteratively estimate an optimal biased distribution for z over regions of Γ where E occurs;    performing an IS simulation using the optimal biased distribution for z over regions of Γ where E occurs and a constrained Metropolis random walk to yield a second result; and    estimating the probability of occurrence of E based on the first and second results.    
   
   
       11 . The method of  claim 10 , wherein the first result comprises estimates of probability distributions p(V) and p(V, E), and the second result comprises an estimate of the probability distribution p(V|E).  
   
   
       12 . The method of  claim 11 , wherein the probability of occurrence of E (P(E)) is estimated by scaling the estimate of p(V|E) to fit the estimate of p(V, E) over a range of values of V where the estimates of p(V|E) and p(V, E) have a predetermined reliability, to yield a scaling factor (SF), wherein SF comprises a first estimate of P(E).  
   
   
       13 . The method of  claim 12 , further comprising integrating [p(V|E)*SF] over Γ V   c  to yield a second estimate of P(E), wherein the second estimate is more accurate than the first estimate.  
   
   
       14 . The method of  claim 10 , wherein the adaptive unconstrained Metropolis simulations and the adaptive constrained Metropolis simulations are performed by: 
 (a) setting an initial distribution for V over all bins Γ V   u  and Γ V   c  for adaptive unconstrained and adaptive constrained simulations, respectively;    (b) generating a random walk in the sample space of z using a Metropolis algorithm;    (c) generating a histogram (H k   j , k=1, . . . , M) of V=f(z) over all the bins of Γ V   u  or Γ V   c  based on the values of z generated by the Metropolis random-walk;    (d) obtaining a new estimate for the distribution of V as P k   j+1 =φ(P k   j ,P k−1   j ,P k−1   j−1 ,H k   l ,H k−1   l , l=0, 1, . . . , j), where φ denotes a predefined function;    (e) incrementing counter j and repeating steps (a)-(d) if the histogram of V is not approximately uniform; and    (f) setting P k   ∞ =P k   j+1 , ∀ kε{1, . . . , M} and ρ*(z)=ρ(z)/(cP k   ∞ ) as an optimal biased distribution of z for all z such that f(z) falls in the k th  bin of Γ V   u  or Γ V   c , and wherein c is chosen such that ∫ρ*(z)dz=1.    
   
   
       15 . A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for estimating the probability of occurrence of an event (E), the method steps comprising: 
 performing an adaptive unconstrained estimation of an optimal biased distribution for a multi-dimensional random variable (z) defined on a sample space (Γ);    performing an importance-sampling (IS) simulation using the optimal biased distribution for z to yield a first result;    performing an adaptive constrained estimation of an optimal biased distribution for z over regions of Γ where E occurs;    performing an IS simulation using the optimal biased distribution for z, over regions of Γ where E occurs, to yield a second result; and    estimating the probability of the occurrence of E based on the first and second results.    
   
   
       16 . The program storage device of  claim 15 , wherein the constrained and unconstrained estimations are performed iteratively.  
   
   
       17 . The program storage device of  claim 15 , wherein the event comprises a word error rate for a forward error correcting (FEC) code.  
   
   
       18 . The program storage device of  claim 17 , wherein the FEC code comprises a LDPC code.  
   
   
       19 . The program storage device of  claim 15 , wherein the event comprises a bit error rate for a forward error correcting (FEC) code.  
   
   
       20 . The program storage device of  claim 19 , wherein the FEC code comprises a LDPC code.  
   
   
       21 . The program storage device of  claim 15 , wherein the steps of performing an adaptive unconstrained estimation of an optimal biased distribution for z and performing an IS simulation using the optimal biased distribution for z to yield a first result comprise: 
 performing adaptive unconstrained Metropolis simulations to iteratively estimate the optimal biased distribution for z; and    performing an IS simulation using the optimal biased distribution for z and an unconstrained Metropolis random walk to yield the first result.    
   
   
       22 . The program storage device of  claim 21 , wherein the steps of performing an adaptive constrained estimation of an optimal biased distribution for z over regions of Γ where E occurs and performing an IS simulation using the optimal biased distribution for z over regions of Γ where E occurs to yield a second result comprise: 
 performing adaptive constrained Metropolis simulations to iteratively estimate the optimal biased distribution for z over regions of Γ where E occurs; and    performing an IS simulation using the optimal biased distribution for z over regions of Γ where E occurs and a constrained Metropolis random walk to yield the second result.    
   
   
       23 . The program storage device of  claim 15 , wherein the probability of the occurrence of E based on the first and second results is estimated by: 
 scaling the second result to fit the first result to yield a scaling factor; and    estimating the probability of the occurrence of E based on the scaling factor.    
   
   
       24 . A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for estimating the probability of occurrence of an event (E), given a known probability distribution (ρ(z)) of a multi-dimensional random variable (z) defined on a sample space (Γ), the method steps comprising: 
 determining a scalar mapping (V) from the multi-dimensional sample space to a single-dimensional space;    defining bins that partition a first range of values of V(Γ V   u ), such that values of V not in the range of values Γ V   u  have a negligible probability of occurrence;    performing adaptive unconstrained Metropolis simulations to iteratively estimate an optimal biased distribution for z;    performing an IS simulation using the optimal biased distribution for z and an unconstrained Metropolis random walk to yield a first result;    defining bins that partition a second range of values of V (Γ V   c ), such that values of V not in the range of values Γ V   c  have a negligible contribution to the probability of occurrence of E;    performing adaptive constrained Metropolis simulations to iteratively estimate an optimal biased distribution for z over regions of Γ where E occurs;    performing an IS simulation using the optimal biased distribution for z over regions of Γ where E occurs and a constrained Metropolis random walk to yield a second result; and    estimating the probability of occurrence of E based on the first and second results.    
   
   
       25 . The program storage device of  claim 24 , wherein the first result comprises estimates of probability distributions p(V) and p(V, E), and the second result comprises an estimate of the probability distribution p(V|E).  
   
   
       26 . The program storage device of  claim 25 , wherein the probability of occurrence of E, (P(E)) is estimated by scaling the estimate of p(V|E) to fit the estimate of p(V, E) over a range of values of V where the estimates of p(V|E) and p(V, E) have a predetermined reliability, to yield a scaling factor (SF), wherein SF comprises a first estimate of P(E).  
   
   
       27 . The program storage device of  claim 25 , further comprising integrating [p(V|E)*SF] over Γ V   c  to yield a second estimate of P(E), wherein the second estimate is more accurate than the first estimate.  
   
   
       28 . The program storage device of  claim 24 , wherein the adaptive unconstrained Metropolis simulations and the adaptive constrained Metropolis simulations are performed by: 
 (a) setting an initial distribution for V over all partition bins of Γ V   u  and Γ V   c  for adaptive unconstrained and adaptive constrained simulations, respectively;    (b) generating a random walk in the sample space Γ using a Metropolis algorithm;    (c) generating a histogram (H k   j , k=1, . . . , M) of V=f(z) over all partition bins of Γ V   u  or Γ V   c  based on the values of z generated by the Metropolis random-walk;    (d) obtaining a new estimate for the distribution of V as P k   j+1 =φ(P k   j ,P k−1   j ,P k−1   j−1 ,H k   l ,H k−1   l ;l=0, 1, . . . , j), where φ denotes a predefined function;    (e) incrementing counter j and repeating steps (a)-(d) if the histogram of V is not approximately uniform; and    (f) setting P k   ∞ =P k   j+1 , ∀ kε{1, . . . , M} and ρ*(z)=ρ(z)/(cP k   ∞ ) as an optimal biased distribution of z for all z such that f(z) falls in the k th  bin of Γ V   u  or Γ V   c , and wherein c is chosen such that ∫ρ*(z)dz=1.    
   
   
       29 . A system, comprising: 
 a processor programmed with computer readable program code for: 
 performing an adaptive unconstrained estimation of an optimal biased distribution for a multi-dimensional random variable (z) defined on a sample space (Γ),  
 performing an importance-sampling (IS) simulation using the optimal biased distribution for z to yield a first result,  
 performing an adaptive constrained estimation of an optimal biased distribution for z over regions of Γ where E occurs,  
 performing an IS simulation using the optimal biased distribution for z, over regions of Γ where E occurs, to yield a second result, and  
 estimating the probability of the occurrence of E based on the first and second results; and  
   a user interface in communication with the processor.    
   
   
       30 . A method of combining a first result from an unconstrained importance-sampling (IS) simulation with a second result from a constrained IS simulation, comprising: 
 receiving the first result;    receiving the second result; and    scaling the second result to fit the first result to yield a scaling factor.    
   
   
       31 . The method of  claim 30 , wherein the first and second results comprise estimates of first and second probability distributions.  
   
   
       32 . The method of  claim 30 , further comprising determining information about an event based on the scaling factor.  
   
   
       33 . The method of  claim 32 , wherein the information about the event comprises an estimate of a probability of occurrence of the event.