Exact simulation of the stationary distribution of the FIFO M/G/c queue: the general case for <Emphasis Type="Italic">ρ</Emphasis><<Emphasis Type="Italic">c</Emphasis>

We present an exact simulation algorithm for the stationary distribution of customer delay for FIFO M/G/c queues in which ρ=λ/μ<c. In Sigman (J. Appl. Probab. 48A:209–216, 2011) an exact simulation algorithm was presented but only under the strong condition that ρ<1 (super stable case). We only assume that the service-time distribution G(x)=P(S≤x), x≥0, with mean 0<E(S)=1/μ<∞, and its corresponding equilibrium distribution $G_{e}(x)=\mu\int_{0}^{x} P(S>y)\,dy$G_{e}(x)=\mu\int_{0}^{x} P(S>y)\,dy are such that samples of them can be simulated. Unlike the methods used in Sigman (J. Appl. Probab. 48A:209–216, 2011) involving coupling from the past, here we use different methods involving discrete-time processes and basic regenerative simulation, in which, as regeneration points, we use return visits to state 0 of a corresponding random assignment (RA) model which serves as a sample-path upper bound.     

Arithmetic of Finite Ordered Sets: Cancellation of Exponents,II

Garrett Birkhoff conjectured in 1942 that when A, B, P are finite posets satisfying A ^PB ^P, then AB. We show that this is true. Further, we introduce an operation C(A ^B), related to Garrett Birkhoff's exponentiation, and determine the structure of the algebra of isomorphism types of finite posets under the operations induced by A+B, A×B, and C(A ^B). Every finite +-indecomposable and ×-indecomposable poset A of more than one element is expressible for unique (up to isomorphism) E and P as AC(E ^P) where P is connected and E is indecomposable for all three operations.     

Equivariant Schubert calculus

We describe T-equivariant Schubert calculus on G(k,n), T being an n-dimensional torus, through derivations on the exterior algebra of a free A-module of rank n, where A is the T-equivariant cohomology of a point. In particular, T-equivariant Pieri’s formulas will be determined, answering a question raised by Lakshmibai, Raghavan and Sankaran (Equivariant Giambelli and determinantal restriction formulas for the Grassmannian, Pure Appl. Math. Quart. 2 (2006), 699–717).     

Jensen’s functional equation on the symmetric group S<Subscript>n</Subscript>

Two natural extensions of Jensen’s functional equation on the real line are the equations f(xy) + f(xy ⁻¹) =  2f(x) and f(xy) + f(y ⁻¹ x) =  2f(x), where f is a map from a multiplicative group G into an abelian additive group H. In a series of papers (see Ng in Aequationes Math 39:85–99, 1990; Ng in Aequationes Math 58:311–320, 1999; Ng in Aequationes Math 62:143–159, 2001), Ng solved these functional equations for the case where G is a free group and the linear group GL_n(R), R=\mathbbZ,\mathbbR{{GL_n(R), R=\mathbb{Z},\mathbb{R}}} , is a quadratically closed field or a finite field. He also mentioned, without a detailed proof, in the above papers and in (see Ng in Aequationes Math 70:131–153, 2005) that when G is the symmetric group S _n , the group of all solutions of these functional equations coincides with the group of all homomorphisms from (S _n , ·) to (H, + ). The aim of this paper is to give an elementary and direct proof of this fact.     

Anchor Maps and Stable Modules in Depth Two

An algebra extension A ∣ B is right depth two if its tensor-square is in the Dress category . We consider necessary conditions for right, similarly left, D2 extensions in terms of partial A-invariance of two-sided ideals in A contracted to the centralizer. Finite dimensional algebras extending central simple algebras are shown to be depth two. Following P. Xu, left and right bialgebroids over a base algebra R may be defined in terms of anchor maps, or representations on R. The anchor maps for the bialgebroids and over the centralizer R = C _A (B) are the modules _S R and R _T studied in Kadison (J. Alg. & Appl., 2005, preprint), Kadison (Contemp. Math., 391: 149–156, 2005), and Kadison and Külshammer (Commun. Algebra, 34: 3103–3122, 2006), which provide information about the bialgebroids and the extension (Kadison, Bull. Belg. Math. Soc. Simon Stevin, 12: 275–293, 2005). The anchor maps for the Hopf algebroids in Khalkhali and Rangipour (Lett. Math. Phys., 70: 259–272, 2004) and Kadison (2005, preprint) reverse the order of right multiplication and action by a Hopf algebra element, and lift to the isomorphism in Van Oystaeyen and Panaite (Appl. Categ. Struct., 2006, in press). We sketch a theory of stable A-modules and their endomorphism rings and generalize the smash product decomposition in Kadison (Proc. Am. Math. Soc., 131: 2993–3002, 2003 Prop. 1.1) to any A-module. We observe that Schneider’s coGalois theory in Schneider (Isr. J. Math., 72: 167–195, 1990) provides examples of codepth two, such as the quotient epimorphism of a finite dimensional normal Hopf subalgebra. A homomorphism of finite dimensional coalgebras is codepth two if and only if its dual homomorphism of algebras is depth two.      

Hyperinvariant subspaces for some <Emphasis Type="Italic">B</Emphasis>–circular operators

We show that if A is a Hilbert–space operator, then the set of all projections onto hyperinvariant subspaces of A, which is contained in the von Neumann algebra υN(A) that is generated by A, is independent of the representation of υ N(A), thought of as an abstract W^*–algebra. We modify a technique of Foias, Ko, Jung and Pearcy to get a method for finding nontrivial hyperinvariant subspaces of certain operators in finite von Neumann algebras. We introduce the B–circular operators as a special case of Speicher's B–Gaussian operators in free probability theory, and we prove several results about a B–circular operator z, including formulas for the B–valued Cauchy– and R–transforms of z^*z. We show that a large class of L^∞([0,1])–circular operators in finite von Neumann algebras have nontrivial hyperinvariant subspaces, and that another large class of them can be embedded in the free group factor L(F₃). These results generalize some of what is known about the quasinilpotent DT–operator. Supported in part by NSF Grant DMS-0300336. with an Appendix by Gabriel Tucci     

Classification of Refinable Splines in ℝ d

A refinable spline in ℝ ^d is a compactly supported refinable function whose support can be decomposed into simplices such that the function is a polynomial on each simplex. The best-known refinable splines in ℝ ^d are the box splines. Refinable splines play a key role in many applications, such as numerical computation, approximation theory and computer-aided geometric design. Such functions have been classified in one dimension in Dai et al. (Appl. Comput. Harmon. Anal. 22(3), 374–381, 2007), Lawton et al. (Comput. Math. 3, 137–145, 1995). In higher dimensions Sun (J. Approx. Theory 86, 240–252, 1996) characterized those splines when the dilation matrices are of the form A=mI, where m∈ℤ and I is the identity matrix. For more general dilation matrices the problem becomes more complex. In this paper we give a complete classification of refinable splines in ℝ ^d for arbitrary dilation matrices A∈M _d (ℤ).     

Distances Between <Emphasis Type="Italic">σ</Emphasis>-Fields on a Probability Space

For a probability space (Ω,ℱ,P) and two sub-σ-fields we consider two natural distances: and . We investigate basic properties of these distances. In particular we show that if a distance (ρ or ) from ℬ to is small then there exists Z∈ℱ with small P(Z), such that for every B∈ℬ there exists such that B∖Z and A∖Z differ by a set of probability zero. This improves results of Neveu (Ann. Math. Stat. 43(4):1369–1371, [1972]), Jajte and Paszkiewicz (Probab. Math. Stat. 19(1):181–201, [1999]).      

A Φ-Entropy Contraction Inequality for Gaussian Vectors

A beautiful result of Sarmanov (Dokl. Akad. Nauk SSSR 121(1), 52–55, 1958) says that for a Gaussian vector (X,Y), \operatorname Var(\mathbb E[f(Y)|X]) ￡ r²\operatorname Var(f(Y))\operatorname {Var}(\mathbb {E}[f(Y)|X])\le \rho^{2}\operatorname {Var}(f(Y)) for all measurable functions f, where ρ is the (linear) correlation coefficient between X and Y. We generalize this result to a general Φ-entropy (a nonlinear version of his result) by means of a previous result of D. Chafai based on Bakry–Emery’s Γ ₂-technique and tensorization.     

Strong Limit Theorems for Weighted Sums of Negatively Associated Random Variables

In this paper, we establish strong laws for weighted sums of identically distributed negatively associated random variables. Marcinkiewicz-Zygmund’s strong law of large numbers is extended to weighted sums of negatively associated random variables. Furthermore, we investigate various limit properties of Cesàro’s and Riesz’s sums of negatively associated random variables. Some of the results in the i.i.d. setting, such as those in Jajte (Ann. Probab. 31(1), 409–412, 2003), Bai and Cheng (Stat. Probab. Lett. 46, 105–112, 2000), Li et al. (J. Theor. Probab. 8, 49–76, 1995) and Gut (Probab. Theory Relat. Fields 97, 169–178, 1993) are also improved and extended to the negatively associated setting.      

Leading coefficients of Kazhdan–Lusztig polynomials for Deodhar elements

We show that the leading coefficient of the Kazhdan–Lusztig polynomial P _x,w (q) known as μ(x,w) is always either 0 or 1 when w is a Deodhar element of a finite Weyl group. The Deodhar elements have previously been characterized using pattern avoidance in Billey and Warrington (J. Algebraic Combin. 13(2):111–136, [2001]) and Billey and Jones (Ann. Comb. [2008], to appear). In type A, these elements are precisely the 321-hexagon avoiding permutations. Using Deodhar’s algorithm (Deodhar in Geom. Dedicata 63(1):95–119, [1990]), we provide some combinatorial criteria to determine when μ(x,w)=1 for such permutations w. The author received support from NSF grants DMS-9983797 and DMS-0636297.     

On the Number of i.i.d. Samples Required to Observe All of the Balls in an Urn

Suppose an urn contains m distinct balls, numbered 1,...,m, and let τ denote the number of i.i.d. samples required to observe all of the balls in the urn. We generalize the partial fraction expansion type arguments used by Pólya (Z Angew Math Mech 10:96–97, 1930) for approximating \mathbbE(t)\mathbb{E}(\tau) in the case of fixed sample sizes to obtain an approximation of \mathbbE(t)\mathbb{E}(\tau) when the sample sizes are i.i.d. random variables. The approximation agrees with that of Sellke (Ann Appl Probab 5(1):294–309, 1995), who made use of Wald’s equation and a Markov chain coupling argument. We also derive a new approximation of \mathbbV(t)\mathbb{V}(\tau), provide an (improved) bound on the error in these approximations, derive a recurrence for \mathbbE(t)\mathbb{E}(\tau), give a new large deviation type result for tail probabilities, and look at some special cases.     

Limit Law of the Local Time for Brox’s Diffusion

We consider Brox’s model: a one-dimensional diffusion in a Brownian potential W. We show that the normalized local time process (L(t,m _log t +x)/t, x∈R), where m _log t is the bottom of the deepest valley reached by the process before time t, behaves asymptotically like a process which only depends on W. As a consequence, we get the weak convergence of the local time to a functional of two independent three-dimensional Bessel processes and thus the limit law of the supremum of the normalized local time. These results are discussed and compared to the discrete time and space case for which the same questions have been answered recently by Gantert, Peres, and Shi (Ann. Inst. Henri Poincaré, Probab. Stat. 46(2):525–536, 2010).     

The flatness properties of <Emphasis Type="Italic">S</Emphasis>-poset <Emphasis Type="Italic">A</Emphasis>(<Emphasis Type="Italic">I</Emphasis>) and Rees factor <Emphasis Type="Italic">S</Emphasis>-posets

Let S be a pomonoid and I a proper right ideal of S. In a previous paper, using the amalgamated coproduct A(I) of two copies of _S S over I, we were able to solve one of the problems posed in S. Bulman-Fleming et al. (Commun. Algebra 34:1291–1317, 2006). In the present paper, we investigate further flatness properties of A(I). We also solve another problem stated in the paper cited above. Namely, we determine the condition under which Rees factor S-posets have property (P _w ). Research supported by nwnu-kjcxgc-03-18.     

The negative cycles polyhedron and hardness of checking some polyhedral properties

Given a graph G=(V,E) and a weight function on the edges w:E→ℝ, we consider the polyhedron P(G,w) of negative-weight flows on G, and get a complete characterization of the vertices and extreme directions of P(G,w). Based on this characterization, and using a construction developed in Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008), we show that, unless P=NP, there is no output polynomial-time algorithm to generate all the vertices of a 0/1-polyhedron. This strengthens the NP-hardness result of Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes (Bussiech and Lübbecke in Comput. Geom., Theory Appl. 11(2):103–109, 1998). As further applications, we show that it is NP-hard to check if a given integral polyhedron is 0/1, or if a given polyhedron is half-integral. Finally, we also show that it is NP-hard to approximate the maximum support of a vertex of a polyhedron in ℝ ⁿ within a factor of 12/n.     

On r-recognition by prime graph of Bp(3) where p is an odd prime

Let G be a finite group. The prime graph Γ(G) of G is defined as follows. The vertices of Γ(G) are the primes dividing the order of G and two distinct vertices p and p′ are joined by an edge if there is an element in G of order pp′. We denote by k(Γ(G)) the number of isomorphism classes of finite groups H satisfying Γ(G) = Γ(H). Given a natural number r, a finite group G is called r-recognizable by prime graph if k(Γ(G)) =  r. In Shen et al. (Sib. Math. J. 51(2):244–254, 2010), it is proved that if p is an odd prime, then B _p (3) is recognizable by element orders. In this paper as the main result, we show that if G is a finite group such that Γ(G) = Γ(B _p (3)), where p > 3 is an odd prime, then G @ B_p(3){G\cong B_p(3)} or C _p (3). Also if Γ(G) = Γ(B ₃(3)), then G @ B₃(3), C₃(3), D₄(3){G\cong B_3(3), C_3(3), D_4(3)}, or G/O₂(G) @ Aut(²B₂(8)){G/O_2(G)\cong {\rm Aut}(^2B_2(8))}. As a corollary, the main result of the above paper is obtained.     

Three classes of smooth Banach submanifolds in B(E,F)

Let E, F be two Banach spaces, and B(E, F), Φ(E, F), SΦ(E, F) and R(E,F) be the bounded linear, Fredholm, semi-Frdholm and finite rank operators from E into F, respectively. In this paper, using the continuity characteristics of generalized inverses of operators under small perturbations, we prove the following result Let ∑ be any one of the following sets {T ∈ Φ(E, F) IndexT =const, and dim N(T) = const.}, {T ∈ SΦ(E, F) either dim N(T) = const. ＜ ∞ or codim R(T) = const.＜ ∞} and {T ∈ R(E, F) RankT =const.＜∞}. Then ∑ is a smooth submanifold of B(E, F) with the tangent space TA∑ = {B ∈ B(E,F) BN(A) (∪) R(A)} for any A ∈ ∑. The result is available for the further application to Thom's famous results on the transversility and the study of the infinite dimensional geometry.     

<Emphasis Type="Italic">P</Emphasis>-orderings of finite subsets of Dedekind domains

If R is a Dedekind domain, P a prime ideal of R and S⊆R a finite subset then a P-ordering of S, as introduced by M. Bhargava in (J. Reine Angew. Math. 490:101–127, 1997), is an ordering {a _i } _i=1 ^m of the elements of S with the property that, for each 1<i≤m, the choice of a _i minimizes the P-adic valuation of ∏ _j<i (s−a _j ) over elements s∈S. If S, S ^′ are two finite subsets of R of the same cardinality then a bijection φ:S→S ^′ is a P-ordering equivalence if it preserves P-orderings. In this paper we give upper and lower bounds for the number of distinct P-orderings a finite set can have in terms of its cardinality and give an upper bound on the number of P-ordering equivalence classes of a given cardinality.     

An interlacing theorem for matrices whose graph is a given tree

Let A and B be (n×n)-matrices. For an index set S ⊂ {1, …, n}, denote by A(S) the principal submatrix that lies in the rows and columns indexed by S. Denote by S′ the complement of S and define η(A, B) = det A(S) det B(S′), where the summation is over all subsets of {1, …, n} and, by convention, det A(∅) = det B(∅) = 1. C. R. Johnson conjectured that if A and B are Hermitian and A is positive semidefinite, then the polynomial η(λA,-B) has only real roots. G. Rublein and R. B. Bapat proved that this is true for n ⩽ 3. Bapat also proved this result for any n with the condition that both A and B are tridiagonal. In this paper, we generalize some little-known results concerning the characteristic polynomials and adjacency matrices of trees to matrices whose graph is a given tree and prove the conjecture for any n under the additional assumption that both A and B are matrices whose graph is a tree. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 10, No. 3, pp. 245–254, 2004.