Conference rusure::math

There are two questions here - one is an 'ideal' question about selecting 
with replacement from a set of 100 objects, the other is about your disk 
changer, for which it is important to know what 'random' means, ie. how 
the changer's selection algorithm works. Do you know what the selection 
algorithm is?

    	re: -.1
    
    	I don't have the slightest idea what the selection algorithm is.
    	I was somewhat mistaken in my Base Note in that after a selection
    	is played, it does select the next track from a different disc.
    	However, after it played Disc 3, Track 6, and then went to Disc 7
    	Track 2, for example, it could go back to Disc 3 then, and possibly
    	select the same track as before, as it doesn't keep track of the
    	ones it has already played.  So, I guess the only way that it does
    	vary from complete randomness, is that it won't play 2 tracks from
    	the same disc in succession.
    
    									Mike

    The average number of tracks played before all 100 tracks have been
    played is 518.74.  (A uniform distribution for the selection is
    assumed.)
    
    Proof:
    
    Let E(n,l) be the expected number of tracks played before all tracks
    have been played, when l out of n tracks have not yet been played.
    E(n,0) = 0. 
    
    When a track is selected and played, it might be one of the l tracks
    that have not been played or one of the n-l tracks that have been
    played.  The former reduces us to E(n,l-1), the latter leaves us in the
    same state.  E(n,l) = 1 + l/n * E(n,l-1) + (n-l)/n * E(n,l).
    
    l/n * E(n,l) = 1 + l/n * E(n,l-1).
    
    E(n,l) = n/l + E(n,l-1).
    
    E(n,l) = sum [i = 1 to l] n/i.
    
    
    				-- edp 

    	re: .3
    
    	Thanks.  So that means that on the average, I'll hear every
    	track, except for that "last one", about 5 times before that
    	"last one" is selected?  That's outrageous!  I'm going to
    	write a letter to Sony expressing my dissatisfaction with
    	their Shuffle Play Mode design.  It doesn't seem like it
    	would've been that difficult to keep track of the selections
    	already played, and not play them again until all the tracks
    	had been played.
    
    								Mike
    

Hmmm, well, maybe it's not all that bad, especially since keeping track 
of what's been played requires a 100-cell *memory* of the disk/track usage.
If you have the memory, it's just as easy to build a system that samples 
without replacement, which can guarantee you never play the same track twice
in a session.

        The analysis in .3 looks like it was done before the
        restriction in .2 was added.
        
        Dan

    With the restriction, the analysis is practically identical.
    As for the result, multiply the unrestricted result by (n-1)/n.
    Thus, for 100 songs, this restriction provides a 1% improvement
    in the expected wait to hear all the songs.

    Re .7:
    
    How do you figure the analysis is practically identical?  The
    distribution of the number of played songs not on the current disc
    determines the probability of selected an unplayed song, and I don't
    see a straightforward way to determine it.
    
    
    				-- edp

Oops, sorry.  I thought it was simply choosing a different *song*.

    	re: .7,.8
    
    	I think I lost you.  Has that number - 518.74 - gotten larger
    	(worse) or smaller, or has what I mentioned in .2 thrown the
    	calculation (in .3) off altogether?  Thanks.
    
    								 Mike
    

    Re .10:
    
    The answer will get smaller, but we don't know by how much.  Keep
    watching this topic; we'll get it eventually.
    
    
    Re .*:
    
    The selection can be viewed as an independent selection of one of nine
    discs and one of ten tracks.  We could write the probability that a
    disc is done as a function of the number of times it has been selected.
    Given a number of hits for each of the ten disks, multiplying them
    produces the probability all songs have been played.  Subtracting from
    one gives the probability not all of them have been played.  Then
    multiply by the probability of that particular distribution of hits
    (given h hits total), then sum over all distributions of hits and over
    all total numbers of hits.
    
    Obviously, we need a way to simplify that.
    
    How many partitions of 100 are there with not more than 10 partitions
    each containing not more than 10 items?  If it's a manageable number, I
    could write a program to construct the graph of states and compute the
    expected value.  But I suspect it is not a manageable number.
    
    
    				-- edp

    A program to count partitions of 100 or less with not more than 10
    elements in each partition with each element containing not more than
    10 items says there are 184,756 such partitions.  Considering a state
    as a partition and a disc upon which a song was just played, there are
    1,679,601 states. 
    
    The possibilities of the disc changer can be represented as a directed
    graph.  Each node is a state, and an edge is the playing of a song.
    
    Each state can go to at most 18 other states, so there are less than 31
    million edges in the graph.  Each edge has a length of one (one song
    played) and a probability of occurring given the state it comes from.
    A node can be reduced from the graph by replacing each pair of one
    incoming edge and one outgoing edge from that node with a new edge
    between the nodes at the other ends of those edges.  The new edge will
    have a length and probability dependent upon the lengths and
    probabilities of the old pair of edges and any single-edge loops on the
    node being reduced.  (The graph initially has no loops but will gain
    them as nodes are eliminated.)  The new edge may need to be combined
    with an already existed edge between the same two nodes.
    
    I think this algorithm is within the bounds of computation, but it
    would be nice to reduce it further.  I don't want to think about what
    the error of hundreds of millions of additions will be.
                                                            
    
    				-- edp

    
    	re: .12
    
    	Whoa!  It sounds like it's getting quite complicated.
    	Thanks for your continued pursuit of the answer.
    
    							 Mike