On a new class of multiplicative pseudo-random number generators

In the computing literature, there are few detailed analytical studies of the global statistical characteristics of a class of multiplicative pseudo-random number generators.We comment briefly on normal numbers and study analytically the approximately uniform discrete distribution or (j,)-normality in the sense of Besicovitch for complete periods of fractional parts {x _{0 1} ⁱ /p} on [0, 1] fori=0, 1,..., (p–1)p^–1–1, i.e. in current terminology, generators given byx _{n+1 1} x _n mod p wheren=0, 1,..., (p–1)p ^–1–1,p is any odd prime, (x ₀,p)=1, ₁ is a primitive root modp ², and 1 is any positive integer.We derive the expectationsE(X, ),E(X ², ),E(X _nX_n+k); the varianceV(X, ), and the serial correlation coefficient k. By means of Dedekind sums and some results of H. Rademacher, we investigate the asymptotic properties of k for various lagsk and integers 1 and give numerical illustrations. For the frequently used case =1, we find comparable results to estimates of Coveyou and Jansson as well as a mathematical demonstration of a so-called rule of thumb related to the choice of ₁ for small k.Due to the number of parameters in this class of generators, it may be possible to obtain increased control over the statistical behavior of these pseudo-random sequences both analytically as well as computationally.     

Two Convergence Problems for Monotone Sequences

Eight measures of rate of convergence of monotone sequences of real numbers have been proposed and discussed in a paper by Beyer, Ebanks, and Qualls (Acta Appl. Math. 20 (1990), 267–284). These rates arose in discussions of dynamical systems. In the comparisons of these rates, two problems remained. A complete answer is given to one of the problems and a partial answer is given to the other problem.     

Discrete optimization in public rail transport

Many problems arising in traffic planning can be modelled and solved using discrete optimization. We will focus on recent developments which were applied to large scale real world instances. Most railroad companies apply a hierarchically structured planning process. Starting with the definition of the underlying network used for transport one has to decide which infrastructural improvements are necessary. Usually, the rail system is periodically scheduled. A fundamental base of the schedule are the lines connecting several stations with a fixed frequency. Possible objectives for the construction of the line plan may be the minimization of the total cost or the maximization of the passengers’s comfort satisfying certain regulations. After the lines of the system are fixed, the train schedule can be determined. A criterion for the quality of a schedule is the total transit time of the passengers including the waiting time which should be minimized satisfying some operational constraints. For each trip of the schedule a train consisting of a locomotive and some carriages is needed for service. The assignment of rolling stock to schedule trips has to satisfy operational requirements. A comprehensible objective is to minimize the total cost. After all strategic and tactical planning the schedule has to be realized. Several external influences, for example delayed trains, force the dispatcher to recompute parts of the schedule on-line. A Web page with examples quoted in this survey can be found at http://www.math.tu-bs.de/mo/ismp.html.     

有限个渐近伪压缩映射近迫点序列的收敛性

研究了Banach空间中有限个渐近伪压缩映射近迫点序列的收敛性问题,此结果推广了以前的结论.     

The Fermi-sea-like limit of the composite fermion wave function

The experimentally observed filling factors of the fractional quantum Hall effect can be described in terms of the composite fermion wave function of the Jastrow-Slater form [0pt] fully projected into the lowest Landau level. The Slater determinant of the above composite fermion wave function represents the filled Landau levels of composite fermions evaluated at the corresponding reduced magnetic field. For a system of fermions studied in the thermodynamic limit, we prove that in the even-denominator-filled state limit (when the number of filled Landau levels of composite fermions becomes infinite), the above composite fermion wave function exactly transforms into the Rezayi-Read Fermi-sea-like wave function [0pt] constructed by attaching 2m flux quanta to the Slater determinant of two-dimensional free fermions at the density corresponding to that filling. We study the composite fermion wave function and its evolution into the Fermi-sea-like wave function for a range of filling factors very close to the even-denominator-filled state. Received 19 March 1999     

Conditions for the convergence in distribution of maxima of stationary normal processes

The asymptotic distribution of the maximum M_n=max_1?t?nξ_t in a stationary normal sequence ξ₁,ξ,… depends on the correlation r_t between ξ₀ and ξ_t. It is well known that if r_t log t → 0 as t → ∞ or if Σr²_t<∞, then the limiting distribution is the same as for a sequence of independent normal variables. Here it is shown that this also follows from a weaker condition, which only puts a restriction on the number of t-values for which rt log t islarge. The condition gives some insight into what is essential for this asymptotic behaviour of maxima. Similar results are obtained for a stationary normal process in continuous time.     

Classification of Dantzig–Wolfe reformulations for binary mixed integer programming problems

In this note, we provide a classification of Dantzig–Wolfe reformulations for Binary Mixed Integer Programming Problems. We specifically focus on modeling the binary conditions in the convexification approach to the Dantzig–Wolfe decomposition. For a general Binary Mixed Integer Programming problem, an extreme point of the overall problem does not necessarily correspond to an extreme point of the subproblem. Therefore, the binary conditions cannot in general be imposed on the new master problem variables but must be imposed on the original binary variables. In some cases, however, it is possible to impose the binary restrictions directly on the new master problem variables. The issue of imposing binary conditions on the original variables versus the master problem variables has not been discussed systematically for MIP problems in general in the literature and most of the research has been focused on the pure binary case. The classification indicates in which cases you can, and cannot, impose binary conditions on the new master problem variables.     

An alignment-free measure based on physicochemical properties of amino acids for protein sequence comparison

Sequence comparison is an important topic in bioinformatics. With the exponential increase of biological sequences, the traditional protein sequence comparison methods — the alignment methods become limited, so the alignment-free methods are widely proposed in the past two decades. In this paper, we considered not only the six typical physicochemical properties of amino acids, but also their frequency and positional distribution. A 51-dimensional vector was obtained to describe the protein sequence. We got a pairwise distance matrix by computing the standardized Euclidean distance, and discriminant analysis and phylogenetic analysis can be made. The results on the Influenza A virus and ND5 datasets indicate that our method is accurate and efficient for classifying proteins and inferring the phylogeny of species.     

A benchmark of optimally folded protein structures using integer programming and the 3D-HP-SC model

The Protein Structure Prediction (PSP) problem comprises, among other issues, forecasting the three-dimensional native structure of proteins using only their primary structure information. Most computational studies in this area use synthetic data instead of real biological data. However, the closer to the real-world, the more the impact of results and their applicability. This work presents 17 real protein sequences extracted from the Protein Data Bank for a benchmark to the PSP problem using the tri-dimensional Hydrophobic-Polar with Side-Chains model (3D-HP-SC). The native structure of these proteins was found by maximizing the number of hydrophobic contacts between the side-chains of amino acids. The problem was treated as an optimization problem and solved by means of an Integer Programming approach. Although the method optimally solves the problem, the processing time has an exponential trend. Therefore, due to computational limitations, the method is a proof-of-concept and it is not applicable to large sequences. For unknown sequences, an upper bound of the number of hydrophobic contacts (using this model) can be found, due to a linear relationship with the number of hydrophobic residues. The comparison between the predicted and the biological structures showed that the highest similarity between them was found with distance thresholds around 5.2–8.2 Å. Both the dataset and the programs developed will be freely available to foster further research in the area.     

On the counting function of the lattice profile of periodic sequences

The lattice profile analyzes the intrinsic structure of pseudorandom number sequences with applications in Monte Carlo methods and cryptology. In this paper, using the discrete Fourier transform for periodic sequences and the relation between the lattice profile and the linear complexity, we give general formulas for the expected value, variance, and counting function of the lattice profile of periodic sequences with fixed period. Moreover, we determine in a more explicit form the expected value, variance, and counting function of the lattice profile of periodic sequences for special values of the period.