random number with an expected average without loops

Question

Given a uniform random number generator that works in O(1), generating a random floating point number on the interval [0..1), how could I generate a random integer on a range [a..b] where a and b are integers, and I expect the average value generated over a large number of iterations to be c, where c is a floating point number on the interval (a..b)?

I've looked over similar questions already on StackOverflow, such as this, this, and this, but they seem to each have a different focus than what I am after.

Edit: my apologies for stating what is evidently an unclear question. I want a function that takes three parameters, a, b, and c and generates a random number between and n such they the expected average if it were repeatedly being called with the same values would be c. For example, if a and b were 0 and 10, and a value of 2.5 was given for c, then the function would tend to produce smaller numbers (ie a skewed but otherwise normal distribution with an average of 2.5 over a large number of calls), while if c were 5, the distribution of values it produces would be more uniform. The solution must also be self contained and not depend on the availability of any other functions than the uniform random number generator. Choice of programming language is largely immaterial, any imperative c-like pseudo code would be fine. Note further that there should be no loops, and that it should complete in O(1) time

For any choice of parameters `a < c < b`, there are infinitely many probability distributions on `{a, a+1, a+2, ..., b}` which have `c` as the expected value. Thus your problem is radically underdetermined. Also -- why do you think an `O(1)` solution is possible? — John Coleman, Jun 23 '17 at 14:33
The ideal distribution would be one that most closely resembles a normal one, but which is skewed (as definition applies to statistics) either to the left or right such that the mean is in a different place than the centre. Are there some reasons why I should think it to not necessarily be possible? — markt1964, Jun 23 '17 at 14:55
I have found a cheap `O(1)` solution, but it is far from your ideal distribution. Let `p` be the probability of picking a number less than `c`, and pick points less than `c` with uniform probability (if you pick such a point) and pick points greater than or equal to `c` with uniform probability (if you pick such a point). By appropriate choice of `p` you can get the expected value of `c` exactly. This follows from the intermediate value theorem. Furthermore, you can algebraically solve for `p`. — John Coleman, Jun 23 '17 at 15:02
By the way `O(1)` is hard in the discrete, non-uniform, case. `O(log(n))` where `n = b-a+1` is rather easy to achieve (though at the cost of `O(n)` memory and pre-processing time). — John Coleman, Jun 23 '17 at 15:18
The probability of picking a number less than c should be equal to the probability of picking a number >c... that's why the average value picked over a large number will tend to be c. Also, hard problems are not the same as impossible, if an O(1) solution is hard, regardless of its the complexity of the calculations involved, it is still O(1). — markt1964, Jun 23 '17 at 18:43
"The probability of picking a number less than c should be equal to the probability of picking a number >c" that is true if you want the *median* to be `c`, not the expected value. For certain discrete distributions there isn't any known `O(1)` way of simulating them. I think that this is the case with e.g. the binomial distribution. The discrete is fundamentally harder to simulate than the continuous, where it is often as simple as inverting a CDF. The book "Random Number Generation and Monte Carlo Methods" by Gentle discusses many of the issues involved. — John Coleman, Jun 23 '17 at 19:00
You are right, of course... my bad. If it is skewed, the mean is obviously going to be different from the median. I'm not sure why discrete would be fundamentally any more difficult than continuous, because I could just take the floor or ceil of any floating point value to get an integer. — markt1964, Jun 23 '17 at 22:32
The problem is that if you take values from a continuous distribution on `[a,b]` which have mean `c` and round those values to the nearest integer, then the mean of those integers will (typically) no longer be `c` itself but would instead be some other number (albeit one which is close to `c`, perhaps close enough for your purposes). — John Coleman, Jun 23 '17 at 22:53
Yes, it would be close enough. I hadn't thought of that before, actually — markt1964, Jun 24 '17 at 00:45

Christian4423 · Answer 1 · 2017-06-22T15:33:15.527

With no code provided, I will assume it is a C based language.

To sum up your question, you want to get a decimal number from the average of your random integers? I do not understand what you mean in the first part of the question.

I would do something like this (c#):

    static float getDecimalAverageFromInts(int a, int b)
    {
        if (a > b)
        {
            throw new System.ArgumentException("Right opperand cannot be greater than left opperand", "a");
        };
        float running_total = 0;
        float total = 0;
        float average = 0;
        for (int i = a; i < b; i++)
        {
            total += a;
            running_total++;
        }
        return average = (total / running_total);
    }

....................................................

I tested it in the console. Here is the full code:

using System;

namespace average
{
    public class Program
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Hello. Please give minimum value");            
            int l_opperand;
            int r_opperand;
            if(int.TryParse(Console.ReadLine(), out l_opperand))
            {
                Console.WriteLine("Thank you for {0}, please provide a max value.", l_opperand);
                if (int.TryParse(Console.ReadLine(), out r_opperand))
                {
                    Console.WriteLine("Thank you for min value: {0} and max value: {1}", l_opperand, r_opperand);
                    Console.WriteLine("Calculating Average....");
                    float average = getDecimalAverageFromInts(l_opperand, r_opperand);
                    Console.WriteLine("Average is {0}", average);
                    Console.ReadLine();
                }
                else
                {
                    Console.WriteLine("Incorrect response");
                    Console.ReadLine();
                }
            }
            else
            {
                Console.WriteLine("Incorrect response");
                Console.ReadLine();
            }
        }
        public static float getDecimalAverageFromInts(int a, int b)
        {
            if (a > b)
            {
                throw new System.ArgumentException("Right opperand cannot be greater than left opperand", "a");
            };
            float running_total = 0;
            float total = 0;
            float average = 0;
            for (int i = a; i < b; i++)
            {
                total += a;
                running_total++;
            }
            return average = (total / running_total);
        }
    }
}

random number with an expected average without loops

1 Answers1