On the Maximum of Bivariate Normal Random Variables

The behavior of the mean and variance of the maximum of bivariate normal random variables to changes in the means, variances, and covariance of the underlying random variables is considered.     

Upper Bounds for the Expected Maxima of Independent Random Variables Given Known First Four Moments

Mathematical Notes - The paper is devoted to the study of conditional bounds for the expectation of the maximum of independent identically distributed standardized random variables for which the...     

On the Distribution of the Extremes of Unequally Correlated Normal Variables with Applications to Antedependent Cluster Data

Based on a small correlations approach, this paper deals with the probability distributions of the order statistics under a general Gaussian model with unequal (positive or negative) correlations. Illustrations are given for the cluster data those follow suitable antedependence models.     

On the Complexity of Computing Error Bounds

We consider the cost of estimating an error bound for the computed solution of a system of linear equations, i.e., estimating the norm of a matrix inverse. Under some technical assumptions we show that computing even a coarse error bound for the solution of a triangular system of equations costs at least as much as testing whether the product of two matrices is zero. The complexity of the latter problem is in turn conjectured to be the same as matrix multiplication, matrix inversion, etc. Since most error bounds in practical use have much lower complexity, this means they should sometimes exhibit large errors. In particular, it is shown that condition estimators that: (1) perform at least one operation on each matrix entry; and (2) are asymptotically faster than any zero tester, must sometimes over or underestimate the inverse norm by a factor of at least , where n is the dimension of the input matrix, k is the bitsize, and where either or grows faster than any polynomial in n . Our results hold for the RAM model with bit complexity, as well as computations over rational and algebraic numbers, but not real or complex numbers. Our results also extend to estimating error bounds or condition numbers for other linear algebra problems such as computing eigenvectors. September 10, 1999. Final version received: August 23, 2000.     

Moment Bounds on Discrete Expected Stop-Loss Transforms, with Applications

This paper shows how to make the best possible use of the information contained in the first few moments (mean, variance and skewness, say) of an integer-valued random variable when one is interested in expected stop-loss transforms. This allows to bound various quantities in applied probability, including the ruin probabilities, for instance.      

On the Maximum Expected Flow in a Network

Consider a graph G in which every arc (i, j) has two numbers, ρ_ij and c_ij, associated with it representing the reliability and capacity of the arc respectively. It is shown that the expected flow is equal to the sum of the expected capacities of the paths from source to sink. An algorithm is described to find the maximum expected flow in the network.     

随机变量数学期望的一个注记

介绍一种计算随机变量数学期望的方法,利用这种方法容易得到数学期望的相关性质,很多概率与矩的不等式证明也因之变得更为简洁.     

Computation of Correlated Equilibrium with Global-Optimal Expected Social Welfare

In this paper, we propose an algorithm which computes the correlated equilibrium with global-optimal (i.e., maximum) expected social welfare for single stage polynomial games. We first derive tractable primal/dual semidefinite programming (SDP) relaxations for an infinite-dimensional formulation of correlated equilibria. We give an asymptotic convergence proof, which ensures solving the sequence of relaxations leads to solutions that converge to the correlated equilibrium with the highest expected social welfare. Finally, we give a dedicated sequential SDP algorithm and demonstrate it in a wireless application with numerical results.     

最大期望收益与最小期望损失决策一致性条件

本首先建立了条件收益值与条件损失值之间的关系，其次在理想期望概念的基础上建立了期望收益与期望损失之间的关系。然后给出了依据最大期望收益准则与最小期望损失准则决策一致性条件。     

关于图的最大亏格的下界

主要考虑2-边和3-边连通图的最大亏格下界情形,推广了J.Chen等(1996)的主要结果,证明了     

Random Planar Graphs with Bounds on the Maximum and Minimum Degrees

Let P _n,d,D denote the graph taken uniformly at random from the set of all labelled planar graphs on {1, 2, . . . , n} with minimum degree at least d(n) and maximum degree at most D(n). We use counting arguments to investigate the probability that P _n,d,D will contain given components and subgraphs, showing exactly when this is bounded away from 0 and 1 as n → ∞.     

A Note on Bounds for the Supremum Metric for Discrete Random Variables

For positive or negative integer-valued random variables X and Y with finite second moments the inequality sup \documentclass{article}\pagestyle{empty}\begin{document}$ \mathop {\sup }\limits_n |\Pr \{ X \le n\} - \Pr \{ Y \le n\} |\, \le \,|EX - EY| + \frac{1}{2}(EX(EX - 1) + (EY(Y - 1)) $\end{document} is established by elementary manipulation, and shown to be tight. Use of generating functions and an inversion formula yields the larger bound with 1/2 replaced by 2/π.     

Bounds for the Concentration of Asymptotically Normal Statistics

Let X₁,..., X _n be independent, not necessarily identically distributed random variables. An optimal bound is derived for the concentration function of an arbitrary real-valued statistic T = T (X ₁,...,X _n ) for which ET² < . Applications are given for Wilcoxon"s rank-sum statistic, U-statistics, Student"s statistic, the two-sample Student statistic and linear regression.     

On the Minimum and Maximum of Bivariate Lognormal Random Variables

Assume that (X,Y) is a bivariate lognormal vector. Let u = ln(X) and v = ln(Y). Then (u, v) is normally distributed. This note examines the effects of the distribution parameters of (u, v) on the first two moments of the order statistics of (X,Y). AMS 2000 Subject Classification Primary—62G30     

Tight Lower Bounds on the Size of a Maximum Matching in a Regular Graph

In this paper we study tight lower bounds on the size of a maximum matching in a regular graph. For k ≥3, let G be a connected k-regular graph of order n and let α′(G) be the size of a maximum matching in G. We show that if k is even, then , while if k is odd, then . We show that both bounds are tight. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Upper and Lower Bounds on Maximum Nonlinearity of n-input m-output Boolean Function

The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions.