This paper introduces an analytical method to calculate segment-level wavefront error tolerances in order to enable the detection of faint extra-solar planets using segmented telescopes in space. This study provides a full treatment of spatially uncorrelated segment phasing errors for segmented telescope coronagraphy, which has so far only been approached using ad hoc Monte-Carlo simulations. Instead of describing the wavefront tolerance globally for all segments, our method produces spatially dependent requirements. We relate the statistical mean contrast in the coronagraph dark hole to the standard deviation of the wavefront error 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 Monte-Carlo simulations of E2E optical propagations through a coronagraph. Comparing our results for the Apodized Pupil Lyot Coronagraph designs for the Large UltraViolet Optical InfraRed (LUVOIR) telescope to previous studies, we show general agreement but provide a relaxation of the requirements for a significant subset of segments. 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.