First passage time problems arise in many fields, but few of them are explicitly solved. Motivated by an application to synchronization of clocks, this paper obtains the probability distribution for the first passage time for a Brownian motion with quadratic drift to exit from two constant barriers that are not necessarily symmetric. The expression for the distribution is explicit, consisting of elementary functions and functions that are characterized by Laplace transforms. Applications of first passage times are demonstrated in the context of synchronization.

In this paper, we introduce a mathematical framework for the characterization of network interference in wireless systems. We consider a network in which the interferers are scattered according to a spatial Poisson process and are operating asynchronously in a wireless environment subject to path loss, shadowing, and multipath fading. We start by determining the statistical distribution of the aggregate network interference. We then investigate four applications of the proposed model: 1) interference in cognitive radio networks; 2) interference in wireless packet networks; 3) spectrum of the aggregate radio-frequency emission of wireless networks; and 4) coexistence between ultrawideband and narrowband systems. Our framework accounts for all the essential physical parameters that affect network interference, such as the wireless propagation effects, the transmission technology, the spatial density of interferers, and the transmitted power of the interferers.

Consider a group of n men and n women, each ranking the members of the opposite sex as a potential marriage partner. A matching (marriage) of men and women is called stable if there is no pair (man, woman) who are not matched but prefer each other to their partners in the matching. It is known that, for every instance of the rankings, there is at least one stable matching and that there are instances with exponentially many stable matchings. Assume that the instance is chosen uniformly at random among all $(n!)^{2n}$ possibilities. In this case the likely number of stable matchings is known to be $n^{1/2-o(1)}$, with high probability, and of order $n\ln n$, with probability $0.84$ at least. In this paper we show that the average number of fixed pairs (man, woman), i.e., pairs common to all stable matchings, is asymptotic to $\ln^2 n$. More generally, the average number of women (men) with k stable husbands (wives) is asymptotic to $(\ln ^{k+1} n)/(k-1)!$.

Of the many important signaling events that take place on the surface of a mammalian cell, activation of signal transduction pathways via interactions of cell surface receptors is one of the most important. Evidence suggests that cell surface proteins are not as freely diffusible as implied by the classic fluid mosaic model and that their confinement to membrane domains is regulated. It is unknown whether these dynamic localization mechanisms function to enhance signal transduction activation rate or to minimize cross talk among pathways that share common intermediates. To determine which of these two possibilities is more likely, we derive an explicit equation for the rate at which cell surface membrane proteins interact based on a Brownian motion model in the presence of endocytosis and exocytosis. We find that in the absence of any diffusion constraints, cell surface protein interaction rate is extremely high relative to cytoplasmic protein interaction rate even in a large mammalian cell with a receptor abundance of a mere two hundred molecules. Since a larger number of downstream signaling events needs to take place, each occurring at a much slower rate than the initial activation via association of cell surface proteins, we conclude that the role of co-localization is most likely that of cross-talk reduction rather than coupling efficiency enhancement.

The two-dimensional (2-D) prolate spheroidal wave function (2-D PSWF) method was previously introduced as an efficient method for trading off between spatial and temporal resolution in magnetic resonance imaging (MRI), with minimal penalty due to truncation and partial volume effects. In the 2-D PSWF method, the k-space sampling area and a matching 2-D PSWF filter, with optimal signal concentration and minimal truncation artifacts, are determined by the shape and size of a given convex region of interest (ROI). The spatial information in the reduced k-space data is used to calculate the total image intensity over a nonsquare ROI instead of producing a low-resolution image. This method can be used for tracking dynamic signals from non-square ROIs using a reduced k-space sampling area, while achieving minimal signal leakage. However, the previous theory is limited to the case of rectilinear sampling. In order to make the 2-D PSWF method more suitable for dynamic studies, this paper presents a generalized version of the 2-D PSWF theory that can be applied to nonrectilinear data acquisition methods. The method is applied to an fMRI study using a spiral trajectory, which illustrates the methods efficiency at tracking hemodynamic signals with high temporal resolution.

Closed-form expressions that lower and upper bound the penalty of hybrid selection/maximal ratio combining relative to maximal ratio combining (MRC) for M-ary phase-shift keying (MPSK) modulation are proved. The bounds offer simple-to-evaluate explicit expressions, and are typically within 0.6 dB for hybrid systems with diversity order up to eight that use at least two branches, yet are independent of signal-to-noise ratio (SNR). Contrary to conclusions conjectured in a previously published paper, it is proved that the SNR penalty is not a constant, independent of SNR. It is also shown that previous estimates of the performance losses of selection diversity relative to MRC underestimate or lower bound the losses for MPSK modulation systems, and that the true loss can be significantly larger than previously believed. An upper bound to this loss is also obtained.

The author presents a new model for stock price fluctuations based on a concept of "information." In contrast, the usual Black-Scholes-Merton-Samuelson (1965, 1973) model is based on the explicit assumption that information is uniformly held by everyone and plays no role in stock prices. The new model is based on the evident nonuniformity of information in the market and the evident time delay until new information becomes generally known. A second contribution of the paper is to present some problems with explicit solutions which are of value in obtaining insights. Several problems of mathematical interest are compared in order to better understand which optimal stopping problems have explicit solutions.

An elliptical region of the plane supports a positive-valued function whose Radon transform depends only on the slope of the integrating line. Any two parallel lines that intersect the ellipse generate equal line integrals of the function. We prove that this peculiar property is unique to the ellipse; no other convex, compact region of the plane supports a nonzero-valued function whose Radon transform depends only on slope. We motivate this problem by considering the detection of a constant-velocity moving object in a sequence of images. In the presence of additive, white, Gaussian noise. The intensity distribution of the object is known, but the velocity is only assumed to lie in some known set, for example, an ellipse or a rectangle. The object is to find a space-time linear filter, operating on the image sequence, whose minimum output signal-to-noise ratio (SNR) for any velocity in the set is maximized. For an ellipse (and its special cases, the disk and the line-segment) the special Radon transform property of the ellipse enables us to obtain a closed-form, analytical solution for the minimax filter, which significantly outperforms the conventional three-dimensional (3-D) matched filter. This analytical solution also suggests a constrained minimax filter for other velocity sets, obtainable in closed form, whose SNR can be very close to the minimax SNR.

An urn containsm balls of value -1 and p balls of value +1. At each turn a ball is drawn randomly, without replacement, and the player decides before the draw whether or not to accept the ball, i.e., the bet where the payoff is the value of the ball. The process continues until all m+p balls are drawn. Let $\overline{V}(m,p)$ denote the value of this acceptance $(m,p)$ urn problem under an optimal acceptance policy. In this paper, we first derive an exact closed form for \overline{V}(m,p) and then study its properties and asymptotic behavior. We also compare this acceptance (m,p) urn problem with the original (m,p)$ urn problem which was introduced by Shepp [Ann. Math. Statist., 40 (1969), pp. 993--1010]. Finally, we briefly discuss some applications of this acceptance (m,p) urn problem and introduce a Bayesian approach to this optimal stopping problem. Some numerical illustrations are also provided.

A convex elliptical region of the plane supports a positive-valued function of two variables whose Radon transform depends only on the slope of the integrating line: any two parallel lines that intersect the ellipse generate equal line integrals of the function. It is somewhat surprising that such a function exists. It is even more surprising, as we show in this paper, that the elliptical region is the only convex compact planar set that supports such a function. We discovered this result while attempting to extend an analytical solution technique for a 2-D integral equation that figures in a certain problem of motion detection in a noisy image sequence.

One important quantity in assessing the viability of local, autonomous, dynamic channel allocation for microcellular systems is user capacity, defined as the average number of users per channel per cell. Here, we determine the capacity for infinite linear and planar arrays of microcells using a very idealized environment. In particular, propagation and interference considerations are simply represented by the constraint that, if a channel is used in a given cell, it cannot be used in R-consecutive rings of cells around that cell. We investigate the elementary case where there is only a single channel available for use in the system. Using this representation, we compute the best and worst user capacities as well as the capacity achieved by random channel placement. While the environment under which these capacities are derived is highly idealized, the results are useful in two important ways. First, the best capacity and the random channel placement capacity we find here for single-channel, self-organized access are fundamental for computing the traffic characteristics of important multichannel dynamic channel allocation algorithms. Second, the random channel placement capacity is close enough to the best that can be achieved to suggest that local, autonomously implemented, dynamic channel allocation loses little capacity when compared with centrally administered fixed channel allocation.>

In a $( t,n,m )$-multipartitioning problem, t lists of $nm$ ordered numbers are partitioned into n sets, where each set contains m numbers from each list. The goal is to maximize some objective function that depends on the sum of the elements in each set and is called the partition function. The authors use the recently developed theory of majorization and Schur convexity with respect to partially ordered sets to study optimal multipartitions for the above problem. In particular, they apply the results to construct a class of counterexamples to a recent conjecture of Du and Hwang, which asserts that (classic) Schur convex functions can be characterized as the partition functions for $( 1,n,m )$-multipartitioning problems having monotone optimal solutions.

Suppose N people are in a circle and each has a K-bit integer on his forehead and can see the others' integers but does not know his own. The problem is to determine how many bits of information must be exchanged among the players so that each can determine his own number after the exchange. The authors provide an algorithm for which the number of bits that suffices equals K plus the least integer >or=K/(N-1). In particular, if N>K, the total of NK bits can be resolved in K+1 transmissions. Since K bits are required to resolve any of the numbers, this is quite efficient, and is shown to be optimal. In addition, the optimal strategy is obtained when the numbers are of different lengths.>

The class of nonnegative definite Toeplitz matrices that can be embedded in nonnegative definite circulant matrices of a larger size is characterized. An equivalent characterization in terms of the spectrum of the underlying process is also presented, together with the corresponding extremal processes. It is shown that a given finite-duration sequence rho can be extended to be the covariance of a periodic stationary processes whenever the Toeplitz matrix R generated by this sequence is strictly positive definite. The sequence rho =1, cos alpha , cos 2 alpha with ( alpha / pi ) irrational, which has a unique nonperiodic extension as a covariance sequence, demonstrates that the strictness is needed. A simple constructive proof supplies a bound on the abovementioned period in terms of the minimal eigenvalue of R. It also yields, under the same conditions, an extension of rho to covariances that eventually decay to zero. For the maximum-likelihood estimate of the covariance of a stationary Gaussian process, the extension length required for using the estimate-maximize iterative algorithm is determined.>

A random loop, or polygon, is a simple random walk whose trajectory is a simple Jordan curve. The study of random loops is extended in two ways. First, the probability P/sub n/(x,y) that a random n-step loop contains a point (x,y) in the interior of the loop is studied, and (1/2, 1/2) is shown to be (1/2)-(1/n). It is plausible that P/sub n/(x,y) tends toward 1/2 for all (x,y), but this is not proved even for (x,y)=(3/2,1/2) A way is offered to simulate random n-step self-avoiding loops. Numerical evidence obtained with this simulation procedure suggests that the probability P/sub n/(3/2,1/2) approximately=(1/2)-(c/n), for some fixed c.>

Hashing with lazy deletion is a simple method for maintaining a dynamic dictionary: items are inserted and sought as usual in a separate-chaining hash table; however, items that no longer need to be in the data structure remain until a later insertion operation stumbles on them and removes them from the table. Because hashing with lazy deletion does not delete items as soon as possible, it keeps more items in the dictionary than methods that use more careful deletion strategies. On the other hand, its space overhead is much smaller than those more careful methods, so if the number of extra items is not too large, hashing with lazy deletion can be a practical algorithm when space is scarce. In this paper, we analyze the expected amount of excess space used by hashing with lazy deletion.

A class of plausible inequalities between conditional probabilities is considered involving random subsets of a set which arise, for example, in studying the capacity of a multiple access channel. Some of the inequalities are true and can be proved by the Fortuin-Kasteleyn-Ginibre (FKG) inequality. Some others are true but seem to need other methods. Still others are false. The results also apply to studying the conditional probability of the failure of a device designed to achieve reliability by using redundant parts, given side information about the failure of some of its components.

Abstract A well known engineering principle in introducing redundancy to a system is that component‐level redundancy is better than system‐level redundancy. However, the mathematical demonstration of this principle is usually for coherent systems constructed by one sequential synthesis and one parallel synthesis (the proof consists of showing that the parallel synthesis should be at the component level). In this article we demonstrate the same principle for systems constructed by parallel‐sequential‐parallel synthesis, one parallel synthesis at the component level and one at the system level. We show that the parallel synthesis at the component level should have more redundancy. The particular vehicle we use for this demonstration is the comparison of blocking probabilities for a 2‐port network known as channel graphs. The crux of the mathematical demonstration is the lemma that [1 − Π (1 − P )]1/a decreases in a, 0 ≤ pi ≤ 1, i = 1,…, n.

We study a model of dynamic storage allocation in which requests for single units of memory arrive in a Poisson stream at rate $\lambda $ and are accommodated by the first available location found in a linear scan of memory. Immediately after this first-fit assignment, an occupied location commences an exponential delay with rate parameter $\mu $, after which the location again becomes available. The set of occupied locations (identified by their numbers) at time t forms a random subset $S_t $ of $\{ 1,2, \cdots \}$. The extent of the fragmentation in $S_t $, i.e. the alternating holes and occupied regions of memory, is measured by $\max (S_t ) - |S_t |$. In equilibrium, the number of occupied locations, $|S|$, is known to be Poisson distributed with mean $\rho = \lambda/ \mu$. We obtain an explicit formula for the stationary distribution of max $(S)$, the last occupied location, and by independent arguments we show that $(E\max (S) - E|S|) /E|S| \to 0$ as the traffic intensity $\rho \to \infty $. Moreover, we verify numerically that for any $\rho $ the expected number of wasted locations in equilibrium is never more than $\frac{1}{3}$ the expected number of occupied locations. Our model applies to studies of fragmentation in paged computer systems, and to containerization problems in industrial storage applications. Finally, our model can be regarded as a simple concrete model of interacting particles [Adv. Math., 5 (1970), pp. 246–290].

Suppose requests to store files arrive at a storage facility in a Poisson stream at rate 1. Each file is allocated storage space on arrival and each remains independently for an exponential time with mean l/p. The lengths of the files are assumed to be independent with common distribution F. Each file is placed in the lowest addressed contiguous sequence of locations large enough to accommodate the fre at its arrival time. This is the so-called first-fit storage discipline. We conjecture that first-fit is asymptotically optimal in the sense that the ratio of expected empty space to expected occupied space tends to zero as p → 0, i.e., as the occupied space tends to ∞. This conjecture seems very hard to prove, but it has been proved for constant file lengths [1], i.e., when F degenerates. We are unable to prove the conjecture but give a graphic display of the results of a Monte Carlo simulation which makes it very convincing.

A model of nonlinear data wave regeneration without retiming is analyzed. Attention is focused on performance after regeneration and subsequent detection. The communication model consists of a pseudoternary signal that is regenerated at one data station, but not retimed prior to retransmission to another station. The signal regeneration is accomplished by a three-level slicer, and this nonlinear transformation degrades the overall system performance in the presence of noise. The extent of this degradation is our subject matter. The formulation and analysis are constructed so that one can put to effective use the fact that, for a certain Gaussian process, one can give definite expressions for the chance that its sample paths lie below a piecewise linear curve on an appropriately restricted time interval. We are able to use events of this type to give upper and lower bounds for the error rate. The bounds are compared with the error rate that would have been obtained had detection been accomplished before the nonlinear regeneration. We hope that the techniques employed here may be of use in other nonlinear communication problems.

We consider binary communication over the additive white Gaussian noise channel with no bandwidth constraint on the channel input signals, assuming the availability of a noiseless delayless feedback link. Although the signals at timetcan depend on the noise at times\tau < tand are therefore random functions, we require that the signal energy never exceed a fixed level. We show that the optimal probability of error is attainable without the use of the feedback channel by using antipodal signals.

Consider the problem of discriminating two Gaussian signals by using only a finite number of linear observables. How to choose the set of n observables to minimize the error probabilityP_{e}, is a difficult problem. BecauseH, the Hellinger integral, andH^{2}form an upper and a lower bound forP_{e}, we minimizeHinstead. We find that the set of observables that minimizesHis a set of coefficients of the simultaneously orthogonal expansions of the two signals. The same set of observables maximizes the HájekJ-divergence as well.