Abstract

We introduce the concept of accessibility and prove that any convex body X in the d-dimensional Euclidean space is accessible with relevant constants depending on d only. This property leads to a new algorithm which may be considered as a natural derandomization of the hit and run algorithm applied to generate a sequence of random points covering X uniformly. We prove stability of the Markov chain generated by the proposed algorithm and provide its rate of convergence

Author information

Contact details are reproduced from the original publication and may be historical.

Benoît Collins

Dép. de Mathématique et Statistique, Université d'Ottawa, 585 King Edward, Ottawa, Ontario, Canada K1N6N5
and: Department of Mathematics, Kyoto University, Japan
and: CNRS, Institut Camille Jordan Université Lyon 1, France

bcollins@uottawa.ca

Termeh Kousha

Dép. de Mathématique et Statistique, Université d'Ottawa, 585 King Edward, Ottawa, Ontario, Canada K1N6N5

tkousha@uottawa.ca

Rafał Kulik

Dép. de Mathématique et Statistique, Université d'Ottawa, 585 King Edward, Ottawa, Ontario, Canada K1N6N5

rkulik@uottawa.ca

Tomasz Szarek

Dept. of Mathematics, University of Gdańsk, ul. Wita Stwosza 57, 80-952 Gdańsk, Poland

szarek@intertele.pl

Karol Życzkowski

Institute of Physics, Jagiellonian University, ul. Reymonta 4, 30-059 Kraków, Poland
and: Center for Theoretical Physics, Polish Academy of Sciences, Warsaw, Poland

karol@tatry.if.uj.edu.pl

References

  1. W. Bruzda, V. Cappellini, H.-J. Sommers, K. Życzkowski: Random quantum operations, Phys. Lett., A 373 (2009) 320–324.https://doi.org/10.1016/j.physleta.2008.11.043Google Scholar
  2. S. L. Braunstein: Geometry of quantum inference, Phys. Lett., A 219 (1996) 169–174.https://doi.org/10.1016/0375-9601(96)00365-9Google Scholar
  3. V. Cappellini H.-J. Sommers, K. Życzkowski: Subnormalized states and tracenon-increasing maps, J. Math. Phys. 48, 052110 (2007) 19 p.https://doi.org/10.1063/1.2738359Google Scholar
  4. V. Cappellini H.-J. Sommers, W. Bruzda, K. Życzkowski: Random bistochastic matrices, J. Phys. A, Math. Theor. 42, 365209 (2009) 23 p.https://doi.org/10.1088/1751-8113/42/36/365209Google Scholar
  5. W. Doeblin: Sur les propriétés asymptotiques de mouvement régis par certains types de chaînes simples, Bull. Math. Soc. Roum. Sci. 39 (1937) 57–115.Google Scholar
  6. M. Dyer, A. Frieze, R. Kannan: A random polynomial-time algorithm for approximating the volume of convex bodies, J. Assoc. Comput. Mach. 38(1) (1991) 1–17.https://doi.org/10.1145/102782.102783Google Scholar
  7. F. John: Extremum problems with inequalities as subsidiary conditions, in: Studies and Essays, K. O. Friedrichs et al. (ed.), Interscience, New York (1948) 187–204.Google Scholar
  8. M. J. W. Hall: Random quantum correlations and density operator distributions, Phys. Lett., A 242 (1998) 123–129.https://doi.org/10.1016/S0375-9601(98)00190-XGoogle Scholar
  9. G. Kimura: The Bloch vector for n–level systems, Phys. Lett., A 314 (2003) 339–349.https://doi.org/10.1016/S0375-9601(03)00941-1Google Scholar
  10. L. Lovász: Random walks on graphs: a survey, in: Combinatorics. Paul Erdös is Eighty. Vol. 2, D. Miklós et al. (ed.), Bolyai Soc. Math. Stud. 2, János Bolyai Math. Soc., Budapest (1996) 353–397.Google Scholar
  11. L. Lovász, S. Vempala: Hit-and-run from a corner, SIAM J. Comput. 35(4) (2006) 985–1005.https://doi.org/10.1137/S009753970544727XGoogle Scholar
  12. L. Lovász, S. Vempala: The geometry of logconcave functions and sampling algorithms, Random Struct. Algorithms 30(3) (2007) 307–358.https://doi.org/10.1002/rsa.20135Google Scholar
  13. S. P. Meyn, R. L. Tweedie: Markov Chains and Stochastic Stability, Springer, London (1993).https://doi.org/10.1007/978-1-4471-3267-7Google Scholar
  14. G. Pisier: The Volume of Convex Bodies and Banach Space Geometry, Cambrige University Press, Cambridge (1999).Google Scholar
  15. L. I. Schiff: Quantum Mechanics, McGraw-Hill, New York (1968).Google Scholar
  16. K. Szymański, B. Collins, T. Szarek, K. Życzkowski: Convex set of quantum states with positive partial transpose analysed by hit and run algorithm, J. Phys. A (2017), in print, arXiv:1611.01194 [quant-ph].https://doi.org/10.1088/1751-8121/aa70f5Google Scholar
  17. S. Vempala: Geometric random walks: a survey, in: Combinatorial and Computational Geometry, J. E. Goodman et al. (ed.), MSRI Publications 52, Cambridge University Press, Cambridge (2005) 573–612.https://doi.org/10.1017/9781009701259.033Google Scholar
  18. K. Życzkowski, H.-J. Sommers: Induced measures in the space of mixed quantum states, J. Phys. A, Math. Gen. 34 (2001) 7111–7125.https://doi.org/10.1088/0305-4470/34/35/335Google Scholar
  19. K. Życzkowski, P. Horodecki, A. Sanpera, M. Lewenstein: Volume of the set of separable states, Phys. Rev. A 58 (1998) 883–892.https://doi.org/10.1103/PhysRevA.58.883Google Scholar

Suggested citation

B. Collins, T. Kousha, R. Kulik, T. Szarek, K. Życzkowski. “The Accessibility of Convex Bodies and Derandomization of the Hit and Run Algorithm.” Journal of Convex Analysis 24 (2017), No. 3, 903–916. https://doi.org/10.68381/jca24053

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2017. Rights now held by Banach Press.