IDEAS home Printed from https://ideas.repec.org/a/eee/csdana/v80y2014icp26-43.html

The complexity of computation and approximation of the t-ratio over one-dimensional interval data

Author

Listed:
  • Černý, Michal
  • Hladík, Milan

Abstract

The main question is how to compute the upper and lower limits of the range of possible values of a given statistic, when the data range over given intervals. Initially some well-known statistics, such as sample mean, sample variance or F-ratio, are considered in order to illustrate that in some cases the limits can be computed efficiently, while in some cases their computation is NP-hard. Subsequently, the t-ratio (variation coefficient) is considered. It is investigated when the limits for t-ratio are computable in polynomial time and a new efficient algorithm is designed for this case. Conversely, complementary NP-hardness results are proved, demonstrating the cases when the computation cannot be done efficiently. Subsequently, the NP-hardness results are strengthened: it is shown that under certain assumptions, even an approximate evaluation with an arbitrary absolute error is NP-hard. Finally, it is shown that the situation can also be (in some sense) regarded positively: a new pseudopolynomial algorithm is developed. The algorithm is of practical importance, especially when the dataset to be processed is large and does not contain “excessively” large numbers.

Suggested Citation

  • Černý, Michal & Hladík, Milan, 2014. "The complexity of computation and approximation of the t-ratio over one-dimensional interval data," Computational Statistics & Data Analysis, Elsevier, vol. 80(C), pages 26-43.
    • Handle: RePEc:eee:csdana:v:80:y:2014:i:c:p:26-43
    DOI: 10.1016/j.csda.2014.06.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0167947314001789
    Download Restriction: Full text for ScienceDirect subscribers only.
    File URL: https://libkey.io/10.1016/j.csda.2014.06.007?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Montes, Ignacio & Miranda, Enrique & Montes, Susana, 2014. "Stochastic dominance with imprecise information," Computational Statistics & Data Analysis, Elsevier, vol. 71(C), pages 868-886.
    2. Jörg Stoye, 2010. "Partial identification of spread parameters," Quantitative Economics, Econometric Society, vol. 1(2), pages 323-357, November.
    3. Ling He & Chenyi Hu, 2009. "Impacts of Interval Computing on Stock Market Variability Forecasting," Computational Economics, Springer;Society for Computational Economics, vol. 33(3), pages 263-276, April.
    4. Corani, G. & Antonucci, A., 2014. "Credal ensembles of classifiers," Computational Statistics & Data Analysis, Elsevier, vol. 71(C), pages 818-831.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Milan Hladík & Michal Černý & Jaromír Antoch, 2020. "EIV regression with bounded errors in data: total ‘least squares’ with Chebyshev norm," Statistical Papers, Springer, vol. 61(1), pages 279-301, February.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ismaël Mourifié & Marc Henry & Romuald Méango, 2020. "Sharp Bounds and Testability of a Roy Model of STEM Major Choices," Journal of Political Economy, University of Chicago Press, vol. 128(8), pages 3220-3283.
    2. Yuichi Kitamura & Jorg Stoye, 2013. "Nonparametric Analysis of Random Utility Models: Testing," Cowles Foundation Discussion Papers 1902, Cowles Foundation for Research in Economics, Yale University.
    3. Jiang, Yanping & Liang, Xia & Liang, Haiming & Yang, Ningman, 2018. "Multiple criteria decision making with interval stochastic variables: A method based on interval stochastic dominance," European Journal of Operational Research, Elsevier, vol. 271(2), pages 632-643.
    4. Vishal Kamat, 2017. "Identifying the Effects of a Program Offer with an Application to Head Start," Papers 1711.02048, arXiv.org, revised Aug 2023.
    5. Yuichi Kitamura & Jorg Stoye, 2019. "Nonparametric Counterfactuals in Random Utility Models," Papers 1902.08350, arXiv.org, revised May 2019.
    6. Kock, Anders Bredahl & Preinerstorfer, David & Veliyev, Bezirgen, 2023. "Treatment recommendation with distributional targets," Journal of Econometrics, Elsevier, vol. 234(2), pages 624-646.
    7. Matthew Masten & Alexandre Poirier, 2016. "Partial independence in nonseparable models," CeMMAP working papers 26/16, Institute for Fiscal Studies.
    8. David M Kaplan & Wei Zhao, 2023. "Comparing latent inequality with ordinal data," The Econometrics Journal, Royal Economic Society, vol. 26(2), pages 189-214.
    9. Fan, Yanqin & Guerre, Emmanuel & Zhu, Dongming, 2017. "Partial identification of functionals of the joint distribution of “potential outcomes”," Journal of Econometrics, Elsevier, vol. 197(1), pages 42-59.
    10. Angela Blanco-Fernández & Peter Winker, 2016. "Data generation processes and statistical management of interval data," AStA Advances in Statistical Analysis, Springer;German Statistical Society, vol. 100(4), pages 475-494, October.
    11. Philip Marx, 2020. "Sharp Bounds in the Latent Index Selection Model," Papers 2012.02390, arXiv.org, revised Apr 2023.
    12. Yanqin Fan & Sang Soo Park, 2009. "Partial identification of the distribution of treatment effects and its confidence sets," Advances in Econometrics, in: Nonparametric Econometric Methods, pages 3-70, Emerald Group Publishing Limited.
    13. Etheridge, Ben, 2015. "A test of the household income process using consumption and wealth data," European Economic Review, Elsevier, vol. 78(C), pages 129-157.
    14. Christoph Rothe, 2012. "Partial Distributional Policy Effects," Econometrica, Econometric Society, vol. 80(5), pages 2269-2301, September.
    15. Girsberger, Esther Mirjam & Méango, Romuald & Rapoport, Hillel, 2020. "Regional migration and wage inequality in the West African economic and monetary union," Journal of Comparative Economics, Elsevier, vol. 48(2), pages 385-404.
    16. François Gerard & Miikka Rokkanen & Christoph Rothe, 2020. "Bounds on treatment effects in regression discontinuity designs with a manipulated running variable," Quantitative Economics, Econometric Society, vol. 11(3), pages 839-870, July.
    17. Matthew A. Masten & Alexandre Poirier, 2018. "Identification of Treatment Effects Under Conditional Partial Independence," Econometrica, Econometric Society, vol. 86(1), pages 317-351, January.
    18. Henning Fischer & Ángela Blanco‐FERNÁndez & Peter Winker, 2016. "Predicting Stock Return Volatility: Can We Benefit from Regression Models for Return Intervals?," Journal of Forecasting, John Wiley & Sons, Ltd., vol. 35(2), pages 113-146, March.
    19. Manski, Charles F., 2016. "Credible interval estimates for official statistics with survey nonresponse," Journal of Econometrics, Elsevier, vol. 191(2), pages 293-301.
    20. Molinari, Francesca, 2020. "Microeconometrics with partial identification," Handbook of Econometrics, in: Steven N. Durlauf & Lars Peter Hansen & James J. Heckman & Rosa L. Matzkin (ed.), Handbook of Econometrics, edition 1, volume 7, chapter 0, pages 355-486, Elsevier.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:csdana:v:80:y:2014:i:c:p:26-43. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/csda .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.