In the typical "shuffle" operation for a playlist of length $N$, we know that there will be $N-1$ songs between successive hearings of any given song.

Now, let's say we shuffle a list of length $2N$, where each song is present twice. How many songs will we hear, on average, before we hear a song for the second time?

Here's my thinking to date:

We can model our songs as a permutation of the multiset $\{1,1,2,2,3,3,....,N,N\}$.

Each such permutation is equally likely. There are $N!$ ways that each song can be separated by 0 songs (shown by multiset above and each permuation of the $N$ "pairs"). There is another $N!$ ways to arrange them to be separated by $N-1$ other songs. In between, we have the remaining $(2N)! - 2(N!)$ arrangements of songs.

This seems combinatorically complicated. Any ideas for proceeding (apart from brute force simulation?)

To clear any confusion, here's the specific quantity I'm interested in:

$$\frac{\sum_1^n d_i}{n}$$ where $d_i$ is the number of songs between repeat hearings of song title $i$.

  • $\begingroup$ You want all of them to be at distance $i$ or that $i$ is the smallest distance in between every song? $\endgroup$ – Phicar May 30 '17 at 3:00
  • $\begingroup$ @Phicar neither. What is the average distance between repeated songs when we randomly shuffle songs (where each song is represented twice in the playlist). $\endgroup$ – user408433 May 30 '17 at 3:03

If I understand correctly you want the expected value of the difference between both appearences of "Despacito" in a random playlist of $2N$ songs (two of those songs are "Despacito").

The answer is

$$\frac{\sum\limits_{i=1}^{2N-1} i(2N-i)}{\binom{2N}{2}}=\frac{\binom{2N+1}{3}}{\binom{2N}{2}}=\frac{2N+1}{3}$$

  • $\begingroup$ Almost! See my edit...thanks. $\endgroup$ – user408433 May 30 '17 at 3:29
  • $\begingroup$ oh ok, the answer is the same, $d_i$ is a random variable, you are interested in the expected value of the random variable defined as the sum of all $d_i$'s but we can use linearity of expectation. $\endgroup$ – Jorge Fernández Hidalgo May 30 '17 at 3:31
  • $\begingroup$ For what values of $n$ does your solution hold? $n=2$ should be fixed at $0$, since we have only two of the same song. $\endgroup$ – user408433 May 30 '17 at 3:35
  • $\begingroup$ Here, $n=2N$ and $i$ counts the plays until the the second song (not between the two songs). So at $n=2$ we get an expected value of $1$ play until the song is played again, rather than $0$ songs between them. $\endgroup$ – Graham Kemp May 30 '17 at 3:47
  • $\begingroup$ let me relabel following the suggestion by graham $\endgroup$ – Jorge Fernández Hidalgo May 30 '17 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy