Probabilistic Sampling in Ruby

class Product
  def self.recommend(products, distribution)
    accumulative_distribution_intervals = ProbabilityHelper.cumulative_intervals(distribution)
    accumulative_distribution_sum = ProbabilityHelper.cumulative_sum(distribution)
    random_point_in_accumulative_distribution = Random.rand * accumulative_distribution_sum
    accumulative_distribution_intervals.each_with_index do |interval, index|
      if random_point_in_accumulative_distribution >= interval[0] && random_point_in_accumulative_distribution < interval[1]
        return products[index]
      end
    end
  end

  # This method in reality would be a scope that pulled from ActiveRecord or some other data store
  def self.most_popular(n)
    out = []
    n.times do |i|
      out << 'product_' + i.to_s
    end
    out
  end
end

class ProbabilityHelper
  def self.cumulative_intervals(array)
    out = []
    sum = 0
    array.map do |x|
      min = sum
      sum += x
      out << [min, sum]
    end
    out
  end

  def self.cumulative_sum(array)
    sum = 0
    array.map do |x|
      sum += x
    end
    sum
  end
end

Probabilistic Sampling in Ruby rspecs

require 'spec_helper'

describe Product do
  describe '.recommend' do
    subject { described_class.recommend(most_popular_products, distribution) }

    let(:most_popular_products) { described_class.most_popular(10) }
    let(:distribution) { most_popular_products.each_with_index.map { |_, index| (most_popular_products.size - index).to_f / most_popular_products.size } }

    it 'returns a product from the given array' do
      most_popular_products.include?(subject).should be_true
    end

    context 'random point falls within' do
      let(:distribution_cumulative_intervals) { ProbabilityHelper.cumulative_intervals(distribution) }
      let(:distribution_cumulative_sum) { ProbabilityHelper.cumulative_sum(distribution) }

      before do
        Random.should_receive(:rand).and_return(normalized_quantile)
      end

      context 'first quantile' do
        let(:normalized_quantile) { distribution_cumulative_intervals.first.first.to_f / distribution_cumulative_sum }

        it 'returns the first product' do
          subject.should == most_popular_products.first
        end
      end

      context 'fifth quantile' do
        let(:normalized_quantile) { distribution_cumulative_intervals[4].first.to_f / distribution_cumulative_sum }

        it 'returns the fifth product' do
          subject.should == most_popular_products[4]
        end
      end

      context 'last quantile' do
        let(:normalized_quantile) { distribution_cumulative_intervals.last.first.to_f / distribution_cumulative_sum }

        it 'returns the last product' do
          subject.should == most_popular_products.last
        end
      end
    end
  end
end

describe ProbabilityHelper do
  describe '.cumulative_intervals' do
    subject { described_class.cumulative_intervals(array) }

    let(:array) { [1, 2, 3] }

    it { should == [[0, 1], [1, 3], [3, 6]] }
  end

  describe '.cumulative_sum' do
    subject { described_class.cumulative_sum(array) }

    let(:array) { [1, 2, 3] }

    it { should == 6 }
  end
end

Probabilistic Sampling in Ruby usage

# Set up array
product_recommendations = Product.most_popular(10)
# Inverse linear distribution (can be any distribution)
distribution = product_recommendations.each_with_index.map { |_, index| (product_recommendations.size - index).to_f }
# Recommend!
Product.recommend(product_recommendations, distribution)