On the evolution of islands

Letn cells be arranged in a ring, or alternatively, in a row. Initially, all cells are unmarked. Sequentially, one of the unmarked cells is chosen at random and marked until, aftern steps, each cell is marked. After thekth cell has been marked the configuration of marked cells defines some number of islands: maximal sets of adjacent marked cells. Let ξ _k denote the random number of islands afterk cells have been marked. We give explicit expressions for moments of products of ξ _k ’s and for moments of products of 1/ξ _k ’s. These are used in a companion paper to prove that if a random graph on the natural number is made by drawing an edge betweeni≧1 andj>i with probabilityλ/j, then the graph is almost surely connected ifλ>1/4 and almost surely disconnected ifλ≦1/4.     

Monte Carlo generation of self-avoiding walks with fixed endpoints and fixed length

We propose a new class of dynamic Monte Carlo algorithms for generating self-avoiding walks uniformly from the ensemble with fixed endpoints and fixed length in any dimension, and prove that these algorithms are ergodic in all cases. We also prove the ergodicity of a variant of the pivot algorithm.     

The advantage of capitalism vs. socialism depends on the criterion

The talk given by the second author, L. A. Shepp, at the Linnik symposium, St.Petersburg, April 2005. We consider two distinct government tax policies towards companies: the republican policy gives tax breaks to the richer companies, while the democratic policy would perhaps give breaks to the weaker companies in hopes to keep them alive and so reduce unemployment. Which policy is better? We show that this depends on the optimization criterion, at least for the case of two companies, which is all that we can handle, in the stated mathematical formulation of the question.     

The set of real numbers left uncovered by random covering intervals

Summary Random covering intervals are placed on the real line in a Poisson manner. Lebesgue measure governs their (random) locations and an arbitrary measure μ governs their (random) lengths. The uncovered set is a regenerative set in the sense of Hoffmann-J?rgensen's generalization of regenerative phenomena introduced by Kingman. Thus, as has previously been obtained by Mandelbrot, it is the closure of the image of a subordinator —one that is identified explicitly. Well-known facts about subordinators give Shepp's necessary and sufficient condition on μ for complete coverage and, when the coverage is not complete, a formula for the Hausdorff dimension of the uncovered set. The method does not seem to be applicable when the covering is not done in a Poisson manner or if the line is replaced by the plane or higher dimensional space. This work does not represent a collaboration among the three authors, but rather is an outgrowth of a discovery that the first author on one hand and the second and third authors on the other hand had proved identical results via similar methods. Based on part of the first author's PhD dissertation written under Kenneth J. Hochberg at Case Western Reserve University. Research partially supported by National Science Foundation Grant MCS 78-01168.     

Connectedness of certain random graphs

L. Dubins conjectured in 1984 that the graph on vertices {1, 2, 3, ...} where an edge is drawn between verticesi andj with probabilityp _ij=λ/max(i, j) independently for each pairi andj is a.s. connected forλ=1. S. Kalikow and B. Weiss proved that the graph is a.s. connected for anyλ>1. We prove Dubin’s conjecture and show that the graph is a.s. connected for anyλ>1/4. We give a proof based on a recent combinatorial result that forλ≦1/4 the graph is a.s. disconnected. This was already proved forλ<1/4 by Kalikow and Weiss. Thusλ=1/4 is the critical value for connectedness, which is surprising since it was believed that the critical value is atλ=1.     

Plasma isotope separation methods

Six major types of isotope separation methods which involve plasma phenomena are discussed. These methods are: plasma centrifuge, AVLIS (atomic vapor laser isotope separation), ion wave, ICR (ion cyclotron resonance), calutron, and gas discharge. The plasma phenomena in these major categories are described. An attempt is made to include enough references so that a more detailed study or evaluation of a particular method could readily be pursued. A brief discussion of isotope separation using mass balance concepts is also included     

The Sperner Capacity of Linear and Nonlinear Codes for the Cyclic Triangle

Shannon introduced the concept of zero-error capacity of a discrete memoryless channel. The channel determines an undirected graph on the symbol alphabet, where adjacency means that symbols cannot be confused at the receiver. The zero-error or Shannon capacity is an invariant of this graph. Gargano, Körner, and Vaccaro have recently extended the concept of Shannon capacity to directed graphs. Their generalization of Shannon capacity is called Sperner capacity. We resolve a problem posed by these authors by giving the first example (the two orientations of the triangle) of a graph where the Sperner capacity depends on the orientations of the edges. Sperner capacity seems to be achieved by nonlinear codes, whereas Shannon capacity seems to be attainable by linear codes. In particular, linear codes do not achieve Sperner capacity for the cyclic triangle. We use Fourier analysis or linear programming to obtain the best upper bounds for linear codes. The bounds for unrestricted codes are obtained from rank arguments, eigenvalue interlacing inequalities and polynomial algebra. The statement of the cyclic q-gon problem is very simple: what is the maximum size N _q(n) of a subset S _n of {0, 1, \(\ldots\) , q?1} ⁿ with the property that for every pair of distinct vectors x = (x _i), y = (y _i) \(\in \) S _n, we have x _j ?y _j ≡ 1(mod q) for some j? For q = 3 (the cyclic triangle), we show N ₃(n)?2 ⁿ . If however S _n is a subgroup, then we give a simple proof that \(\left| {S_n } \right| \leqslant \sqrt 3 ^n \) .     

Strong Decomposition of Random Variables

A random variable X is called strongly decomposable into (strong) components Y,Z, if X=Y+Z where Y=φ(X), Z=X−φ(X) are independent nondegenerate random variables and φ is a Borel function. Examples of decomposable and indecomposable random variables are given. It is proved that at least one of the strong components Y and Z of any random variable X is singular. A necessary and sufficient condition is given for a discrete random variable X to be strongly decomposable. Phenomena arising when φ is not Borel are discussed. The Fisher information (on a location parameter) in a strongly decomposable X is necessarily infinite.