IDEAS home Printed from https://ideas.repec.org/a/eee/csdana/v80y2014icp26-43.html
   My bibliography  Save this article

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 search 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 & Jörg Stoye, 2013. "Nonparametric analysis of random utility models: testing," CeMMAP working papers 36/13, Institute for Fiscal Studies.
    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. 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.
    6. Yuichi Kitamura & Jorg Stoye, 2019. "Nonparametric Counterfactuals in Random Utility Models," Papers 1902.08350, arXiv.org, revised May 2019.
    7. Kock, Anders Bredahl & Preinerstorfer, David & Veliyev, Bezirgen, 2023. "Treatment recommendation with distributional targets," Journal of Econometrics, Elsevier, vol. 234(2), pages 624-646.
    8. 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.
    9. 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.
    10. Christoph Rothe, 2012. "Partial Distributional Policy Effects," Econometrica, Econometric Society, vol. 80(5), pages 2269-2301, September.
    11. Matthew A. Masten & Alexandre Poirier, 2018. "Identification of Treatment Effects Under Conditional Partial Independence," Econometrica, Econometric Society, vol. 86(1), pages 317-351, January.
    12. 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.
    13. Manski, Charles F., 2016. "Credible interval estimates for official statistics with survey nonresponse," Journal of Econometrics, Elsevier, vol. 191(2), pages 293-301.
    14. Javier Arroyo & Rosa Espínola & Carlos Maté, 2011. "Different Approaches to Forecast Interval Time Series: A Comparison in Finance," Computational Economics, Springer;Society for Computational Economics, vol. 37(2), pages 169-191, February.
    15. Tobias Eckernkemper & Bastian Gribisch, 2021. "Classical and Bayesian Inference for Income Distributions using Grouped Data," Oxford Bulletin of Economics and Statistics, Department of Economics, University of Oxford, vol. 83(1), pages 32-65, February.
    16. Luther Yap, 2022. "Sensitivity of Policy Relevant Treatment Parameters to Violations of Monotonicity," Working Papers 655, Princeton University, Department of Economics, Industrial Relations Section..
    17. Matthew Masten & Alexandre Poirier, 2016. "Partial independence in nonseparable models," CeMMAP working papers CWP26/16, Centre for Microdata Methods and Practice, Institute for Fiscal Studies.
    18. Xavier D'Haultfœuille & Roland Rathelot, 2017. "Measuring segregation on small units: A partial identification analysis," Quantitative Economics, Econometric Society, vol. 8(1), pages 39-73, March.
    19. David M Kaplan & Wei Zhao, 2023. "Comparing latent inequality with ordinal data," The Econometrics Journal, Royal Economic Society, vol. 26(2), pages 189-214.
    20. Stefan Hoderlein & Jörg Stoye, 2015. "Testing stochastic rationality and predicting stochastic demand: the case of two goods," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 3(2), pages 313-328, October.

    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.