This paper introduces an analytical method to calculate segment-level wavefront error (WFE) tolerances to enable the detection of faint extra-solar planets using segmented-aperture telescopes in space. This study provides a full treatment of the case of spatially uncorrelated segment phasing errors for segmented telescope coronagraphy, which has so far only been approached using ad-hoc Monte Carlo (MC) simulations. Instead of describing the wavefront tolerance globally for all segments, our method produces spatially dependent requirement maps. We relate the statistical mean contrast in the coronagraph dark hole to the standard deviation of the WFE of each individual segment on the primary mirror. This statistical framework for segment-level tolerancing extends the Pair-based Analytical model for Segmented Telescope Imaging from Space (PASTIS), which is based uniquely on a matrix multiplication for the optical propagation. We confirm our analytical results with MC simulations of end-to-end optical propagations through a coronagraph. Comparing our results for the Apodized Pupil Lyot Coronagraph designs for the Large Ultraviolet Optical Infrared telescope to previous studies, we show general agreement but we provide a relaxation of the requirements for a significant subset of segments in the pupil. These requirement maps are unique to any given telescope geometry and coronagraph design. The spatially uncorrelated segment tolerances we calculate are a key element of a complete error budget that will also need to include allocations for correlated segment contributions. We discuss how the PASTIS formalism can be extended to the spatially correlated case by deriving the statistical mean contrast and its variance for a non-diagonal aberration covariance matrix. The PASTIS tolerancing framework therefore brings a new capability that is necessary for the global tolerancing of future segmented space observatories.