14 citations · 48 across the 28 of their papers we have counts for
14 papers · 1 filter
Self-intersections of Two-Dimensional Equilateral Random Walks and Polygons
Max B. Kutler, Margaret Rogers, Nicholas Pippenger
We study the mean and variance of the number of self-intersections of the equilateral isotropic random walk in the plane, as well as the corresponding quantities for isotropic equi…
Elementary Proofs of the Main Limit Theorems of Probability
Nicholas Pippenger
We give simple proofs, under minimal hypotheses, of the Weak Law of Large Numbers and the Central Limit Theorem for independent identically distributed random variables. These proo…
Fault Tolerance in Cellular Automata at Low Fault Rates
Mark McCann, Nicholas Pippenger
A commonly used model for fault-tolerant computation is that of cellular automata. The essential difficulty of fault-tolerant computation is present in the special case of simply r…
Analysis of an M/M/1 Queue Using Fixed Order of Search for Arrivals and Service
Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger
We analyze an M/M/1 queue with a service discipline in which customers, upon arriving when the server is busy, search a sequence of stations for a vacant station at which to wait,…
Stochastic Service Systems, Random Interval Graphs and Search Algorithms
Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger
We consider several stochastic service systems, and study the asymptotic behavior of the moments of various quantities that have application to models for random interval graphs an…
The M/M/Infinity Service System with Ranked Servers in Heavy Traffic
Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger
We consider an M/M/Infinity service system in which an arriving customer is served by the first idle server in an infinite sequence S_1, S_2, ... of servers. We determine the first…
Martingale Couplings and Bounds on the Tails of Probability Distributions
Kyle J. Luh, Nicholas Pippenger
Hoeffding has shown that tail bounds on the distribution for sampling from a finite population with replacement also apply to the corresponding cases of sampling without replacemen…
Asymptotic Behavior of the Moments of the Maximum Queue Length During a Busy Period
Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger
We give a simple derivation of the distribution of the maximum L of the length of the queue during a busy period for the M/M/1 queue with lambda<1 the ratio between arrival rate an…
A Bound on the Variance of the Waiting Time in a Queueing System
Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger
Kingman has shown, under very weak conditions on the interarrival- and sevice-time distributions, that First-Come-First-Served minimizes the variance of the waiting time among poss…
Large Deviations and Moments for the Euler Characteristic of a Random Surface
Kevin Fleming, Nicholas Pippenger
We study random surfaces constructed by glueing together filled -gons along their edges, with all pairings of the edges being equally lik…
Carry Propagation in Multiplication by Constants
Alice Izsak, Nicholas Pippenger
Suppose that a random n-bit number V is multiplied by an odd constant M, greater than or equal to 3, by adding shifted versions of the number V corresponding to the 1s in the binar…
Fault Tolerance in Cellular Automata at High Fault Rates
Mark McCann, Nicholas Pippenger
A commonly used model for fault-tolerant computation is that of cellular automata. The essential difficulty of fault-tolerant computation is present in the special case of simply r…
The Linking Probability of Deep Spider-Web Networks
Nicholas Pippenger
We consider crossbar switching networks with base (that is, constructed from crossbar switches), scale (that is, with inputs, outputs and link…
The average amount of information lost in multiplication
Nicholas Pippenger
We show that if X and Y are integers independently and uniformly distributed in the set {1, ..., N}, then the information lost in forming their product (which is given by the equiv…