Diffusion approximation for a heavily loaded multi-user wireless communication system with cooperation

A cellular wireless communication system in which data is transmitted to multiple users over a common channel is considered. When the base stations in this system can cooperate with each other, the link from the base stations to the users can be considered a multi-user multiple-input multiple-output (MIMO) downlink system. For such a system, it is known from information theory that the total rate of transmission can be enhanced by cooperation. The channel is assumed to be fixed for all transmissions over the period of interest and the ratio of anticipated average arrival rates for the users, also known as the relative traffic rate, is fixed. A packet-based model is considered where data for each user is queued at the transmit end. We consider a simple policy which, under Markovian assumptions, is known to be throughput-optimal for this coupled queueing system. Since an exact expression for the performance of this policy is not available, as a measure of performance, we establish a heavy traffic diffusion approximation. To arrive at this diffusion approximation, we use two key properties of the policy; we posit the first property as a reasonable manifestation of cooperation, and the second property follows from coordinate convexity of the capacity region. The diffusion process is a semimartingale reflecting Brownian motion (SRBM) living in the positive orthant of N-dimensional space (where N is the number of users). This SRBM has one direction of reflection associated with each of the 2 ^N −1 boundary faces, but show that, in fact, only those directions associated with the (N−1)-dimensional boundary faces matter for the heavy traffic limit. The latter is likely of independent theoretical interest.     

Occupancy with two types of balls

The classical occupancy problem is extended to the case where two types of balls are thrown. In particular, the probability that no urn contains both types of balls is studied. This is a birthday problem in two groups of boys and girls to consider the coincidence of a boy's and a girl's birthday. Let N ₁ and N ₂ denote the numbers of balls of each type thrown one by one when the first collision between the two types occurs in one of m urns. Then N ₁ N ₂/m is asymptotically exponentially distributed as m tends to infinity.This problem is related to the security evaluation of authentication procedures in electronic message communication.     

The conditioning of the stiffness matrix for certain elements approximating the incompressibility condition in fluid dynamics

Summary In order to solve the Stokes equations numerically, Crouzeix and Raviart introduced elements satisfying a discrete divergence condition. For the two dimensional case and uniform triangulations it is shown, that using the standard basis functions, the conditioning of the stiffness matrix is of orderN ², whereN is the dimension of the corresponding finite element space. Hierarchical bases are introduced which give a condition number of orderN log(N)³.     

Quasi-Exactly Solvable Generalizations of Calogero–Sutherland Models

A generalization of the procedures for constructing quasi-exactly solvable models with one degree of freedom to (quasi-)exactly solvable models of N particles on a line allows deriving many well-known models in the framework of a new approach that does not use root systems. In particular, a BC _N elliptic Calogero–Sutherland model is found among the quasi-exactly solvable models. For certain values of the paramaters of this model, we can explicitly calculate the ground state and the lowest excitations.     

A Bayesian approach to a sequential three‐decision problem: Voting and the uses of information in electoral choice*

This paper investigates a situation of decision‐making under risk in which an individual must select one of three actions. Substantively, an electoral example in which a citizen must decide how and whether to vote in a two‐candidate election is used to illustrate the argument. Only the value of the consequences of one action, which is to abstain from voting, is known. The expected values of voting for either candidate must be estimated based upon a sample of information. Specifically, we are interested in how one may decide when to stop gathering information and the behavioral consequences of that choice for the voting decision. The dependence of the voting decision on the original ambiguity and magnitude of the expected utilities and on the costs of information is also explored.     

Randomization time for the overhand shuffle

This paper analyzes repeated shuffling of a deck ofN cards. The measure studied is a model for the popularoverhand shuffle introduced by Aldous and Diaconis. It is shown that convergence to the uniform distribution requires at least orderN ² shuffles, and that orderN ² log(N) shuffles suffice. For a 52-card deck, more than 1000 shuffles are needed.     

Weighted compound integration rules with higher order convergence for all N

Quasi-Monte Carlo integration rules, which are equal-weight sample averages of function values, have been popular for approximating multivariate integrals due to their superior convergence rate of order close to 1/N or better, compared to the order 1/?N1/\sqrt{N} of simple Monte Carlo algorithms. For practical applications, it is desirable to be able to increase the total number of sampling points N one or several at a time until a desired accuracy is met, while keeping all existing evaluations. We show that although a convergence rate of order close to 1/N can be achieved for all values of N (e.g., by using a good lattice sequence), it is impossible to get better than order 1/N convergence for all values of N by adding equally-weighted sampling points in this manner. We then prove that a convergence of order N ^− α for α > 1 can be achieved by weighting the sampling points, that is, by using a weighted compound integration rule. We apply our theory to lattice sequences and present some numerical results. The same theory also applies to digital sequences.     

Transitive permutation groups and equipotent voting rules

Let F a two-alternative voting rule and G_F the subgroup of permutations of the voters under which F is invariant. Group theoretic properties of G_F provide information about the voting rule F. In particular, sets of imprimitivity of G_F describe the ‘committee decomposition’ structure of F and permutation group transitivity of G_F (equipotency) is shown to be closely connected with equal distribution of power among the voters. If equipotency replaces anonymity in the hypotheses of May's theorem, voting rules other than simple majority are possible. By combining equipotency with two additional social choice conditions a new characterization of simple majority rule is obtained. Equipotency is proposed as an important alternative to the more restrictive anonymity as a fairness criterion in social choice.     

Accusation probabilities in Tardos codes: beyond the Gaussian approximation

We study the probability distribution of user accusations in the q-ary Tardos fingerprinting system under the Marking Assumption, in the restricted digit model. In particular, we look at the applicability of the so-called Gaussian approximation, which states that accusation probabilities tend to the normal distribution when the fingerprinting code is long. We introduce a novel parametrization of the attack strategy which enables a significant speedup of numerical evaluations. We set up a method, based on power series expansions, to systematically compute the probability of accusing innocent users. The ‘small parameter’ in the power series is 1/m, where m is the code length. We use our method to semi-analytically study the performance of the Tardos code against majority voting and interleaving attacks. The bias function ‘shape’ parameter k{{\kappa}} strongly influences the distance between the actual probabilities and the asymptotic Gaussian curve. The impact on the collusion-resilience of the code is shown. For some realistic parameter values, the false accusation probability is even lower than the Gaussian approximation predicts.     

Heights of representative systems

Representative systems are hierarchical aggregation schemes that are applicable in social choice theory, multiattribute decision making, and in the study of three-valued logics. For example, many procedures for voting on issues—including simple majority voting and weighted voting—can be characterized as representative system. Such systems also include procedures in which vote outcomes of constituencies are treated as votes in a higher level of an election system. The general form of a representative system consists of a “supreme council” which aggregates vote outcomes of secondary councils, which in turn aggregate vote outcomes of tertiary councils, and so forth.An n-variable representative system maps n-tuples of 1's, 0's and ?1's into {1,0,?1} through a nested hierarchy of sign functions. The height of a representative system is the fewest number of hierarchical levels that are needed to characterize the system. The height μ(n) of all n-variable representative systems is the largest height of such systems. It was shown previously that μ(n) ? n ? 1 for all positive integers n and that μ(n) = n ? 1 for n from 1 to 4 inclusive. The present paper proves that μ(5) = μ(6) = 4 and that μ(n) ? ?2 for all n ? 6. The height function μ is known to be unbounded.     

Block plan for a fractional 2 m factorial design derived from a 2 r factorial design

Summary For a given fractional 2 ^m factorial (2 ^m -FF) designT, the constitution of a block plan to divideT intok (2 ^r−1<k≦2 ^r ) blocks withr block factors each at two levels is proposed and investigated. The well-known three norms of the confounding matrix are used as measures for determining a “good” block plan. Some theorems concerning the constitution of a block plan are derived for a 2 ^m -FF design of odd or even resolution. Two norms which may be preferred over the other norm are slightly modified. For each value ofN assemblies with 11≦N≦26, optimum block plans fork=2 blocks with block sizes [N/2] andN−[N/2] minimizing the two norms are presented forA-optimal balanced 2⁴-FF designs of resolutionV given by Srivastava and Chopra (Technometrics,13, 257–269).     

N-dimensional geometries generated by hypercomplex numbers

The geometries in N-dimensional Euclidean spaces can be described by Clifford algebras that were introduced as extensions of complex numbers. These applications are due to the fact that the Euclidean invariant (the distance between two points) is the same as the one of Clifford numbers. In this paper we consider the more general extension of complex numbers due to their group properties (hypercomplex systems), and we introduce the N-dimensional geometries associated with these systems. For N > 2 these geometries are different from the N-dimensional Euclidean geometries; then their investigation could open new applications. Moreover for the commutative systems the differential calculus does exist and this property allows one to define the functions of hypercomplex variable that can be used for studying some partial differential equations as well as the non-flat N-dimensional spaces. This last property can be relevant in general relativity and in field theories.     

On minimal disjoint degenerations of modules over tame path algebras

For representations of tame quivers the degenerations are controlled by the dimensions of various homomorphism spaces. Furthermore, there is no proper degeneration to an indecomposable. Therefore, up to common direct summands, any minimal degeneration from M to N is induced by a short exact sequence 0→U→M→V→0 with indecomposable ends that add up to N. We study these ‘building blocs’ of degenerations and we prove that the codimensions are bounded by two. Therefore, a quiver is Dynkin resp. Euclidean resp. wild iff the codimension of the building blocs is one resp. bounded by two resp. unbounded. We explain also that for tame quivers the complete classification of all the building blocs is a finite problem that can be solved with the help of a computer.     

On summability of eigenfunction expansions of piecewise smooth functions

We consider two forms of eigenfunction expansions associated with an arbitrary elliptic differential operator with constant coefficients and order m, that is the multiple Fourier series and integrals. For the multiple Fourier integrals, we prove the convergence of the Riesz means of order s?>?(N???3)/2 of piecewise smooth functions of N?≥?2 variables. The same result is proved in the case of the N?≥?3 dimensional multiple Fourier series.     

Rigidity of H–type groups

On H–type groups N the left invariant horizontal vector fields span a subbundle of the tangent bundle, called the horizontal bundle HN. Generalized contact mappings f on N are smooth mappings which preserve HN. The question is: how many such mappings exist? In the case of the Heisenberg group these are the contact mappings in the classical sense and they exist in abundance. In this paper it is shown that if the dimension of the center of N is at least three, then the generalized contact mappings are in the automorphism group of a finite dimensional Lie algebra g. The elements in are the infinitesimal generators of local one parameter subgroups of generalized contact transformations. Rigidity is defined as the property that is finite dimensional. For the case of the complexified Heisenberg group, i.e. the case when the dimension of the center of N is two, it has been shown [RR] that g is infinite dimensional. Received January 4, 2000; in final form March 20, 2000 / Published online April 12, 2001     

Selection from poisson processes

Summary There are givenk Poisson processes with mean arrival times 1/λ₁,...1/λ _k . Let λ_[1]≦λ_[2]≦...≦λ_[k] denote the ordered set of values λ₁...,λ_[k]. We consider three procedures for selecting the process corresponding to λ_[k]. The processes are observed until there areN arrivals from any of the given processes, when the processes are observed continuously, or until there are at leastN arrivals, when the processes are observed at successive intervals of time whereN is a pre-determined positive integer. In the continuous case, the process for which theNth arrival time is shortest, is selected. In the discrete case, the selection involves certain randomization. Given (λ_[k]/λ_[k-1])≧0>1, it is shown that the probability of a correct selection (Pcs) is minimized whenθλ_[1]=θλ_[2]=...=θλ_[k-1]=θλ_[k]=θλ, say. The Pcs for this configuration is independent of λ for two of the given procedures, and monotone increasing in λ for the third. The value ofN is determined by a lower bound placed on the value of the Pcs. The problem of selecting from given Poisson processes for the discrete case is related to the problem of selecting from given Poisson populations. An application of the given procedures to a problem of selecting the “most probable event” from a multinomial population, is considered.     

On the regularity of spherically symmetric wave maps

Wave maps are critical points U: M → N of the Lagrangian ??[U] = ∞_M ‖dU‖², where M is an Einsteinian manifold and N a Riemannian one. For the case M = ?^2,1 and U a spherically symmetric map, it is shown that the solution to the Cauchy problem for U with smooth initial data of arbitrary size is smooth for all time, provided the target manifold N satisfies the two conditions that: (1) it is either compact or there exists an orthonormal frame of smooth vectorfields on N whose structure functions are bounded; and (2) there are two constants c and C such that the smallest eigenvalue λ and the largest eigenvalue λ of the second fundamental form k_AB of any geodesic sphere Σ(p, s) of radius s centered at p ? N satisfy sλ ≧ c and s A ≦ C(1 + s). This is proved by first analyzing the energy-momentum tensor and using the second condition to show that near the first possible singularity, the energy of the solution cannot concentrate, and hence is small. One then proves that for targets satisfying the first condition, initial data of small energy imply global regularity of the solution. © 1993 John Wiley & Sons, Inc.     

Asymptotic modelling of conductive thin sheets

We derive and analyse models which reduce conducting sheets of a small thickness ε in two dimensions to an interface and approximate their shielding behaviour by conditions on this interface. For this we consider a model problem with a conductivity scaled reciprocal to the thickness ε, which leads to a nontrivial limit solution for ε → 0. The functions of the expansion are defined hierarchically, i.e. order by order. Our analysis shows that for smooth sheets the models are well defined for any order and have optimal convergence meaning that the H ¹-modelling error for an expansion with N terms is bounded by O(ε ^N+1) in the exterior of the sheet and by O(ε ^N+1/2) in its interior. We explicitly specify the models of order zero, one and two. Numerical experiments for sheets with varying curvature validate the theoretical results.     

A lower bound for the r -order of a matrix modulo N

For a positive integer N, we define the N-rank of a non singular integer d × d matrix A to be the maximum integer r such that there exists a minor of order r whose determinant is not divisible by N. Given a positive integer r, we study the growth of the minimum integer k, such that A ^k − I has N-rank at most r, as a function of N. We show that this integer k goes to infinity faster than log N if and only if for every eigenvalue λ which is not a root of unity, the sum of the dimensions of the eigenspaces relative to eigenvalues which are multiplicatively dependent with λ and are not roots of unity, plus the dimensions of the eigenspaces relative to eigenvalues which are roots of unity, does not exceed d − r − 1. This result will be applied to recover a recent theorem of Luca and Shparlinski [6] which states that the group of rational points of an ordinary elliptic curve E over a finite field with q ⁿ elements is almost cyclic, in a sense to be defined, when n goes to infinity. We will also extend this result to the product of two elliptic curves over a finite field and show that the orders of the groups of \Bbb F_qⁿ-{\Bbb F}_{q^n}- rational points of two non isogenous elliptic curves are almost coprime when n approaches infinity.     

Universal Overconvergence of Polynomial Expansions of Harmonic Functions

For each compact subset K of ^N let (K) denote the space of functions that are harmonic on some neighbourhood of K. The space (K) is equipped with the topology of uniform convergence on K. Let Ω be an open subset of ^N such that 0Ω and ^N\Ω is connected. It is shown that there exists a series ∑H_n, where H_n is a homogeneous harmonic polynomial of degree n on ^N, such that (i) ∑H_n converges on some ball of centre 0 to a function that is continuous on Ω and harmonic on Ω, (ii) the partial sums of ∑H_n are dense in (K) for every compact subset K of ^N\Ω with connected complement. Some refinements are given and our results are compared with an analogous theorem concerning overconvergence of power series.