TAILIEUCHUNG - Báo cáo toán học: "Compositions of Random Functions on a Finite Set"

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: Compositions of Random Functions on a Finite Set. | Compositions of Random Functions on a Finite Set Avinash Dalal Eric Schmutz MCS Department Drexel University Drexel University and Swarthmore College Philadelphia Pa. 19104 Philadelphia Pa. 19104 ADalal@ Submitted July 21 2001 Accepted July 9 2002 MR Subject Classifications 60C05 60J10 05A16 05A05 Abstract If we compose sufficiently many random functions on a finite set then the composite function will be constant. We determine the number of compositions that are needed on average. Choose random functions f1 f2 f3 independently and uniformly from among the nn functions from n into n . For t 1 let gt ft o ft-1 o o f1 be the composition of the first t functions. Let T be the smallest t for which gt is constant . gt i gt j for all i j . We prove that E T 2n as n 1 where E T denotes the expected value of T. 1 Introduction If we compose sufficiently many random functions on a finite set then the composite function is constant. We ask how long this takes on average. More precisely let Un be the set of nn functions from n to n Let An be the n element subset of Un consisting of the constant functions g 2 An iff g i g j for all i j. Let f1 f2 f3 be a sequence of random functions chosen independently and uniformly from Un. Let g1 f1 and for t 1 let gt ft o gt-1 be the composition of the first t random maps. Define T fH to be the smallest t for which gt 2 An. If no such t exists define T 1. It is not difficult to show that Pr T 1 0. Our goal in this paper is to estimate E T . It is natural to restate the problem as a question about a Markov chain. The state space is S s1 s2 sn . For t 0 and r 2 n we are in state sr if and only if gt has exactly r elements in its range. With the convention that go is the identity permutation we start in state sn at time t 0. The question is how long . how many compositions it takes to reach the absorbing state s1. For m 1 let Tm t Range gt m be the amount of time we are in n state sm. Thus T P .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.