• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

A Study on Poset Probability / En studie om Pomängdsprobabilitet

Jaldevik, Albin January 2022 (has links)
Let <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D%20=%20(%5Cmathbb%7BP%7D,%20%5Cpreceq)" data-classname="equation_inline" data-title="" /> be a finite poset (partially ordered set) with cardinality <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?n" data-classname="equation_inline" data-title="" />. A linear extension of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" /> is an order-preserving bijection <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Csigma" data-classname="equation_inline" data-title="" />: <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D%20%5Crightarrow%20%5Bn%5D" data-classname="equation_inline" data-title="" />, that is, if <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?x%20%5Cpreceq%20y" data-classname="equation_inline" data-title="" /> in <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" /> then <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Csigma(x)%20%5Cle%20%5Csigma(y)" data-classname="equation_inline" data-title="" />. We define the poset probability <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)" data-classname="equation_inline" data-title="" /> as the proportion of linear extensions where <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Csigma(%5Calpha)%20%5Cle%20%5Csigma(%5Cbeta)" data-classname="equation_inline" data-title="" />. We are primarily interested in <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)" data-classname="equation_inline" data-title="" /> for incomparable elements <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Calpha%20%5Cparallel%20%5Cbeta" data-classname="equation" data-title="" />. The probability has significance in areas such as information theory. Let <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?e(%5Cmathbb%7BP%7D)" data-classname="equation_inline" data-title="" /> denote the total number of linear extensions of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" />. We prove that the poset probability can be evaluated as <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)%20=%20%5Cfrac%7B%20%5Csum_%7BT%20%5Cin%20B(%5Calpha,%5Cbeta)%7D%20e(T)%20e(%5Cmathbb%7BP%7D%20%5Csetminus%20(T%20%5Ccup%20%5C%7B%5Calpha%5C%7D))%7D%7Be(%5Cmathbb%7BP%7D)%7D" data-classname="equation" data-title="" /> where <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?B(%5Calpha,%5Cbeta)" data-classname="equation_inline" data-title="" /> is the set of order ideals of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" /> without <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Calpha" data-classname="equation" data-title="" /> or <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cbeta" data-classname="equation" data-title="" />, where we can add <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Calpha" data-classname="equation_inline" data-title="" /> to get a new order ideal of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" />. The practicality of the preceding formula is explored and we show that <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?T%20%5Cin%20B(%5Calpha,%5Cbeta)%20%5CLeftrightarrow%20%5Cleft%5C%7B%20x%20%7C%20x%20%5Cprec%20%5Calpha%20%5Cright%5C%7D%20%5Csubseteq%20T%20%5Ctext%7B%20and%20%7D%20T%20%5Ctext%7B%20order%20ideal%20of%20%7D%0A%5Cleft%5C%7B%20x%20%7C%20%5Calpha%20%5Cnot%20%5Cpreceq%20x,%5C%20%5Cbeta%20%5Cnot%20%5Cpreceq%20x%7D" data-classname="equation" /> The formula is particularly useful for certain classes of posets such as partition posets which are examined in further detail. We apply the formula to prove that, for all partition posets of shape <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Bn,n%5D" data-classname="equation_inline" data-title="" />, the probability obeys <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P((2,a)%20%5Cpreceq%20(1,a+1))%20=%20%5Cfrac%7B%20C_a%20C_%7Bn-a%7D%7D%20%7BC_n%7D" data-classname="equation" data-title="" /> where <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?C_n" data-classname="equation_inline" data-title="" /> is the nth Catalan number and <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?a%20%3C%20n" data-classname="equation_inline" data-title="" />. We also explore how Monte Carlo methods can be used to estimate <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)" data-classname="equation_inline" data-title="" />.

Page generated in 0.0681 seconds