# Expected distance between repeated songs in a playlist when shuffling two of every song?

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$.

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

## 1 Answer

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}$$

• Almost! See my edit...thanks. – user408433 May 30 '17 at 3:29
• 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. – Jorge Fernández Hidalgo May 30 '17 at 3:31
• 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. – user408433 May 30 '17 at 3:35
• 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. – Graham Kemp May 30 '17 at 3:47
• let me relabel following the suggestion by graham – Jorge Fernández Hidalgo May 30 '17 at 4:16