Let π be a minimal Erdös-Szekeres permutation of 1, 2, ..., n2, and let ln,k be the length of the longest increasing subsequence in the segment (π(1), ..., π(k)). Under uniform measure we establish an exponentially decaying bound of the upper tail probability for ln,k, and as a consequence we obtain a complete convergence, which is an improvement of Romik’s recent result. We also give a precise lower exponential tail for ln,k. 相似文献
The Mallows measure on the symmetric group Sn is the probability measure such that each permutation has probability proportional to q raised to the power of the number of inversions, where q is a positive parameter and the number of inversions of π is equal to the number of pairs i<j such that πi>πj. We prove a weak law of large numbers for the length of the longest increasing subsequence for Mallows distributed random permutations, in the limit that n→∞ and q→1 in such a way that n(1?q) has a limit in R. 相似文献
We consider P(G is connected) when G is a graph with vertex set Z+ = {1,2, …}, and the edge between i and j is present with probability p(i, j) = min(λ h(i, j), 1) for certain functions h(i, j) homogeneous of degree -1. It is known that there is a critical value λc of λ such that . We show that the probability, at the critical point λc, that n1, and n2 are connected satisfies a power law, in the sense that for n2 ≧ nt ≧ 1 for any δ > 0 and certain constants c1 and c2. 相似文献
The paper gives a proof, valid for a large class of bounded domains, of the following compactness statements: Let G be a bounded domain, β be a tensor-valued function on G satisfying certain restrictions, and let {n} be a sequence of vector-valued functions on G where the L2-norms of {n}, {curl n}, and {div(β n)} are bounded, and where all n either satisfy x n = 0 or (β Fn) = 0 at the boundary ?G of G ( = normal to ?G): then {n} has a L2-convergent subsequence. The first boundary condition is satisfied by electric fields, the second one by magnetic fields at a perfectly conducting boundary ?G if β is interpreted as electric dielectricity ? or as magnetic permeability μ, respectively. These compactness statements are essential for the application of abstract scattering theory to the boundary value problem for Maxwell's equations. 相似文献
Let where In 1958, Vietoris proved that σn (x) is positive for all n ≥ 1 and x ∈ (0, π). We establish the following refinement. The inequalities hold for all natural numbers n and real numbers n ≥ 1 and x ∈ (0, π) if and only if 相似文献
We consider random PATRICIA trees constructed from n i.i.d. sequences of independent equiprobable bits. We study the height Hn (the maximal distance between the root and a leaf), and the minimal fill-up level Fn (the minimum distance between the root and a leaf). We give probabilistic proofs of . 相似文献
We consider the problem of the asymptotically best linear method of approximation in the metric of Ls[?π, π] of the set \(\tilde W_p^\alpha (1)\) of periodic functions with a bounded in Lp[?π, π] fractional derivative, by functions from \(\tilde W_p^\beta (M)\) ,β >α, for sufficiently large M, and the problem about the best approximation in Ls[?π, π] of the operator of differentiation on \(\tilde W_p^\alpha (1)\) by continuous linear operators whose norm (as operators from Lr[?π, π] into Lq[?π, π])does not exceed M. These problems are reduced to the approximation of an individual element in the space of multipliers, and this allows us to obtain estimates that are exact in the sense of the order. 相似文献
We consider the length L of the longest common subsequence of two randomly uniformly and independently chosen n character words over a k-ary alphabet. Subadditivity arguments yield that E[L]/n converges to a constant γk. We prove a conjecture of Sankoff and Mainville from the early 1980s claiming that as k→∞. 相似文献
If Rt is the position of the rightmost particle at time t in a one dimensional branching brownian motion, whore α is the inverse of the mean life time and m is the mean of the reproduction law. If Zt denotes the random point measure of particles living at time t, we get in the critical area {c = c0} The function u(t, x) = P(Rt > x) is studied as a solution of the K-P-P equation for some function f. Conditioned on non-extinction of the spatial tree in the c0-direction, a limit distribution is obtained and characterized. 相似文献