Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Two-stage allocations and the double Q-function | Two-stage allocations and the double Q-function Sergey Agievich National Research Center for Applied Problems of Mathematics and Informatics Belarusian State University Fr. Skorina av. 4 220050 Minsk Belarus agievich@ Submitted Apr 2 2002 Accepted Jun 10 2002 Published May 12 2003 MR Subject Classifications 05A15 05A16 60C05 Abstract Let m n particles be thrown randomly independently of each other into N cells using the following two-stage procedure. 1. The first m particles are allocated equiprobably that is the probability of a particle falling into any particular cell is 1 N. Let the ith cell contain mi particles on completion. Then associate with this cell the probability ai mi m and withdraw the particles. 2. The other n particles are then allocated polynomially that is the probability of a particle falling into the ith cell is ai. Let V V m N be the number of the first particle that falls into a non-empty cell during the second stage. We give exact and asymptotic expressions for the expectation E V. 1 Introduction Problems that deal with random allocations of particles into N cells balls into urns pellets into boxes are classical in discrete probability theory and combinatorial analysis see 3 7 for details . The main results are concerned with determining the probability characteristics of i the number fj r of cells that contain exactly r particles after allocation ii the number vr s of the first particle that falls so that some s cells contain at least r particles each and other random variables. Equiprobable allocations are the most simple and well studied. Consider for example an Internet voting on the theme Which of the N teams will win the world cup . If voters don t know anything about the teams then they make a choice particle for each team cell with equal probability 1 N. The more common model is so-called polynomial allocations. In this case the probabilities a-1 . aN to fall into each cell are given. For THE ELECTRONIC JOURNAL OF COMBINATORICS
