Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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_] :=
 Block[{weightedResult},

  (* 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],
       vals,
       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],
      PDF[dist][First@vals]}]];

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

It works for plots...

DiscretePlot[
 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?

share|improve this question
    
Is this inverted? I would think the probability of a repeated first element would increase as you allow more elements. –  Daniel Lichtblau Mar 17 at 20:44
    
@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. –  kirma Mar 17 at 21:12
    
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 –  rasher Mar 17 at 21:29
    
@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. :) –  kirma Mar 17 at 21:33
1  
@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. –  rasher Mar 17 at 21:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.