Birthdays, Broadcasts, and Boolean Algebras: Probabilistic Boolean Algebras and Applications
MetadataShow full item record
In the area of extremal finite set theory there are many combinatorial results concerning the selection of m k-element sets. This type of set selection can also be viewed as a boolean algebra. In this paper we consider a probabilistic construction of this boolean algebra, concentrating on the structure and properties such an algebra may form, particularly the structure of the algebra's atoms. The results are then applied to a generalization of the popular birthday problem, where the event of interest is now whether all selected sets have a unique element; we find an upper bound on the probability of this event. We also extend the definition of the generalized birthday problem to model content protection protocols. While these protocols are widely used in digital media rights management, they are insufficiently analyzed due to a lack of such an underlying model. We focus on the event that revoking the rights of multiple pirate users inadvertently causes the rights of other, authorized users to be unjustly revoked; we give an exact formula for the probability of this event.
computer science; technical report
Previously Published As