I want to solve the following problem symbolically, using Probability:

What is the probability of the first random variate of a set to be present more than once, if the set is constructed of random variates from a specific discrete probability distribution in a way that its' length is at most N, and any other duplicates except the first variate are removed?

Maybe that's not the most elegant way to describe the problem, but it's better than nothing.

What I would want is to reach a symbolic result using Probability in a descriptive way that is intuitively reached from the definition of the problem.

At the moment, I have only a numeric simulation to solve this problem:

prob[dist_, n_] :=

  (* Return {probability, weight} for a single trial *)
  weightedResult[] :=
   Block[{f, test},

    (* Append if value is the same as first, or not in rest *)
    f[vals_] :=
     With[{v = RandomVariate[dist]},
      If[vals != {} && v != First@vals && MemberQ[Rest@vals, v],
       Append[vals, v]]];

    (* Stop nesting if first and last are the same, 
    or limiting length of unique values is reached *)
    test[{} | {_}] := True;
    test[vals_] := First@vals != Last@vals && Length[vals] < n;
    Block[{vals = NestWhile[f, {}, test]},
     {Boole[First@vals == Last@vals],

  (* Computes weighted mean of 10000 trials *)
  WeightedData @@ 
    Transpose[ParallelTable[weightedResult[], {10000}]] // Mean]

It works for plots...

 prob[DiscreteUniformDistribution[{1, n}], 10], {n, 10, 50}]

enter image description here

DiscretePlot[prob[GeometricDistribution[1/n], 10], {n, 2, 20}]

enter image description here

Where to start on symbolic solution?

  • 1
    $\begingroup$ Is this inverted? I would think the probability of a repeated first element would increase as you allow more elements. $\endgroup$ – Daniel Lichtblau Mar 17 '14 at 20:44
  • $\begingroup$ @DanielLichtblau Maybe my wording needs improvement. As you see, I widen DiscreteUniformDistribution and compute probability that between first occurrence of whatever picked value repeats before more than eight other values (duplicates removed) occur before next occurrence of the original one. $\endgroup$ – kirma Mar 17 '14 at 21:12
  • $\begingroup$ Probability 1 if N>=1+ Population size, otherwise it's a modification of 'coupon collector problem', huge amount of literature out there you might get some ideas from. Interesting question, might x-post for the mathematical aspect over at math.stackexchange.com $\endgroup$ – ciao Mar 17 '14 at 21:29
  • $\begingroup$ @rasher N>=1+Population size part is obvious. My question is: how to formulate this question with Probability - preferably in a composable way that shifts "thinking" to Mathematica. :) $\endgroup$ – kirma Mar 17 '14 at 21:33
  • 1
    $\begingroup$ @kirma, as I said, this seems to be a modified CCP - I did something similar (except a "duplicate" vaporized itself and its duplicate) some time ago in MMA, I'll ferret out the code. I'll recommend again, ask at math, sure to elicit a response from someone that has seen the adaptation or something similar, then trivial to turn into code. Math should be fairly simple. $\endgroup$ – ciao Mar 17 '14 at 21:42

Your Answer

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

Browse other questions tagged or ask your own question.