| <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
| <html xmlns="http://www.w3.org/1999/xhtml" lang="en-US"> |
| <head> |
| <meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/> |
| <meta http-equiv="X-UA-Compatible" content="IE=11"/> |
| <meta name="generator" content="Doxygen 1.9.8"/> |
| <meta name="viewport" content="width=device-width, initial-scale=1"/> |
| <title>datasketches-cpp: bounds_binomial_proportions Class Reference</title> |
| <link href="tabs.css" rel="stylesheet" type="text/css"/> |
| <script type="text/javascript" src="jquery.js"></script> |
| <script type="text/javascript" src="dynsections.js"></script> |
| <link href="search/search.css" rel="stylesheet" type="text/css"/> |
| <script type="text/javascript" src="search/searchdata.js"></script> |
| <script type="text/javascript" src="search/search.js"></script> |
| <link href="doxygen.css" rel="stylesheet" type="text/css" /> |
| </head> |
| <body> |
| <div id="top"><!-- do not remove this div, it is closed by doxygen! --> |
| <div id="titlearea"> |
| <table cellspacing="0" cellpadding="0"> |
| <tbody> |
| <tr id="projectrow"> |
| <td id="projectalign"> |
| <div id="projectname">datasketches-cpp |
| </div> |
| </td> |
| </tr> |
| </tbody> |
| </table> |
| </div> |
| <!-- end header part --> |
| <!-- Generated by Doxygen 1.9.8 --> |
| <script type="text/javascript"> |
| /* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */ |
| var searchBox = new SearchBox("searchBox", "search/",'.html'); |
| /* @license-end */ |
| </script> |
| <script type="text/javascript" src="menudata.js"></script> |
| <script type="text/javascript" src="menu.js"></script> |
| <script type="text/javascript"> |
| /* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */ |
| $(function() { |
| initMenu('',true,false,'search.php','Search'); |
| $(document).ready(function() { init_search(); }); |
| }); |
| /* @license-end */ |
| </script> |
| <div id="main-nav"></div> |
| <!-- window showing the filter options --> |
| <div id="MSearchSelectWindow" |
| onmouseover="return searchBox.OnSearchSelectShow()" |
| onmouseout="return searchBox.OnSearchSelectHide()" |
| onkeydown="return searchBox.OnSearchSelectKey(event)"> |
| </div> |
| |
| <!-- iframe showing the search results (closed by default) --> |
| <div id="MSearchResultsWindow"> |
| <div id="MSearchResults"> |
| <div class="SRPage"> |
| <div id="SRIndex"> |
| <div id="SRResults"></div> |
| <div class="SRStatus" id="Loading">Loading...</div> |
| <div class="SRStatus" id="Searching">Searching...</div> |
| <div class="SRStatus" id="NoMatches">No Matches</div> |
| </div> |
| </div> |
| </div> |
| </div> |
| |
| <div id="nav-path" class="navpath"> |
| <ul> |
| <li class="navelem"><a class="el" href="namespacedatasketches.html">datasketches</a></li><li class="navelem"><a class="el" href="classdatasketches_1_1bounds__binomial__proportions.html">bounds_binomial_proportions</a></li> </ul> |
| </div> |
| </div><!-- top --> |
| <div class="header"> |
| <div class="summary"> |
| <a href="#pub-static-methods">Static Public Member Functions</a> | |
| <a href="classdatasketches_1_1bounds__binomial__proportions-members.html">List of all members</a> </div> |
| <div class="headertitle"><div class="title">bounds_binomial_proportions Class Reference</div></div> |
| </div><!--header--> |
| <div class="contents"> |
| |
| <p>Confidence intervals for binomial proportions. |
| <a href="classdatasketches_1_1bounds__binomial__proportions.html#details">More...</a></p> |
| |
| <p><code>#include <<a class="el" href="bounds__binomial__proportions_8hpp_source.html">bounds_binomial_proportions.hpp</a>></code></p> |
| <table class="memberdecls"> |
| <tr class="heading"><td colspan="2"><h2 class="groupheader"><a id="pub-static-methods" name="pub-static-methods"></a> |
| Static Public Member Functions</h2></td></tr> |
| <tr class="memitem:aeaf7a3842e7bc82772b1dc33891f8c50" id="r_aeaf7a3842e7bc82772b1dc33891f8c50"><td class="memItemLeft" align="right" valign="top">static double </td><td class="memItemRight" valign="bottom"><a class="el" href="classdatasketches_1_1bounds__binomial__proportions.html#aeaf7a3842e7bc82772b1dc33891f8c50">approximate_lower_bound_on_p</a> (uint64_t n, uint64_t k, double num_std_devs)</td></tr> |
| <tr class="memdesc:aeaf7a3842e7bc82772b1dc33891f8c50"><td class="mdescLeft"> </td><td class="mdescRight">Computes lower bound of approximate Clopper-Pearson confidence interval for a binomial proportion. <br /></td></tr> |
| <tr class="separator:aeaf7a3842e7bc82772b1dc33891f8c50"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a497df40100e75dd55e6f0cdccd90b60a" id="r_a497df40100e75dd55e6f0cdccd90b60a"><td class="memItemLeft" align="right" valign="top">static double </td><td class="memItemRight" valign="bottom"><a class="el" href="classdatasketches_1_1bounds__binomial__proportions.html#a497df40100e75dd55e6f0cdccd90b60a">approximate_upper_bound_on_p</a> (uint64_t n, uint64_t k, double num_std_devs)</td></tr> |
| <tr class="memdesc:a497df40100e75dd55e6f0cdccd90b60a"><td class="mdescLeft"> </td><td class="mdescRight">Computes upper bound of approximate Clopper-Pearson confidence interval for a binomial proportion. <br /></td></tr> |
| <tr class="separator:a497df40100e75dd55e6f0cdccd90b60a"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a04e345ceea6646f2789a4fc8868c470d" id="r_a04e345ceea6646f2789a4fc8868c470d"><td class="memItemLeft" align="right" valign="top">static double </td><td class="memItemRight" valign="bottom"><a class="el" href="classdatasketches_1_1bounds__binomial__proportions.html#a04e345ceea6646f2789a4fc8868c470d">estimate_unknown_p</a> (uint64_t n, uint64_t k)</td></tr> |
| <tr class="memdesc:a04e345ceea6646f2789a4fc8868c470d"><td class="mdescLeft"> </td><td class="mdescRight">Computes an estimate of an unknown binomial proportion. <br /></td></tr> |
| <tr class="separator:a04e345ceea6646f2789a4fc8868c470d"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:ab0c083907bbd0cf5c9532f7c094ae6ef" id="r_ab0c083907bbd0cf5c9532f7c094ae6ef"><td class="memItemLeft" align="right" valign="top">static double </td><td class="memItemRight" valign="bottom"><a class="el" href="classdatasketches_1_1bounds__binomial__proportions.html#ab0c083907bbd0cf5c9532f7c094ae6ef">erf</a> (double x)</td></tr> |
| <tr class="memdesc:ab0c083907bbd0cf5c9532f7c094ae6ef"><td class="mdescLeft"> </td><td class="mdescRight">Computes an approximation to the <a class="el" href="classdatasketches_1_1bounds__binomial__proportions.html#ab0c083907bbd0cf5c9532f7c094ae6ef" title="Computes an approximation to the erf() function.">erf()</a> function. <br /></td></tr> |
| <tr class="separator:ab0c083907bbd0cf5c9532f7c094ae6ef"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a842aac311b818d8b074f8d1c344b903a" id="r_a842aac311b818d8b074f8d1c344b903a"><td class="memItemLeft" align="right" valign="top">static double </td><td class="memItemRight" valign="bottom"><a class="el" href="classdatasketches_1_1bounds__binomial__proportions.html#a842aac311b818d8b074f8d1c344b903a">normal_cdf</a> (double x)</td></tr> |
| <tr class="memdesc:a842aac311b818d8b074f8d1c344b903a"><td class="mdescLeft"> </td><td class="mdescRight">Computes an approximation to normal_cdf(x). <br /></td></tr> |
| <tr class="separator:a842aac311b818d8b074f8d1c344b903a"><td class="memSeparator" colspan="2"> </td></tr> |
| </table> |
| <a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2> |
| <div class="textblock"><p>Confidence intervals for binomial proportions. </p> |
| <p>This class computes an approximation to the Clopper-Pearson confidence interval for a binomial proportion. Exact Clopper-Pearson intervals are strictly conservative, but these approximations are not.</p> |
| <p>The main inputs are numbers <em>n</em> and <em>k</em>, which are not the same as other things that are called <em>n</em> and <em>k</em> in our sketching library. There is also a third parameter, numStdDev, that specifies the desired confidence level.</p> |
| <ul> |
| <li> |
| <em>n</em> is the number of independent randomized trials. It is given and therefore known. </li> |
| <li> |
| <em>p</em> is the probability of a trial being a success. It is unknown. </li> |
| <li> |
| <em>k</em> is the number of trials (out of <em>n</em>) that turn out to be successes. It is a random variable governed by a binomial distribution. After any given batch of <em>n</em> independent trials, the random variable <em>k</em> has a specific value which is observed and is therefore known. </li> |
| <li> |
| <em>pHat</em> = <em>k</em> / <em>n</em> is an unbiased estimate of the unknown success probability <em>p</em>. </li> |
| </ul> |
| <p>Alternatively, consider a coin with unknown heads probability <em>p</em>. Where <em>n</em> is the number of independent flips of that coin, and <em>k</em> is the number of times that the coin comes up heads during a given batch of <em>n</em> flips. This class computes a frequentist confidence interval [lowerBoundOnP, upperBoundOnP] for the unknown <em>p</em>.</p> |
| <p>Conceptually, the desired confidence level is specified by a tail probability delta.</p> |
| <p>Ideally, over a large ensemble of independent batches of trials, the fraction of batches in which the true <em>p</em> lies below lowerBoundOnP would be at most delta, and the fraction of batches in which the true <em>p</em> lies above upperBoundOnP would also be at most delta.</p> |
| <p>Setting aside the philosophical difficulties attaching to that statement, it isn't quite true because we are approximating the Clopper-Pearson interval.</p> |
| <p>Finally, we point out that in this class's interface, the confidence parameter delta is not specified directly, but rather through a "number of standard deviations" numStdDev. The library effectively converts that to a delta via delta = normalCDF (-1.0 * numStdDev).</p> |
| <p>It is perhaps worth emphasizing that the library is NOT merely adding and subtracting numStdDev standard deviations to the estimate. It is doing something better, that to some extent accounts for the fact that the binomial distribution has a non-gaussian shape.</p> |
| <p>In particular, it is using an approximation to the inverse of the incomplete beta function that appears as formula 26.5.22 on page 945 of the "Handbook of Mathematical Functions" by Abramowitz and Stegun.</p> |
| <dl class="section author"><dt>Author</dt><dd>Kevin Lang </dd> |
| <dd> |
| Jon Malkin </dd></dl> |
| </div><h2 class="groupheader">Member Function Documentation</h2> |
| <a id="aeaf7a3842e7bc82772b1dc33891f8c50" name="aeaf7a3842e7bc82772b1dc33891f8c50"></a> |
| <h2 class="memtitle"><span class="permalink"><a href="#aeaf7a3842e7bc82772b1dc33891f8c50">◆ </a></span>approximate_lower_bound_on_p()</h2> |
| |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">static double approximate_lower_bound_on_p </td> |
| <td>(</td> |
| <td class="paramtype">uint64_t </td> |
| <td class="paramname"><em>n</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">uint64_t </td> |
| <td class="paramname"><em>k</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">double </td> |
| <td class="paramname"><em>num_std_devs</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">static</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Computes lower bound of approximate Clopper-Pearson confidence interval for a binomial proportion. </p> |
| <p>Implementation Notes:<br /> |
| The approximateLowerBoundOnP is defined with respect to the right tail of the binomial distribution.</p> |
| <ul> |
| <li> |
| We want to solve for the <em>p</em> for which sum<sub><em>j,k,n</em></sub>bino(<em>j;n,p</em>) = delta. </li> |
| <li> |
| We now restate that in terms of the left tail. </li> |
| <li> |
| We want to solve for the p for which sum<sub><em>j,0,(k-1)</em></sub>bino(<em>j;n,p</em>) = 1 - delta. </li> |
| <li> |
| Define <em>x</em> = 1-<em>p</em>. </li> |
| <li> |
| We want to solve for the <em>x</em> for which I<sub><em>x(n-k+1,k)</em></sub> = 1 - delta. </li> |
| <li> |
| We specify 1-delta via numStdDevs through the right tail of the standard normal distribution. </li> |
| <li> |
| Smaller values of numStdDevs correspond to bigger values of 1-delta and hence to smaller values of delta. In fact, usefully small values of delta correspond to negative values of numStdDevs. </li> |
| <li> |
| return <em>p</em> = 1-<em>x</em>. </li> |
| </ul> |
| <dl class="params"><dt>Parameters</dt><dd> |
| <table class="params"> |
| <tr><td class="paramname">n</td><td>is the number of trials. Must be non-negative. </td></tr> |
| <tr><td class="paramname">k</td><td>is the number of successes. Must be non-negative, and cannot exceed n. </td></tr> |
| <tr><td class="paramname">num_std_devs</td><td>the number of standard deviations defining the confidence interval </td></tr> |
| </table> |
| </dd> |
| </dl> |
| <dl class="section return"><dt>Returns</dt><dd>the lower bound of the approximate Clopper-Pearson confidence interval for the unknown success probability. </dd></dl> |
| |
| </div> |
| </div> |
| <a id="a497df40100e75dd55e6f0cdccd90b60a" name="a497df40100e75dd55e6f0cdccd90b60a"></a> |
| <h2 class="memtitle"><span class="permalink"><a href="#a497df40100e75dd55e6f0cdccd90b60a">◆ </a></span>approximate_upper_bound_on_p()</h2> |
| |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">static double approximate_upper_bound_on_p </td> |
| <td>(</td> |
| <td class="paramtype">uint64_t </td> |
| <td class="paramname"><em>n</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">uint64_t </td> |
| <td class="paramname"><em>k</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">double </td> |
| <td class="paramname"><em>num_std_devs</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">static</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Computes upper bound of approximate Clopper-Pearson confidence interval for a binomial proportion. </p> |
| <p>Implementation Notes:<br /> |
| The approximateUpperBoundOnP is defined with respect to the left tail of the binomial distribution.</p> |
| <ul> |
| <li> |
| We want to solve for the <em>p</em> for which sum<sub><em>j,0,k</em></sub>bino(<em>j;n,p</em>) = delta. </li> |
| <li> |
| Define <em>x</em> = 1-<em>p</em>. </li> |
| <li> |
| We want to solve for the <em>x</em> for which I<sub><em>x(n-k,k+1)</em></sub> = delta. </li> |
| <li> |
| We specify delta via numStdDevs through the right tail of the standard normal distribution. </li> |
| <li> |
| Bigger values of numStdDevs correspond to smaller values of delta. </li> |
| <li> |
| return <em>p</em> = 1-<em>x</em>. </li> |
| </ul> |
| <dl class="params"><dt>Parameters</dt><dd> |
| <table class="params"> |
| <tr><td class="paramname">n</td><td>is the number of trials. Must be non-negative. </td></tr> |
| <tr><td class="paramname">k</td><td>is the number of successes. Must be non-negative, and cannot exceed <em>n</em>. </td></tr> |
| <tr><td class="paramname">num_std_devs</td><td>the number of standard deviations defining the confidence interval </td></tr> |
| </table> |
| </dd> |
| </dl> |
| <dl class="section return"><dt>Returns</dt><dd>the upper bound of the approximate Clopper-Pearson confidence interval for the unknown success probability. </dd></dl> |
| |
| </div> |
| </div> |
| <a id="a04e345ceea6646f2789a4fc8868c470d" name="a04e345ceea6646f2789a4fc8868c470d"></a> |
| <h2 class="memtitle"><span class="permalink"><a href="#a04e345ceea6646f2789a4fc8868c470d">◆ </a></span>estimate_unknown_p()</h2> |
| |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">static double estimate_unknown_p </td> |
| <td>(</td> |
| <td class="paramtype">uint64_t </td> |
| <td class="paramname"><em>n</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">uint64_t </td> |
| <td class="paramname"><em>k</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">static</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Computes an estimate of an unknown binomial proportion. </p> |
| <dl class="params"><dt>Parameters</dt><dd> |
| <table class="params"> |
| <tr><td class="paramname">n</td><td>is the number of trials. Must be non-negative. </td></tr> |
| <tr><td class="paramname">k</td><td>is the number of successes. Must be non-negative, and cannot exceed n. </td></tr> |
| </table> |
| </dd> |
| </dl> |
| <dl class="section return"><dt>Returns</dt><dd>the estimate of the unknown binomial proportion. </dd></dl> |
| |
| </div> |
| </div> |
| <a id="ab0c083907bbd0cf5c9532f7c094ae6ef" name="ab0c083907bbd0cf5c9532f7c094ae6ef"></a> |
| <h2 class="memtitle"><span class="permalink"><a href="#ab0c083907bbd0cf5c9532f7c094ae6ef">◆ </a></span>erf()</h2> |
| |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">static double erf </td> |
| <td>(</td> |
| <td class="paramtype">double </td> |
| <td class="paramname"><em>x</em></td><td>)</td> |
| <td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">static</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Computes an approximation to the <a class="el" href="classdatasketches_1_1bounds__binomial__proportions.html#ab0c083907bbd0cf5c9532f7c094ae6ef" title="Computes an approximation to the erf() function.">erf()</a> function. </p> |
| <dl class="params"><dt>Parameters</dt><dd> |
| <table class="params"> |
| <tr><td class="paramname">x</td><td>is the input to the erf function </td></tr> |
| </table> |
| </dd> |
| </dl> |
| <dl class="section return"><dt>Returns</dt><dd>returns erf(x), accurate to roughly 7 decimal digits. </dd></dl> |
| |
| </div> |
| </div> |
| <a id="a842aac311b818d8b074f8d1c344b903a" name="a842aac311b818d8b074f8d1c344b903a"></a> |
| <h2 class="memtitle"><span class="permalink"><a href="#a842aac311b818d8b074f8d1c344b903a">◆ </a></span>normal_cdf()</h2> |
| |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">static double normal_cdf </td> |
| <td>(</td> |
| <td class="paramtype">double </td> |
| <td class="paramname"><em>x</em></td><td>)</td> |
| <td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">static</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Computes an approximation to normal_cdf(x). </p> |
| <dl class="params"><dt>Parameters</dt><dd> |
| <table class="params"> |
| <tr><td class="paramname">x</td><td>is the input to the normal_cdf function </td></tr> |
| </table> |
| </dd> |
| </dl> |
| <dl class="section return"><dt>Returns</dt><dd>returns the approximation to normalCDF(x). </dd></dl> |
| |
| </div> |
| </div> |
| <hr/>The documentation for this class was generated from the following file:<ul> |
| <li>common/include/<a class="el" href="bounds__binomial__proportions_8hpp_source.html">bounds_binomial_proportions.hpp</a></li> |
| </ul> |
| </div><!-- contents --> |
| <!-- start footer part --> |
| <hr class="footer"/><address class="footer"><small> |
| Generated by <a href="https://www.doxygen.org/index.html"><img class="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.9.8 |
| </small></address> |
| </body> |
| </html> |
