Volumes Spanned by Random Points in the Hypercube | Zendy

Dyer M. E. | Zendy; Füredi Z. | Zendy; McDiarmid C. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Volumes Spanned by Random Points in the Hypercube

Author(s) -

Dyer M. E.,

Füredi Z.,

McDiarmid C.

Publication year - 1992

Publication title -

random structures and algorithms

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.314

H-Index - 69

eISSN - 1098-2418

pISSN - 1042-9832

DOI - 10.1002/rsa.3240030107

Subject(s) - hypercube , combinatorics , mathematics , volume (thermodynamics) , convex hull , constant (computer programming) , regular polygon , discrete mathematics , physics , geometry , computer science , quantum mechanics , programming language

Consider the hypercube [0, 1] n in R n . This has 2 n vertices and volume 1. Pick N = N(n) vertices independently at random, form their convex hull, and let V n be its expected volume. How large should N(n) be to pick up significant volume? Let k =2/√≈1.213, and let ϵ > 0. We shall show that, as n→∞, V n →0 if N(n)⩽(k−ϵ) n →1 if N(n) ⩾ ( k + ϵ) n . A similar result holds for sampling uniformly from within the hypercube, with constant .

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research