Browsing by Author "Gubner, John A."
Now showing 1 - 9 of 9
Results Per Page
Sort Options
Item Bin Packing and Dynamic File Storage: An 'Any-Fit' Algorithm Can Stabilize.(1987) Gubner, John A.; ISRIn this paper we first consider the one-dimensional bin-packing problem and show that a class of "any-fit" algorithms can bound the expected wasted space in the system under certain conditions. In the second part of the paper we consider a dynamic file- storage problem and show, under certain conditions, that a class of "any-fit" algorithms can bound the expected wasted space left by deleted files.Item Bounding Functions of Markov processes and the Shortest Queue Problem.(1987) Gubner, John A.; Gopinath, B.; Varadhan, S.R.S.; ISRIn this paper we prove a general lemma which can be used to show that the expectation of a nonnegative function of the state of a time-homogeneous Markov process is uniformly bounded in time. This is reminiscent of the classical theory of nonnegative supermartingales, except that our analog of the supermartingale inequality need not hold almost surely. Consequently, the lemma is suitable for establishing the stability of systems that evolve in a stabilizing mode in most states, though from certain states they may jump to a less stable state. We use this lemma to show that "joining the shortest queue" can bound the expected sum of the squares of the differences between all pairs among N queues, even under arbitrarily heavy traffic.Item Deterministic Codes for Arbitrarily Varying Multiple-Access Channels(1988) Gubner, John A.; Narayan, P.; ISRThe Arbitrarily Varying Multiple-Access Channel (AVMAC) is a model of a multiple-access channel with unknown parameters. In 1981, Jahn characterized the capacity region of the AVMAC, assuming that the region had a nonempty interior; however, he did not address the problem of deciding whether or not the capacity region had a nonempty interior. Using the method of types and an approach completely different from Jahn's, we have partially solved this problem. We begin by introducing the simple but crucial notion of symmetrizability for the two-user AVMAC. We show that if an AVMAC is symmetrizable, then its capacity region has an empty interior. For the two-user AVMAC, this means that at least one (and perhaps both) users cannot reliably transmit information across the channel. More importantly, we show that if the channel is suitably nonsymmetrizable, then the capacity region has a nonempty interior, and both users can reliably transmit information across the channel. In light of these results, it is indeed fortunate that to test a channel for symmetrizability, one simply solves a system of linear equations whose coefficients are the channel transition probabilities. Our proofs rely heavily on a rather complicated decoding rule. This leads us to seek conditions under which simpler multiple-message decoding techniques might suffice. In particular, we give conditions under which the universal maximum mutual information decoding rule will be effective. We then consider the situation in which a constraint is imposed on the sequence of "states" in which the channel can reside. We extend our approach to show that in the presence of a state constraint, the capacity region can increase dramatically. A striking example of this effect occurs with the adder channel. This channel is symmetrizable, and without a state constraint, neither user can reliably transmit information across the channel. However, if a suitable state constraint is imposed, each user can reliably transmit more that 0.4 bits of information per channel use.Item Deterministic Codes for Arbitrarily Varying Multiple-Access Channels.(1988) Gubner, John A.; ISRThe arbitrarily varying multiple-access channel (AVMAC) is a model of a multiple access channel with unknown parameters. In 1981, Jahn characterized the capacity region of the AVMAC, assuming that the region had a nonempty interior; however, he did not address the problem of deciding whether or not the capacity region had a nonempty interior. Using the method of types and an approach completely different from Jahn's, we have partially solved this problem. We begin by introducing the simple but crucial notion of symmetrizability for the two-user AVMAC. We show that if an AVMAC is symmetrizable, then its capacity region has an empty interior. For the two-user AVMAC, this means that at least one (and perhaps both) users cannot reliably transmit information across the channel. More importantly, we show that if the channel is suitably nonsymmetrizable, then the capacity region has a nonempty interior, and both users can reliably transmit information across the channel. In light of these results, it is indeed fortunate that to test a channel for symmetrizability, one simply solves a system of linear equations whose coefficients are the channel transition probabilities. Our proofs rely heavily on a rather complicated decoding rule. This leads us to seek conditions under which simpler multiple-message decoding techniques might suffice. In particular, we give conditions under which the universal mazimum mutual informatzon decoding rule will be effective. We then consider the situation in which a constraint is imposed on the sequence of "states" in which the channel can reside. We extend our approach to show that in the presence of a state constraint, the capacity region can increase dramatically. A striking example of this effect occurs with the adder channel . This channel is symmetrizable, and without a state constraint, neither user can reliably transmit information across the channel. However, if a suitable state constraint is imposed, each user can reliably transmit more than 0.4 bits of information per channel use.Item Estimation of the Rate of a Discrete-Time Multivariate Point Process.(1985) Gubner, John A.; Narayan, P.; ISRWe introduce the notion of a discrete-time multivariate point process which can arise in the modeling of an optical communication system. We wish to estimate the rate of this process at time t given the past of the process up to time t-l. This requires the computation of a certain conditional expectation: we perform this computation by introducing an absolutely continuous change of measure and then applying the generalized Bayes' rule.Item Estimation of the Rate of a Doubly-Stochastic Time-Space Poisson Process.(1985) Gubner, John A.; Narayan, P.; ISRWe consider the problem of estimating the rate of a doubly- stochastic, time-space Poisson process when the observations are restricted to a region D subset of R^2. In the general case, we obtain a representation of the minimum mean-square-error (MMSE) estimate in terms of the conditional characteristic function of an underlying state process. In the case D=R^2, we extend a known result to compute the MMSE estimate explicitly. For a special form of the rate process, a well-defined integral equation is presented which defines the linear MMSE estimate of the rate.Item Filtering Results for A Joint Control-Decoding Problem in Optical Communications.(1987) Gubner, John A.; ISRWe consider a doubly-stochastic time-space Poisson-process model for a direct-detection receiver in an optical communication system. Using a Bayesian decision approach to specify the design of the receiver, we encounter a likelihood ratio which, in general, is a function of a certain conditional expectation. We show how the design of the receiver leads to what we call the Joint Control-Decoding Probiem. In a degenerate case, we completely solve the Joint Control-Decoding Problem and compute the conditional expectation mentioned. In the general case, we cannot compute the conditional expectation mentioned above, and hence, cannot proceed to solve the Joint Control-Decoding problem; however, in order to gain insight into the general filtering problem given time-space point-process observations, we attempt to apply known filtering methods to the computation of a related conditional expectation. Finally, we consider linear estimates to substitute for the needed conditional expectation. In the case of a deterministic control, we reduce the linear estimation problem to the solution of a Fredholm integral equation. In the final chapter, we present a discrete-time version of our model which we hope will render the corresponding Discrete-Time Joint Control-Decoding Problem more tractable.Item On the Deterministic-Code Capacity of the Multiple-Access Arbitrarily Varying Channel.(1988) Gubner, John A.; ISRThe capacity region of the multiple-access arbitrarily varying channel (AVC) was characterized by Jahn, assuming that the region had a nonempty interior; however, he did not indicate how one could decide whether or not the capacity region had a nonempty interior. Using the method of types and an approach different from Jahn's, we have partially solved this problem. We begin by considering the notion of symmetrizability for the two-user AVC as an extension of the same notion for the single-user AVC. We show that if a multiple-access AVC is symmetrizable, then its capacity region has an empty interior. For the two-user AVC, this means that at least one (and perhaps both) users cannot reliably transmit information across the channel. More importantly, we show that if the channel is suitably nonsymmetrizable, then the capacity region has a nonempty interior, and both users can reliably transmit information across the channel. Our proofs rely heavily on a rather complicated decoding rule. This leads us to seek conditions under which simpler multiple-message decoding techniques might suffice. In particular, we give conditions under which the universal mazimum mutual information decoding rule will be effective.Item State Constraints for the Multiple-Access Arbitrarily Varying Channel.(1989) Gubner, John A.; ISRIt is known that if a multiple-access arbitrarily varying channel is symmetrizable, then the capacity region has an empty interior. In this paper, we show that if a suitable constraint is placed on the channel state sequences, then the capacity region can contain certain open rectangles and thereby possess a nonempty interior. We also prove a new weak converse under a state constraint. We use our results to establish the capacity region of the two-user adder channel under state constraint 1/2.