I have a contiguous ordered data structure (0 based index):

x= [1/3, 1/3, 1/3]

Let's say I selected index 1 and increased the probability by 1/3. Rest of the probabilities each decrease by 1/6 and the total probability remains P = 1.

x= [1/6, 2/3, 1/6]

Let's say I selected index 2 and increased the probability by 1/3. Rest of the probabilities in total need to decrease by 1/3 to make the total probability remain P= 1.

x= [1/10, 2/5, 1/2]

Is there a name for this kind of data structure? I'd like to research that name and use a library instead of my custom rolled code if possible.


This can be easily achieved by an array $A$ and an additional variable $m$. The entry $A[i]$ stores the probability of $i$ times $m$.

In your example you start with

A=[1,1,1], m=3

The you increase the probability of the second element by 1/3. This can be carried out by setting $A[2]=4$ and $m=6$, which gives

A=[1,4,1], m=6

In general you could set the probability of element $k$ to $p$ by solving the system $$\sum_i A[i] = m \text{ and } A[k]=p\cdot m,$$ for the unknowns $A[k]$ and $m$.

So all you need to do is to set $m$ to $$ m = \frac{\sum_{i\neq k} A[i]}{1-p},$$ and $A[k]=p\cdot m$ for the new $m$.

  • $\begingroup$ @pwned: yepp. Fixed it. $\endgroup$ – A.Schulz Nov 18 '12 at 20:08
  • $\begingroup$ @ASchulz I see where this is going, I will profile this compared to my auto normalizing version. In the meanwhile, would you help me find a data structure similar to this? I know this isn't about how memory is laid out, but it supports all the operations a data structure would have. (mutation of elements, growth, etc) It's about probability distributions and histograms or roulette wheel, or maybe it doesn't exist and I'm making something new. I just need some more keywords. $\endgroup$ – pwned Nov 18 '12 at 21:08
  • $\begingroup$ @pwnd: I suggest your post you request as new question and give all the details. Describe precisely what set of operations should be supported and what are your other requirements. $\endgroup$ – A.Schulz Nov 19 '12 at 9:02

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.