Evaluation of the patterning accuracy of e-beam lithography machines requires a high precision inspection system that is capable of measuring the true xy-locations of fiducial marks generated by the e-beam machine under test. Fiducial marks are fabricated on a single photo mask over the entire working area in the form of equally spaced two-dimensional grids. In performing the evaluation, the principles of self-calibration enable to determine the deviations of fiducial marks from their nominal xy-locations precisely, not being affected by the motion errors of the inspection system itself. It is, however, the fact that only repeatable motion errors can be eliminated, while random motion errors encountered in probing the locations of fiducial marks are not removed. Even worse, a random error occurring from the measurement of a single mark propagates and affects in determining locations of other marks, which phenomenon in fact limits the ultimate calibration accuracy of e-beam machines. In this paper, we describe an uncertainty analysis that has been made to investigate how random errors affect the final result of self-calibration of e-beam machines when one uses an optical inspection system equipped with high-resolution microscope objectives and a precision xy-stages. The guide of uncertainty analysis recommended by the International Organization for Standardization is faithfully followed along with necessary sensitivity analysis. The uncertainty analysis reveals that among the dominant components of the patterning accuracy of e-beam lithography, the rotationally symmetrical component is most significantly affected by random errors, whose propagation becomes more severe in a cascading manner as the number of fiducial marks increases.