Thesis (M.Sc.). / Written for the Dept. of Mathematics and Statistics. Title from title page of PDF (viewed 2009/09/07). Includes bibliographical references.

Ingeniero Civil Matemático / El Problema de la Secretaria (SP) (por Secretary Problem), un problema con mucho interés desde los años 50, se trata de encontrar una manera de procesar las entrevistas de N candidatos a un puesto de secretaria para maximizar la probabilidad de contratar al mejor de ellos, bajo el supuesto que las entrevistas se realizan en orden aleatorio y que las decisiones tomadas: rechazar o aceptar, son irrevocables. Esto permite modelar directamente la versión discreta del problema. También se puede considerar una versión contínua con una infinidad de candidatos, suponiendo que los instantes de entrevista son tiempos aleatorios uniformes sobre el intervalo [0,1]. Este problema y sus variantes tienen muchas aplicaciones. Esta memoria se enfoca en el estudio de la variante llamada Problema de la Secretaria con Restricciones de Tiempo (TCSP). En la formulación discreta del (TCSP) se rechazan k candidatos y luego se quiere contratar al mejor de los N−k que quedan, mientras que en su formulación contínua se rechazan todos los candidatos entrevistados antes de un tiempo T y luego se quiere contratar al mejor de los candidatos entrevistados después del tiempo T. En ambos casos los candidatos rechazados al principio forman un sampleo, y se puede utilizar la información acumulada en este sampleo inicial para mejorar la toma de decisión durante la fase de aceptación que sigue. Después de familiarizarse con esta variante, se demuestran propiedades que cumple la regla óptima que resuelve el (TCSP) discreto. Basándose en esto, se estudia la siguiente estrategia para el caso contínuo. Se selecciona una sucesión creciente de constantes absolutas {T_i} en [0,1] o tiempos barreras, independientes del tiempo T del sampleo. El proceso de selección se realiza del siguiente modo: sólo se acepta un candidato entrevistado entre los tiempos T_i y T_{i+1} si es mejor que todos los ya entrevistado después del tiempo T y mejor que el i-ésimo mejor del sampleo inicial. Se encuentran fórmulas explícitas para calcular dichas barreras. La regla óptima para resolver el (TCSP) discreto tiene una forma similar, donde en vez de tiempos barreras, se usan candidatos barreras. Se comprueba que a medida que N tiende a infinito, las razones entre la posición del candidato barrera i-ésimo y el número de candidatos tienden al valor encontrado para los tiempos barreras en el caso contínuo. Finalmente, se estudia una variante del (TCSP) en la cual el empleador sólo puede recordar un candidato del periodo del sampleo (no necesariamente el mejor) y al mejor candidato entrevistado luego del sampleo. Se deduce en el caso discreto la forma de la regla óptima en la situación donde el algoritmo guarda el i-ésimo mejor candidato de la zona sampleada. Esta regla interpretada en el caso contínuo consiste en: rechazar a todos los candidatos hasta un tiempo T_1 > T, luego aceptar un candidato entrevistado entre los tiempos T_1 y T_0 > T_1 si es mejor que ambos miembros en memoria, y luego si no se aceptó a nadie, aceptar a un candidato entrevistado después del tiempo T_0 solamente si es mejor que el mejor entrevistado después del tiempo T. Se encuentran fórmulas explícitas para las barreras T_1 y T_0 como función de T y del rango i del candidato del sampleo guardado en memoria.

No description available.

In Chapter 1 the classical secretary problem is introduced. Chapters 2 and 3 are variations of this problem. Chapter 2, discusses the problem of maximizing the probability of stopping with one of the two highest values in a Bernoulli random walk with arbitrary parameter p and finite time horizon n. The optimal strategy (continue or stop) depends on a sequence of threshold values (critical probabilities) which has an oscillating pattern. Several properties of this sequence have been proved by Dr. Allaart. Further properties have been recently proved. In Chapter 3, a gambler will observe a finite sequence of continuous random variables. After he observes a value he must decide to stop or continue taking observations. He can play two different games A) Win at the maximum or B) Win within a proportion of the maximum. In the first section the sequence to be observed is independent. It is shown that for each n>1, theoptimal win probability in game A is bounded below by (1-1/n)^{n-1}. It is accomplished by reducing the problem to that of choosing the maximum of a special sequence of two-valued random variables and applying the sum-the-odds theorem of Bruss (2000). Secondly, it is assumed the sequence is i.i.d. The best lower bounds are provided for the winning probabilities in game B given any continuous distribution. These bounds are the optimal win probabilities of a game A which was examined by Gilbert and Mosteller (1966).

This dissertation is in two parts, each of three chapters. In Part 1, I shall prove some results concerning variants of the 'secretary problem'. In Part 2, I shall bound several generalizations of the acyclic chromatic number of a graph as functions of its maximum degree. I shall begin Chapter 1 by describing the classical secretary problem, in which the aim is to select the best candidate for the post of a secretary, and its solution. I shall then summarize some of its many generalizations that have been studied up to now, provide some basic theory, and briefly outline the results that I shall prove. In Chapter 2, I shall suppose that the candidates come as ‘m’ pairs of equally qualified identical twins. I shall describe an optimal strategy, a formula for its probability of success and the asymptotic behaviour of this strategy and its probability of success as m → ∞. I shall also find an optimal strategy and its probability of success for the analagous version with ‘c’-tuplets. I shall move away from known posets in Chapter 3, assuming instead that the candidates come from a poset about which the only information known is its size and number of maximal elements. I shall show that, given this information, there is an algorithm that is successful with probability at least ¹/e . For posets with ‘k ≥ 2’ maximal elements, I shall prove that if their width is also ‘k’ then this can be improved to ‘k-1√1/k’ and show that no better bound of this type is possible. In Chapter 4, I shall describe the history of acyclic colourings, in which a graph must be properly coloured with no two-coloured cycle, and state some results known about them and their variants. In particular, I shall highlight a result of Alon, McDiarmid and Reed, which bounds the acyclic chromatic number of a graph by a function of its maximum degree. My results in the next two chapters are of this form. I shall consider two natural generalizations in Chapter 5. In the first, only cycles of length at least ’l’ must receive at least three colours. In the second, every cycle must receive at least ‘c’ colours, except those of length less than ‘c’, which must be multicoloured. My results in Chapter 6 generalize the concept of a cycle; it is now subgraphs with minimum degree ‘r’ that must receive at least three colours, rather than subgraphs with minimum degree two (which contain cycles). I shall also consider a natural version of this problem for hypergraphs.

Robbins' problem is an optimal stopping problem where one seeks to minimize the expected rank of their observations among all observations. We examine random walk analogs to Robbins' problem in both discrete and continuous time. In discrete time, we consider full information and relative ranks versions of this problem. For three step walks, we give the optimal stopping rule and the expected rank for both versions. We also give asymptotic upper bounds for the expected rank in discrete time. Finally, we give upper and lower bounds for the expected rank in continuous time, and we show that the expected rank in the continuous time problem is at least as large as the normalized asymptotic expected rank in the full information discrete time version.

In this thesis an optimal stopping problem related to the classical secretary problem is studied. The theory of optimal stopping represents a special branch of stochastic optimization. Here the socalled full information best choice problem with a known number of offers is generalized by maximizing the probability of selecting an r-candidate, where an offer is called r-candidate if it is not lower than the maximal offer reduced by function r. In the first part discrete time is investigated. For this optimal stopping problem to select an r-candidate an optimal stopping time is indicated, the suboptimal myopic stopping time is displayed and threshold rules are studied including asymptotic behaviour. The basis of this optimal stopping problem is displayed in a general setting where the payoff depends on the prophet´s choiceand on the maximal offer, i.e. the value of the prophet. As a further application the mean of the ratio of the gambler´s choice and prophet´s value is investigated. Then in the second part offers arrive in continuous time. Offers are presented according to random arrival times and the horizon terminating the period of choosing is taken to be fixed and random. Here stress is layed on the geometric and on the exponential distribution, i.e. the Poisson process. In the final part the optimal stopping problem of maximizing the duration of owning a sufficiently good offer is applied to the concept of an r-candidate. A distinction between an overall and a temporary r-candidate is made. The duration of owning an r-candidate is investigated for a finite number of offers with regard to recall. The duration problem with discounted epochs is resolved. Finally the duration of owning an r-candidate is considered regarding the Poisson process where the horizon is fixed and exponentially distributed.

Chen, Rosenberg和Shepp（1997）的“雙人決策者的秘書問題“（A Secretary Problem with Two Decision Makers），探討在完整訊息（Full Information）與選擇次序不變的情況下，具有優先選擇權的決策者佔有較大優勢。這裡所謂的優勢意指在雙方最終選擇的大小為勝負條件所產生獲勝機率的比較。而本篇文章主要是延伸此一探討，意即在若不變動兩者選擇的次序，但賦予後選擇決策者較多資訊的條件下，能否平衡雙方的優劣勢。我們首先討論後決策者擁有預知下一步（One-step look-ahead）資訊能力的條件下，雙方優勢的改變；隨之若是在後決策者能預知完全資訊的情況下，是否能平衡雙方的優劣勢。而事實上，即便在後決策者擁有所有資訊的條件，仍無法完全改變此一情況；更進一步而言，先選擇決策者甚至在不知道後決策者已掌握了所有資訊的情況下，仍可佔有獲勝機率大於後決策者的優勢。這裡我們將提供理論與理論上的數值結果。 / Chen, Rosenberg, and Shepp (1997) considered a variation of the "secretary problem" in which the salary demands of a group of applicants are from a known and continuous distribution (i.e., full information case) and these applicants are interviewed sequentially by two managers, say, I and II. For every applicant. Manager I has the right to interview and hire him/her first. If Manager I rejects the applicant, Manager II can interview him/her. No recall is allowed when the applicant is rejected by both managers, and neither manager can interview and hire another applicant once he/she has hired an applicant. The manager who chooses the applicants with the lower salary wins the game. Chen et al. shows that manager I has bigger winning chance than manager II in the full information case. This study is to extend the paper by Chen et al., by giving extra information to manager H. In particular, suppose that manager II can look a few applicants ahead, i.e., he/she knows the salary demands of applicants before manager I interview them. However, under the full-information assumption, even if manager II is a clairvoyant, who claims to be able to see what will happen in the future, his/her winning probability is still less than that of manager I. We provide theoretical proof and simulation to confirm this result.