Yesterday, an algorithmic idea came into my mind which required a specific component:

  • Given: Set of discrete delements E(i). Likelihood P(i) for the occurence of an element E(i).
  • Goal: A function which returns a random element from E based on the distribution described by P.

What is this useful for? Well, I wanted to implement some kind of stochastic gradient descent algorithm for image registration without gradients but given a certain likelihood for a point to increase the cost function value. However, I think this kind of function comes in handy for many situations.

Matlab Code & Example

I wrote a Matlab function randelement() which solves exactly the problem. It is based on the theory of inverse transform sampling. The link to the download is given below. It is well-documented, that’s why I will only provide a little usage example:

  1. %  select some arbitrary discrete points
  2. E = [-2 0 2 4 6];
  3.  
  4. % select likelihoods for each point
  5. P = [1 0.5 2 0.1 0.5];
  6.  
  7. % get a long vector with elements from P
  8. % distributed according to P
  9. R=randelement(E, [100000 1], P);
  10.  
  11. % verify by looking at the histogram
  12. figure, hist(R);

The histogram will then look somehow similar to this:

histogram

So … this function seems to do what we wanted - I like it!
The latest version of randelement.m can be downloaded here.