I was recently running tests to get items to drop randomly in an old-school computer RPG. I wanted to verify that all items in a range, say, 1-80 would drop in a certain dungeon. But I couldn't do things all at once.

After one test run with the 80-item dungeon, here might be example output from my array of item drops:

Items dropping in D: 1-5, 7-12, 15-21, ...., 73-80

In other words, my program doesn't just print out "yes no yes no" but lumps together a range of consecutive numbers that randomly turned up, where a range is defined as any set of $x \ge 1$ continuous integers that have been rolled. So 1 alone would count as a range, and so would 40-78.

I noticed that this expanded for a while, then it shrank. But I'm curious what m would give the maximum number of ranges. This necessitates a formula for the expected number of ranges in terms of $m$ and $n$, and I have to admit I don't know where to start there. Obviously I could run Monte Carlo simulations to give a guess, but I'm interested in the general formula/derivation.

  • $\begingroup$ A side question would be, what would give the longest text output? For instance, if the output was like 01, 02-03, 06-11, 14, (etc.) how would weighting by range size affect n as a function of m? $\endgroup$ – aschultz Feb 14 at 8:10
  • $\begingroup$ Related. $\endgroup$ – hilberts_drinking_problem Feb 14 at 8:54

Following the derivation described here, we can obtain an explicit probability of getting $k$ intervals when selecting $m$ out of $n$ available objects by extracting coefficients of the following generating function:


Here, $w$ counts objects that do appear, $z$ counts the objects that don't and $u$ counts runs/intervals.

Using Mathematica, we can explicitly compute the expected number of runs for n=numItems and a given m as follows:

numItems = 30; 
f[z_, w_, u_] := (1 - w + u*w)/((1 - z) (1 - w) - u*w*z); 
countNRuns[m_, r_] := 
  f[z, w, u], {z, 0, numItems - m}, {w, 0, m}, {u, 0, r}];
expectedRuns[m_] := 
  N[Sum[r*countNRuns[m, r], {r, 0, m}]/Binomial[numItems, m]];
DiscretePlot[expectedRuns[m], {m, 0, numItems}]

yielding the following for n=30:

enter image description here

Explicit computation for large $n$ is costly, but it seems that the maximal number of runs is achieved when the number of selected items if approximately $n/2 = 40$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.