Вычислительные аспекты вероятностных расширений | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 47. DOI: 10.17223/19988605/47/5

Вычислительные аспекты вероятностных расширений

В статье предлагается новый подход к вычислению функций со случайными аргументами. Подход основан на идее уменьшения размерности функции путем вычисления определенных интегралов и использования вычислительного вероятностного анализа. Применяется одно из основных понятий вычислительного вероятностного анализа - вероятностное расширение для вычисления функции со случайными аргументами. Для реализации этого метода предлагается способ, основанный на параллельных рекурсивных вычислениях. Приведены численные примеры, демонстрирующие эффективность предложенного подхода.

Computational aspects of probabilistic extensions.pdf Problems of modelling can be reduced to the numerical analysis of functions [1]. Z = f(x, x2 xn ) • Let (x1,...,xn) be a system of continuous random variables with joint probability density function p(xl,...,xn) and random variable z is a function f (xl,..,xn). Consider main methods to find the distribution of random variable z. These are to use the cumulative distribution function F(y) = P(f (x. xn ) < y) and the probability z < y is determined by the formula P(z < У) =fn P(x v,x„)dx1 •••dxn, (1) JUy where П = {(xj,..., xK) | f (x ,.., xK ) < y). Further, the probability density function f of random variable z is defined as the derivative [2] f (y=-• dy In the case of the monotone function f (x), the distribution density f of the random variable z is defined as [2] as follows: f(y) = f(ry)) I (rl)'(y) I, (2) where f-1 is the inverse function of f . Note that the calculation of the integral (1) and the use of the formula (2) in some cases is rather difficult. Moreover, one of the reasons for the emergence of the Monte Carlo method was the need to calculate integrals of the form (1) in the case of large values of n. Thus, the Monte Carlo method is often the only way to calculate the probability density function f of a random variable z. Monte Carlo method is a powerful approach, but it has some serious shortcomings, first of all, this is an extremely low rate of convergence. Non-Monte Carlo methods have been developed since the 1960s. A major non-Monte Carlo approach is interval analysis. However, interval analysis computing only to the boundaries of random processes, without examining their internal distributions. An important special case is operations on independent random variables. In the papers [3-6], various approaches for numerical operations on densities of random variables are considered. In our work, we develop a technique that uses Computational Probabilistic Analysis (CPA) to solve various problems with stochastic data uncertainty [7-9]. The basis of computational probabilistic analysis is numerical operations on probability density functions of the random values. These are operations "+", " -", " •", "/", "T ", "max", "min", as well as binary relations " < "," > " and some others. The numerical operations of the piecewise polynomial function arithmetic constitute the major component of CPA. The use of CPA for these problems is more effective than the Monte Carlo method in a thousand times. Using the arithmetic of probability density functions and probabilistic extensions, we can construct numerical methods that enable us solving systems of linear and nonlinear algebraic equations with random parameter [7, 8]. We will use piecewise polynomial models to represent probability density functions [10-12]: - piecewise constant functions (histograms); - piecewise linear functions (frequency polygons); - piecewise polynomial functions (splines). 1. Probabilistic extensions One of the most important problems that NPA deals with is to construct probability density functions of random variables. Let z be a function f (xxn) Z - f ( X1,:., X„ ). Definition. By probabilistic extension f (£,x v..,xn) of the function f, we mean a probability density function z of the random variable z z(Q - f fe X1,; xn). Definition. Support of the probability density functions f will be called the set supp(f) - (x I f (x) > 0}. One possible way to estimate the probability density z of a random variable z Z - f(X1,:., Xn ). (3) is the Monte Carlo method [13]. For these purposes a random vector {x[,..., x'n) with joint probability density function p(xlxn) is generated. Further calculated zi - f (xi,...,xin),i - 1,...,N. Using the histogram method for z1, we can construct an estimate of the probability density function z. We study the properties of the probability density z. Build the grid (z0, z1 ,...zk}e supp(z) and calculate the number щ of sample points falling in each segment zM, z,. It is known that histograms converge to the probability density function of the mean integral value pt - n z zttЩ. N J zi-1 Build the grid (t0,t,-tm} с supp(Xl) and calculate the number m. of sample points falling in each segment tj_j,t.. p1 - m^. P' N Consider only those random vectors (x[,...,xn) for such (x e(tj_tj). Number such vectors is equal exactly m .. If vyl is the number of sample points falling in each segment zlzl, then m n-£v л j p = n=z m h. N j N mj m Going to the limit at N ^ с m. x«' • N Further, let for any t e supp xt we can construct a probabilistic extension f (•, t, x2,.--, x„) V n « f (t, X 2 ,..., X n ) . mj Increasing the dimension of the grids and going to the limit, we obtain f (4) = f x1 X (t)f (4, t, X2,..., Xn )dt. (4) ^xi Thus proven Theorem. Theorem 1. Let f (4,X,-•,Xn) be probabilistic extensions of function f (%,x2,...,xn) and for each real t function f (4,t,X2,...,X„) be probabilistic extensions of the function f (t,x2,...,x„). Then f(4, X,..., x„„ = fxi x (t )f(4, t, X2,..., Xn)dt. (5) Jx1 Corollary. Theorem 1 infers the possibility of recursive computations for the general form of probability extensions and reduction to the calculation of the one-dimensional case. Let us consider the computing of the integral (5). For simplicity, we represent (5) as a numerical quadrature - m fx1 X1 (t)f (4, t, x2 ,..., x„ )dt « £ y X1(t )f (4, h, x2 ,..., x„ ). x1 i=1 Further, for the computing f (4, tl, X2,..., Xn) we can also use numerical quadratures and so on. In general, it is NP-hard problem with actual parallelization. and Fig. 1. The tree of the parallel recursive programming In Fig. 1 we are shown the tree of the parallel recursive organization of the computational process. Thus, on the lower layer, it is necessary to computing the probabilistic extensions only for one variable. Note that all computations on each layer are independent and can be computed simultaneously. 2. One-dimensional case Consider the procedure for computing the probabilistic extensions for the one-dimensional case. Let there be given a functional dependence ^ = f (x), where x is a random variable. Let x be the probability density function of a random variable x with support [x, x]. Further [rt (z) e [x, x] | i = 1,.., n} are the roots of the equation z = f (x). Following the main method (1) it is easy to construct a generalization of the expression (2). We can represent probabilistic extensions f (•, x) of function f (x) in the form f(Ex) = 2 X(r(E)) ) 21f'(r(E))I' Example 1. As an example, consider the construction of a probabilistic extensions function f = ax2 + bx, a > 0, b > 0, x is random variable distributed on [0,2] by a triangular law ' E if E e[0,1), Further Finally Put a = 1 and b = 0 x(E) = < ^ [2 - E if E e [1,2]' , ч yj4az + b2 + b , ч V4az+b2-b r1 (Z) =--1-, r2 (Z) = -1-' 2a 2a г-^ are roots z = f (r). Choose a positive root r (E) = r2 (E) = --, and 2a [ax2 + bx]' = 2ax + b = V 4az + b2' f (E, X) = x(r (E)) Ц 4aE + b2' f 1 / 2 if E e [0,1), f (E, x) = ^ ^ /4!-1 /2 if Ee [1,4]' 2.1. Numerical approach Consider a numerical approach to construct a probabilistic extensions f of function f (x). For these purposes, we construct in the support [x, x] of the probability density function x a grid {Ei I Ei e [x, x], i = 0,1,2'„n} and compute (z; = f (E,), i = 0,1,2„n}. Next we set f (z.) I (f '(Ei )l and using (z, f (z)) we construct a piecewise polynomial interpolation. So, for Example 1. the support is [0,2], E, = i /10,i = 0,1,.,20. With a = 1, b = 0 we get (Zi, fz(Zi)) = {(i /10)2,X(i^10> i = 0,1,.,20' I. i / 5 ) Fig. 2. Probabilistic extensions f (■, x) The Fig. 2 shows the probability density function f (■,x) from Example 1. Unlike the general approach, there is no need to find the roots of the equation. 3. Two dimensional case Let (x,y) be a system of continuous random variables with joint probability density function p(x,y) and the random variable z is a function f (x, y) z = f (x y). Need to find probability density function the random variable z. Define Я = {(x,y) I z > f (x,y)} and cdf F the random variable z probability density function of z Consequently F=L p^x' y) dxdy f = -F ■ dz Assuming that dx = 0 then and Finally get where - fz = d L p(x y)dxdy = dz dz Jnz J p(x,y)dxdy - J p(x,y)dxdy = lim dz^0 . L dz p( x, y) dxdy = lim dz^0 dz dz = f' dy dS = dxdy = dxdz/1 f' |. p( x, y) dx, fz(z)=L Jrz I f'y(x,y) | ' ^z = {(x,y) I z = f (x,y)} = {(x,y(x))}. Let p(t, y(Q) /Л t) - | f ' y(t )) | be probabilistic extensions of f (t, y). Thus, the calculation of the probabilistic extension f is reduced to the calculation of the integral of probabilistic extensions f (t, y). Example 2. Consider the construction of a probabilistic extension for the function 5 5 z = x y + xy . Let t be real, put y = t and a probabilistic extension for the function 2 , , ,2 zx = x t + xt . is zx(4, t) = x(n(£)) Ц4t£ +14, where n(£) = +14 - 6) / (2t). Thus, the probabilistic extension for г can be represented as Z) = IУ (t )zx(^, t )dt = j y (t) x (n©) Ц 4ic +14 dt. (6) 4. Random Boundary value Problem Consider using probabilistic extensions to calculate solutions Random Boundary value Problem [14] Lu = -pu+ qu = f (x), x е (0,1), (7) with boundary conditions u (0) = 0, u (1) = 0. where p > 0, q > 0, p, q are independent random variables. Let Qh = (x,. = ih,i = 1,2,..., N -1, h = 1 / N} be grid and Lhuh = -p u'-1 - 2u' + u+1 + qu = f (x), i = 1,2,..., N -1. h is difference scheme. [p,p], [q,q] are supports ofp, q. Generate grids Qp = (P0 = P < P1 < ■■■< Pk = P} and Qq = (q0 = q < q < ...< qL = q} . Solve numerically KL problems u. , -2u. + u.^, ч , „ ,T , -pk i-1 5 2'-- + = f (x),i = 1,2,...,N -1. h Thus we get an array of solutions ulH = u,. (pk, q). Consider building probability density functions for ut. For these purposes, we construct Hermitian cubic splines sl(p), l = 0,1,.,10 using the values u,(p*,q). In fig. 3 they are shown in solid line. Further for some £ we find the roots p st(Pl) = l = 0,1,...,10. The values of и (£) are computed using numerical quadratures, for example, Simpson quadratures 10 ui ©=hI Yk q(qk) p( pk) / s'( pk). k =0 In fig. 3 line of integration mark = 'o'. Note, Simpson quadratures and cubic splines have O(h4) accuracy. Numerical experiments with K, L = 10 showed good agreement with the Monte Carlo method with the number of samples ~ 106. Thus, in this example, the proposed method turned out to be more efficient than Monte Carlo ~ 104 times. Fig. 3. Construction of probabilistic extensions for ui, 1 are splines, 2 is a line of integration Remark. The main computational costs are spent on building the set ~ O(KLN). Computational costs building of the probability extension of u is O(m). Therefore, once you have , you can compute relatively quickly Ui for different p, q. Conclusion The proposed approach makes it possible to solve the problem of computing the probability density function in the modeling processes with random input data. For these purposes we propose using a parallel-recursive organization of the computational process. Thus, the important problem of computing probability extensions can be solved within parallel recursive programming. This opens multifold possibilities for studying various models with random input data. Fast and accurate calculations are based on the properties of numerical arithmetic procedures over piecewise polynomial models developed within the framework of computational probabilistic analysis.

Ключевые слова

computational probabilistic analysis, probabilistic extensions, non-Monte Carlo methods, random boundary value problem, вычислительный вероятностный анализ, вероятностные расширения, не Монте-Карло методы, случайные краевые задачи


Добронец Борис СтаниславовичСибирский федеральный университетпрофессор, доктор физико-математических наук, профессор кафедры систем искусственного интеллектаBDobronets@yandex.ru
Попова Ольга АркадьевнаСибирский федеральный университеткандидат технических наук, доцент кафедры систем искусственного интеллектаOlgaArc@yandex.ru
Всего: 2


Rocquigny, E. (2012) Modelling Under Risk and Uncertainty: An Introduction to Statistical, Phenomenological and Computational Methods. Wiley Series in Probability and Statistics. John Wiley & Sons.
Springer, M.D. (1979) The Algebra of Random Variables. New York; Chichester; Brisbane: John Wiley & Sons.
Gerasimov, V.A., Dobronets, B.S. & Shustrov M.Yu. (1991) Numerical operations of histogram arithmetic and their applications. Automation and Remote Control. 52(2). pp. 208-212.
Williamson, R. & Downs, T. (1990) Probabilistic arithmetic i: numerical methods for calculating convolutions and dependency bounds. International Journal of Approximate Reasoning. 4(2). pp. 89-158. DOI: 10.1016/0888-613X(90)90022-T
Li, W. & Hym, J. (2004) Computer arithmetic for probability distribution variables. Reliability Engineering and System Safety. 85(1-3). pp. 191-209. DOI: 10.1016/j.ress.2004.03.012
Jaroszewicz, S. & Korzen, M. (2012) Arithmetic operations on independent random variables: a numerical approach. SIAM J. Sci. Comput. 34(3). pp. A1241-A1265. DOI: 10.1137/110839680
Dobronets, B.S. & Popova, O.A. (2014) Numerical probabilistic analysis under aleatory and epistemic uncertainty. Reliable Computing. 19. pp. 274-289.
Dobronets, B. & Popova, O. (2016) Numerical Probabilistic Approach for Optimization Problems. Scientific Computing, Computer Arithmetic, and Validated Numerics. Lecture Notes in Computer Science. Vol. 9553. Springer International Publishing, Cham. pp. 43-53.
Dobronets, B.S. & Popova, O.A. (2017) Improving the accuracy of the probability density function estimation. Journal of Siberian Federal University, Mathematics and Physics. 10(1). pp. 16-21. DOI: 10.17516/1997-1397-2017-10-1-16-21
Dobronets, B.S. & Popova, O.A. (2018) Piecewise Polynomial Aggregation as Preprocessing for Data Numerical Modeling. IOP Conf. Series: Journal of Physics: Conf. Series. 1015. DOI:10.1088/1742-6596/1015/3/032028
Dobronets, B.S. & Popova, O.A. (2018) Improving reliability of aggregation, numerical simulation and analysis of complex systems by empirical data. IOP Conf. Series: Materials Science and Engineering. 354. D0I:10.1088/1757-899X/354/1/012006
Popova, O.A. (2019) Using Richardson extrapolation to improve the accuracy of procesing and analyzing empirical data. Measurement Techniques. 2. pp. 18-22.
Mikhailov, G.A. & Voitishek, A.V. (2018) Statisticheskoe modelirovanie: metodMonte-Karlo [Statistical modeling. Monte Carlo methods]. Moscow: Yurait.
Soong, T.T. (1973) Random Differential Equations in Science and Engineering. New York and London: Academic Press.
 Вычислительные аспекты вероятностных расширений | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 47. DOI: 10.17223/19988605/47/5

Вычислительные аспекты вероятностных расширений | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 47. DOI: 10.17223/19988605/47/5