function [ coupon, n_coupon, seed ] = coupon_sample ( n_type, seed ) %*****************************************************************************80 % %% COUPON_SAMPLE simulates the coupon collector's problem. % % Discussion: % % The coupon collector needs to collect one of each of N_TYPE % coupons. The collector may draw one coupon on each trial, % and takes as many trials as necessary to complete the task. % On each trial, the probability of picking any particular type % of coupon is always 1 / N_TYPE. % % The most interesting question is, what is the expected number % of drawings necessary to complete the collection? % how does this number vary as N_TYPE increases? What is the % distribution of the numbers of each type of coupon in a typical % collection when it is just completed? % % As N increases, the number of coupons necessary to be % collected in order to get a complete set in any simulation % strongly tends to the value N_TYPE * LOG ( N_TYPE ). % % If N_TYPE is 1, the simulation ends with a single drawing. % % If N_TYPE is 2, then we may call the coupon taken on the first drawing % a "Head", say, and the process then is similar to the question of the % length, plus one, of a run of Heads or Tails in coin flipping. % % Licensing: % % This code is distributed under the GNU LGPL license. % % Modified: % % 16 February 2005 % % Author: % % John Burkardt % % Parameters: % % Input, integer N_TYPE, the number of types of coupons. % % Input, integer SEED, a seed for the random number generator. % % Output, integer COUPON(N_TYPE), the number of coupons of each type % that were collected during the simulation. % % Output, integer N_COUPON, the total number of coupons collected. % % Output, integer SEED, a seed for the random number generator. % max_coupon = 2000; coupon(1:n_type) = 0; straight = 0; n_coupon = 0; % % Draw another coupon. % while ( n_coupon < max_coupon ) [ i, seed ] = i4_uniform_ab ( 1, n_type, seed ); % % Increment the number of I coupons. % coupon(i) = coupon(i) + 1; n_coupon = n_coupon + 1; % % If I is the next one we needed, increase STRAIGHT by 1. % if ( i == straight + 1 ) while ( 1 ) straight = straight + 1; % % If STRAIGHT = N_TYPE, we have all of them. % if ( n_type <= straight ) return; end % % If the next coupon has not been collected, our straight is over. % if ( coupon(straight+1) <= 0 ) break; end end end end fprintf ( 1, '\n' ); fprintf ( 1, 'COUPON_SAMPLE - Fatal error!\n' ); fprintf ( 1, ' Maximum number of coupons drawn without success.\n' ); return end