Unlike their hard realtime counterparts, soft realtime applications are only expected to guarantee their "expected delay" over input data space. This paradigm shift calls for customized statistical design techniques to replace the conventional pessimistic worst case analysis methodologies. Statistical design methods can provide a realistic assessment of design space, and improve the design quality by exploiting its stochastic behavior. We present a novel probabilistic time budgeting algorithm that translates the application expected delay constraint into its components delay constraints. Our algorithm which is based on mathematical properties of the problem, determines the optimal maximum weighted timing relaxation of an application under expected delay constraint. Experimental results on core-based synthesis of several multi-media applications on FPGAs show about 20% and 19% average energy and area improvement, respectively.