Knowledge base: Warsaw University of Technology

Settings and your account

Back

Bernoulli sequences: records and random permutations

Oliwia Alicja Gadomska

Abstract

In this bachelor thesis we consider infinite sequences of independent identically distributed continuous random variables. In such sequences we study distribution of the number of records and strings of two subsequent records interrupted by a given number d-1 of non-records, called d-strings. Particularly, we take interest in counts of double records. We prove that these counts are Poisson distributed with mean 1 in three different ways. In the first chapter we introduce the record definition. We show that with probability one infinitely many records occur and record indicators are Bernoulli distributed. Then counts of d-strings are considered. By embedding in a marked Poisson process we prove that these counts are Poisson distributed with parameter 1/d. In the following chapter we consider B-harmonic Bernoulli sequences. We prove that counts of double records are Poisson distributed with mean 1 by probability-generating functions. Also some games whose result is connected with record sequences are presented. In the third chapter of this thesis we consider the number of cycles in random permutations and its relation to records. We show the solution of “hat-check” problem. By introducing Feller algorithm we show the correspondence between double records and fixed points in random permutations. This way we are given the last proof of the fact stated in the beginning.
Diploma type
Engineer's / Bachelor of Science
Diploma type
Bachelor thesis
Author
Oliwia Alicja Gadomska (FMIS) Oliwia Alicja Gadomska,, Faculty of Mathematics and Information Science (FMIS)
Title in Polish
Ciągi Bernoulliego: rekordy i permutacje losowe
Supervisor
Agnieszka Piliszek (FMIS) Agnieszka Piliszek,, Faculty of Mathematics and Information Science (FMIS)
Certifying unit
Faculty of Mathematics and Information Science (FMIS)
Affiliation unit
Faculty of Mathematics and Information Science (FMIS)
Study subject / specialization
, Matematyka
Language
(pl) Polish
Status
Finished
Defense Date
20-09-2019
Issue date (year)
2019
Reviewers
Paweł Naroski (FMIS/DAC) Paweł Naroski,, Department of Algebra and Combinatorics (FMIS/DAC)Faculty of Mathematics and Information Science (FMIS) Agnieszka Piliszek (FMIS) Agnieszka Piliszek,, Faculty of Mathematics and Information Science (FMIS)
Keywords in Polish
rekord, k-string, permutacja losowa, rozkład Poissona, B-harmoniczny ciąg Bernoulliego
Keywords in English
record, k-string, random permutation, Poisson distribution, B-harmonic Bernoulli sequence
Abstract in Polish
W tej pracy licencjackiej rozważamy nieskończone ciągi niezależnych zmiennych losowych o tym samym ciągłym rozkładzie. Zajmujemy się rozkładem liczby rekordów, a także rekordów d-odległych, czyli sekwencji dwóch kolejnych rekordów oddzielonych d-1 nie-rekordami, w takich ciągach. Szczególną uwagę poświęcamy podwójnym rekordom. Przedstawiamy trzy różne dowody faktu, że ich liczba ma rozkład Poissona z parametrem 1. W pierwszym rozdziale wprowadzamy pojęcie rekordu. Pokazujemy, że prawie na pewno wystąpi ich nieskończenie wiele oraz że zmienne losowe informujące o wystąpieniu rekordu na k-tym miejscu ciągu mają rozkład Bernoulliego z prawdopodobieństwem sukcesu 1/k. Następnie, korzystając z pojęcia cechowanego procesu Poissona, dowodzimy, że liczba rekordów d-odległych ma rozkład Poissona z parametrem 1/d. W kolejnym rozdziale skupiamy się na B-harmonicznych ciągach Bernoulliego. Przedstawiamy inny sposób dowodzenia rozkładu liczby podwójnych rekordów, bazujący na funkcjach tworzących rozkładu. Przywołujemy też przykłady gier, w których wynik nawiązuje do rozkładu zmiennych losowych opisujących sekwencje rekordów. Trzeci rozdział tej pracy jest poświęcony związkowi rekordów z cyklami w permutacjach losowych. Prezentujemy w nim rozwiązanie tzw. „hat-check” problem, a następnie, wprowadzając algorytm Fellera, pokazujemy odpowiedniość między podwójnymi rekordami a punktami stałymi permutacji. Dzięki temu otrzymujemy kolejny dowód wspomnianego na początku faktu.
File
  • File: 1
    thesis_pl.pdf
Request a WCAG compliant version
Local fields
Identyfikator pracy APD: 31082

Uniform Resource Identifier
https://repo.pw.edu.pl/info/bachelor/WUTb300d1462709459b846d4e4e8743ac3c/
URN
urn:pw-repo:WUTb300d1462709459b846d4e4e8743ac3c

Confirmation
Are you sure?
Report incorrect data on this page