This paper examines the probability that a random polynomial of specific degree over a field has a specific number of distinct roots in that field. Probabilities are found for random quadratic polynomials with respect to various probability measures on the real numbers and p-adic numbers. In the process, some properties of the p-adic integer uniform random variable are explored. The measure Witt ring, a generalization of the canonical Witt ring, is introduced as a way to link quadratic forms and measures, and examples are found for various fields and measures. Special properties of the Haar measure in connection with the measure Witt ring are explored. Higher-degree polynomials are explored with the aid of numerical methods, and some conjectures are made regarding higher-degree p-adic polynomials. Other open questions about measure Witt rings are stated. / Graduation date: 1999

Consider a multi-priority, nonpreemptive, N-server Poisson arrival queueing system. The number of servers requested by an arrival has a known probability distribution. Service times are negative exponential. In order to save available servers for higher priority customers, arriving customers of each lower priority are deliberately queued whenever the number of servers busy equals or exceeds a given priority-dependent cutoff number. A queued priority i customer enters service the instant the number of servers busy is at most the respective cutoff number of servers minus the number of servers requested (by the customer) and all higher priority queues are empty. In other words the queueing discipline is in a sense HOL by priorities, FCFS within a priority. All servers requested by a customer start service simultaneously; service completion instants are independent. We derive the priority i waiting time distribution (in transform domain) and other system statistics.

No description available.

No description available.

No description available.

No description available.

This thesis consists of two parts, Papers A and B, in which some stochastic processes, originating from random matrix theory (RMT), are studied. In the first paper we study the fluctuations of the kth largest eigenvalue, xk, of the Gaussian unitary ensemble (GUE). That is, let N be the dimension of the matrix and k depend on N in such a way that k and N-k both tend to infinity as N - ∞. The main result is that xk, when appropriately rescaled, converges in distribution to a Gaussian random variable as N → ∞. Furthermore, if k1 < ...< km are such that k1, ki+1 - ki and N - km, i =1, ... ,m - 1, tend to infinity as N → ∞ it is shown that (xk1 , ... , xkm) is multivariate Gaussian in the rescaled N → ∞ limit. In the second paper we study the Airy process, A(t), and prove that it fluctuates like a Brownian motion on a local scale. We also prove that the Discrete polynuclear growth process (PNG) fluctuates like a Brownian motion in a scaling limit smaller than the one where one gets the Airy process. / QC 20100716

Quantum key distribution (QKD) can provide unconditional security based on the fundamental laws of quantum physics. Unfortunately, real-life implementations of a QKD system may contain overlooked imperfections and thus violate the practical security of QKD. It is vital to explore these imperfections. In this thesis, I study two practical imperfections in QKD: i) Discovering security loophole in a commercial QKD system: I perform a proof-of-principle experiment to demonstrate a technically feasible quantum attack on top of a commercial QKD system. The attack I utilize is called phase-remapping attack. ii) Generating high-speed truly random numbers: I propose and experimentally demonstrate an ultrafast QRNG at a rate over 6 Gb/s, which is based on the quantum phase fluctuations of a laser. Moreover, I consider a potential adversary who has partial knowledge of the raw data and discuss how one can rigorously remove such partial knowledge with post-processing.

Quantum key distribution (QKD) can provide unconditional security based on the fundamental laws of quantum physics. Unfortunately, real-life implementations of a QKD system may contain overlooked imperfections and thus violate the practical security of QKD. It is vital to explore these imperfections. In this thesis, I study two practical imperfections in QKD: i) Discovering security loophole in a commercial QKD system: I perform a proof-of-principle experiment to demonstrate a technically feasible quantum attack on top of a commercial QKD system. The attack I utilize is called phase-remapping attack. ii) Generating high-speed truly random numbers: I propose and experimentally demonstrate an ultrafast QRNG at a rate over 6 Gb/s, which is based on the quantum phase fluctuations of a laser. Moreover, I consider a potential adversary who has partial knowledge of the raw data and discuss how one can rigorously remove such partial knowledge with post-processing.

El objetivo de esta tesis es estudiar el funcionamiento de los mercados de trabajo dónde los trabajadores son asignados a las empresas por procesos aleatorios usando modelos de asignación bilateral. En estos modelos, los agentes pertenecen a uno de dos conjuntos disjuntos -empresas y trabajadores- y cada agente tiene preferencias ordinales sobre el otro lado del mercado. El problema se reduce a una asignación de los miembros de estos dos conjuntos el uno al otro.En el segundo capítulo, titulado "On Random Matching Markets: Properties and Equilibria," se describe un algoritmo que empieza desde una asignación cualquiera y continua creando, a cada paso, una asignación provisional. En cada momento del tiempo, una empresa es elegida al azar y se considera el mejor trabajador en su lista de preferencias. Si este trabajador ya está asignado a una empresa mejor, la asignación no se altera. En caso contrario, el trabajador y la empresa quedan temporalmente juntos hasta que el trabajador reciba una propuesta de trabajo mejor. Seguidamente, se exploran algunas propiedades del algoritmo; por ejemplo, el algoritmo generaliza el famoso algoritmo de "deferred-acceptance" de Gale y Shapley. Luego se analizan los incentivos que los agentes enfrentan en el juego de revelación inducido por el algoritmo. El hecho de que las empresas son seleccionadas al azar introduce incertidumbre en el resultado final. Una vez que las preferencias de los agentes son ordinales, se utiliza un concepto de equilibrio ordinal, basado en la dominancia estocastica de primer orden.En el tercer capítulo, "Incentives in Decentralized Random Matching Markets," se considera un juego secuencial dónde los agentes actúan de acuerdo con las reglas generales del algoritmo. En este capítulo, las estrategias de los agentes pueden tomar una forma cualquiera y no tienen que coincidir con una lista de preferencias. El primer jugador es la Naturaleza, que elige una secuencia de empresas , que representa la incertidumbre existente en un mercado descentralizado. Luego, las empresas son elegidas de acuerdo con la sequencia y les es dada la oportunidad de hacer una propuesta. Ya que el juego es dinamico, se analizan los equilibrios de Nash ordinales perfectos en subjuegos.En "Random Stable Mechanisms in the College Admissions Problem," se considera el juego inducido por un mecanismo aleatorio estable. En este capítulo, se caracterizan los equilibrios de Nash ordinales. En particular, puede obtenerse una asignación en un equilibrio dónde las empresas revelan sus verdaderas preferencias si y sólo si la asignación es estable con respecto a las verdaderas preferencias.Por fin, en el último capítulo, se caracterizan los equilibrios perfectos ordinales en el juego inducido por un mecanismo aleatorio estable. / The purpose of this thesis is to explore the functioning of labor markets where workers are assigned to firms by means of random processes using two-sided matching models. In these models, agents belong to one of two disjoint sets -firms and workers- and each agent has ordinal preferences over the other side of the market. Matching reduces to assigning the members of these two sets to one another.In the second chapter, entitled "On Random Matching Markets: Properties and Equilibria," I describe an algorithm that starts with any matching situation and proceeds by creating, at each step, a provisional matching. At each moment in time, a firm is randomly chosen and the best worker on its list of preferences is considered. If this worker is already holding a firm he prefers, the matching goes unchanged. Otherwise, they are (temporarily) matched, pending the possible draw of even better firms willing to match this worker. Some features of this algorithm are explored; namely, it encompasses other algorithms in the literature, as Gale and Shapley's famous deferred-acceptance algorithm. I then analyze the incentives facing agents in the revelation game induced by the proposed algorithm. The random order in which firms are selected when the algorithm is run introduces some uncertainty in the output reached. Since agents' preferences are ordinal in nature, I use ordinal Nash equilibria, based on first-order stochastic dominance.In the third chapter, "Incentives in Decentralized Random Matching Markets," I take a step further by considering a sequential game where agents act according to the general rules of the algorithm. The original feature is that available strategies exhaust all possible forms of behavior: agents act in what they perceive to be their own best interest throughout the game, not necessarily according to a list of possible matches. The game starts with a move by Nature that determines the order of play, reflecting the inherently uncertain features of a decentralized market. Then, firms are selected according to the drawn order and given the opportunity to offer their positions. In order to account for the dynamic nature of the game, I characterize subgame perfect ordinal Nash equilibria.Following a different approach, in "Random Stable Mechanisms in the College Admissions Problem," I consider the game induced by a random stable matching mechanism. In this paper, I characterize ordinal Nash equilibria, providing simultaneously some results that extend to deterministic mechanisms. In particular, a matching can be obtained as the outcome of a play of the game where firms reveal their true preferences if and only if it is stable with respect to the true preferences.In closing, in the last chapter I characterize perfect equilibria in the game induced by a random stable mechanism.