Algoritmo per generare N numeri casuali tra A e B che sommano a X

Come detto prima, questa domanda in realtà non ha una risposta: le restrizioni imposte sui numeri rendono la casualità discutibile al meglio.

Tuttavia, potresti trovare una procedura che restituisca un elenco di numeri del genere:

Diciamo che abbiamo scelto i primi due numeri a caso come -0.8 e -0.7. Ora il requisito è quello di trovare 3 numeri "casuali" che sommino fino a 2.5 e siano tutti nell'intervallo [-1,1]. Questo problema è molto simile al problema iniziale, solo le dimensioni sono cambiate. Ora, tuttavia, se prendiamo un numero casuale nell'intervallo [-1,1] potremmo finire senza alcuna soluzione. Possiamo limitare la nostra gamma per assicurarci che esistano ancora soluzioni: la somma degli ultimi 2 numeri sarà compresa nell'intervallo [-2,2]. Ciò significa che dobbiamo selezionare un numero compreso nell'intervallo [0,5,1] per assicurarci di raggiungere un totale di 2,5.

La sezione precedente descrive un passaggio del processo.

In generale: determina l'intervallo per il numero successivo applicando l'intervallo del resto dei numeri alla somma richiesta. Pseudo-codice:

function randomNumbers (number, range, sum) {
  restRange = range * (number - 1)
  myRange = intersection ([sum - restRange.upper, sum - restRange.lower], range)

  myNumber = random(myRange)

  rest = randomNumbers (number-1, range, sum - myNumber)

  return [myNumber, rest]
}

Quindi per il caso descritto sopra

randomNumbers (3, [-1,1], 2.5)
  restRange = [-1,1] * (3-1) = [-2,2]
  myRange = intersection ([2.5-2,2.5-(-2)], [-1,1]) = intersection ([0.5,4.5],[-1,1]) = [0.5,1]

Un'implementazione rapida e sporca in Java:

public class TestRandomNumberList
{

    @Test
    public void test()
    {
        double[] numbers = new double[5];
        randomNumbers(numbers, 0, -1, 1, 1);
        assertEquals(sum(numbers), 1.0, 0.00001);
        for (double d : numbers)
        {
            assertTrue(d >= -1 );
            assertTrue(d <= 1);
        }
    }

    private void randomNumbers(double[] numbers, int index, double lowerBound, double upperBound, double sum)
    {
        int next = index + 1;
        if (next == numbers.length)
        {
            numbers[index] = sum;
        }
        else
        {
            int rest = numbers.length - next;  

            double restLowerBound = lowerBound * rest;
            double restUpperBound = upperBound * rest;

            double myLowerBound = Math.max(lowerBound, sum - restUpperBound);
            double myUpperBound = Math.min(upperBound, sum - restLowerBound);

            numbers[index] = random(myLowerBound, myUpperBound);
            randomNumbers(numbers, next, myLowerBound, myUpperBound, sum - numbers[index]);
        }
    }

    private double random(double myLowerBound, double myUpperBound)
    {
        double random = Math.random();
        return myLowerBound + random * (myUpperBound - myLowerBound);
    }

    private double sum(double[] numbers)
    {
        double result = 0;
        for (double num : numbers)
        {
            result += num;
        }
        return result;
    }

}

Semplice, a patto di sapere quanti.

1. Hai bisogno di N numeri chiamati da V1 a Vn. La somma richiesta è S.
2. Genera numeri casuali N (in qualsiasi intervallo conveniente). Sono da R1 a Rn.
3. Calcola la loro somma come SR.
4. Ridimensiona ogni numero in modo Vn = Rn * S / SR.

Potresti produrre un piccolo errore di arrotondamento, ma dubito che questo sarà un problema.

Se il numero N deve essere casuale, scegli prima quello.

Le mie scuse, mi mancava il requisito che i numeri fossero tra A e B. L'algoritmo è esattamente lo stesso. Scegli N numeri casuali, quindi ridimensionali in base a A, B, somma effettiva e somma richiesta. Lascio il resto come dettaglio di implementazione.

È possibile che ciascuna variabile sia distribuita uniformemente su un intervallo mentre la distribuzione congiunta soddisfa un vincolo di codimensione 1. Ad esempio, se si seleziona (x, y, z) in modo che sia uniformemente distribuito su una sfera unitaria, ciascuna coordinata viene distribuita uniformemente sull'intervallo [-1,1]. Le coordinate non sono solo indipendenti.

Anche se si rinuncia all'indipendenza, non è possibile per 5 numeri distribuiti uniformemente su [-1,1] avere una somma costante di 1. Questo perché l'aspettativa è lineare per tutte le variabili casuali, non solo per quelle indipendenti . Se hai 5 variabili casuali che sono distribuite uniformemente su [-1,1], la loro somma ha valore medio 0, quindi non può essere la costante 1.

Altre risposte suggeriscono di selezionare i primi numeri uniformi su [-1,1], quindi correggere gli ultimi numeri. Questo di solito rinuncia alla simmetria tra i numeri. Potresti essere in grado di dire quali numeri sono stati generati senza vincoli e quali sono stati usati per rendere la somma adatta, poiché il quinto numero potrebbe essere in [-1,1] ma potrebbe non avere una distribuzione uniforme.

Invece, potresti prendere una distribuzione condizionale. Poiché il problema è simmetrico, la distribuzione condizionale è simmetrica. Immagina di scegliere un epsilon > 0, campione da [-1,1] 5 volte in modo indipendente e quindi rifiutare la 5-tupla se la somma è maggiore di epsilon a partire da 1. Questo ti dà una distribuzione congiunta all'interno dell'unità 5- cubo che è concentrato vicino al vincolo hyperplane x0 + x1 + x2 + x3 + x4 = 1. Quindi lascia epsilon andare a 0, e si ottiene una distribuzione limitante. Poiché la probabilità di ottenere un punto sul piano è troppo bassa (matematicamente 0, ma positiva per, diciamo, random float a 32 bit) per utilizzare direttamente il campionamento di reiezione, è necessario un altro metodo per produrre questa distribuzione.

È equivalente a produrre {xi / 2 + 1/2} uniforme su [0,1] con somma 3, o {xi / 6 + 1/6} uniforme su [0,1 / 3] con somma 1 Quindi, produce 5 numeri positivi sommando a 1, e quindi rifiuta il campione (ripeti se uno di questi è maggiore di 1/3. (Successivamente moltiplica questi 6 e sottrai 1 per ottenere i numeri su [-1,1] sommando a 1.) Per produrre 5 numeri positivi sommando a 1, un modo è quello di generare 4 numeri casuali su [0,1], ordinarli (y0, y1, y2, y3), aggiungere 0 e 1 in avanti e indietro, (0, y0, y1, y2, y3,1), quindi prendi le differenze (y0, y1-y0, y2-y1, y3-y2,1-y3). (Un altro metodo è per creare 5 variabili casuali esponenzialmente distribuite prendendo -log (uniforme) e rinormalizzare con la loro somma.)

Devi essere cauto nel campionare il rifiuto in alte dimensioni poiché la probabilità di accettazione potrebbe essere bassa, e quindi devi ripetere più volte. La probabilità che tra i 5 numeri sommati a 1, nessuno di essi sia almeno 1/3 può essere trovato con inclusione-esclusione: 1-5 (2/3) ^ 4 + 10 (1/3) ^ 4 = 11 / 81 > 1/8. Quindi, il numero medio di 5 tuple che devi generare con questo metodo prima di trovarne uno senza numero maggiore di 1/3 è inferiore a 8, quindi, in media, ci vogliono meno di 40 numeri in modo casuale per generare una tupla da 5 con somma 1 ricavata dalla distribuzione condizionale. Se i parametri del problema cambiano, potresti preferire un metodo più complicato che eviti il campionamento del rifiuto.

Questa domanda è forse vecchia, ma ecco la mia soluzione (scritta in C #), che è basata sul codice Java di Maarten Winkels:

public static double[] GenerateRandomNumbers(uint values, double minimum, double maximum, double sum, Random generator = null)
    {
        if (values == 0)
            throw new InvalidOperationException($"Cannot create list of zero numbers.");
        if (minimum * values > sum)
            throw new InvalidOperationException($"The minimum value ({minimum}) is too high.");
        if (maximum * values < sum)
            throw new InvalidOperationException($"The maximum value ({maximum}) is too low.");
        if (minimum > maximum)
            throw new InvalidOperationException($"The maximum value ({maximum}) is lower than the minimum value ({minimum}).");
        if (generator == null)
            generator = new Random();

        var numberList = new double[values];

        for (var index = 0; index < values - 1; index++)
        {
            var rest = numberList.Length - (index + 1);

            var restMinimum = minimum * rest;
            var restMaximum = maximum * rest;

            minimum = Math.Max(minimum, sum - restMaximum);
            maximum = Math.Min(maximum, sum - restMinimum);

            var newRandomValue = generator.NextDouble(minimum, maximum);
            numberList[index] = newRandomValue;
            sum -= newRandomValue;
        }

        numberList[values - 1] = sum;

        return numberList;
    }

Codice per la generazione di doppi valori casuali tra un valore minimo e massimo:

public static double NextDouble(this Random generator, double minimum, double maximum)
    {
        if (minimum > maximum)
            throw new InvalidOperationException($"The maximum value ({maximum}) is lower than the minimum value ({minimum}).");

        return generator.NextDouble() * (maximum - minimum) + minimum;
    }

Ed ecco come viene utilizzato:

var min = -1.0;
var max = 1.0;
var sum = 0.0;
uint values = 100000;
var seed = 123;
var generator = new Random(seed);

var randomNumbers = Extensions.GenerateRandomNumbers(values, min, max, sum, generator);

Debug.WriteLine($"Distinct Values: {randomNumbers.Distinct().Count()}");
Debug.WriteLine($"Min: {randomNumbers.Min()}");
Debug.WriteLine($"Max: {randomNumbers.Max()}");
Debug.WriteLine($"Average: {randomNumbers.Average()}");
Debug.WriteLine($"Median: {randomNumbers.Median()}");
Debug.WriteLine($"Sum: {randomNumbers.Sum()}");

Debug.WriteLine("\nFirst 10 values:");
randomNumbers.Take(10).ToList().ForEach(v => Debug.WriteLine(v));

L'output:

Distinct Values: 99800
Min: -0,999962684698385
Max: 1
Average: 0
Median: 0,00128587102577371
Sum: 0

First 10 values:
0,969113830462617
0,815630646336652
0,487091036274606
0,623283306892628
0,477558290342595
-0,903369966849391
-0,965998261219821
-0,701281160908416
-0,610592191857562
0,26017893536956

Un problema che ho dovuto affrontare con il codice di Winkels era che si trattava di un metodo ricorsivo e che per elenchi di grandi dimensioni (> 30.000 numeri) il programma avrebbe lanciato eccezioni StackOverflow. Questo è il motivo per cui l'ho scritto come una funzione iterativa. Ho anche provato a ripulire e rimuovere le operazioni non necessarie. Ho anche aggiunto il supporto per il seeding del generatore di numeri casuali e alcuni errori di gestione.

C'è ancora spazio per miglioramenti. Non ho dato troppa attenzione a quanto questo sia veramente casuale, quindi approfondisci ulteriormente se hai bisogno di fare qualcosa di scientifico.

Puoi iniziare con 5 numeri casuali nell'intervallo, ma devi solo prestare attenzione a quali sono negativi e quali sono positivi.

Caso (A): tutti e 5 i numeri sono positivi.

Qui puoi semplicemente dividere per la loro somma. La somma è garantita per essere maggiore di ogni singolo numero, poiché ogni numero N è positivo. Allora hai

0 < N < 1 

per ogni singolo numero N, e hai la somma normalizzata uguale a 1.

Caso (B): positivi e negativi.

Prima normalizza i negativi in modo che la loro somma sia

-1 < (Sum of normalized negatives) < 0

A questo punto siamo sicuri che ogni numero negativo è ancora all'interno dell'intervallo

-1 < N_negative < 0.

per ogni singolo numero negativo N_negativo.

Avanti normalizza i positivi in modo che

1 - (Sum of normalized positives) = (Sum of normalized negatives)

Ora potremmo aver avuto problemi a prendere uno o più numeri positivi al di fuori dell'intervallo. Controlla se ciò accade. Se no, allora abbiamo finito. In tal caso, quindi rinormalizzare i numeri positivi in modo che il valore individuale massimo sia 1. Sappiamo che la somma dei positivi rinormalizzati sarà inferiore alla somma della prima normalizzazione positiva, ma anche la somma rinormalizzata sarà maggiore di 1. Pertanto può rinormalizzare i negativi in modo che

1 - (Sum of *re*normalized positives) = (Sum of *re*normalized negatives)

E ora abbiamo decisamente finito con il caso B.

Caso (C): tutti i 5 numeri sono negativi.

Questo non ha soluzione.

Un'opzione per risolvere questo problema è costruire un albero di ricerca. Lo stato obiettivo sarà la somma di tutti i nodi lungo il percorso corrente uguale a X. Ogni nodo è un valore diverso tra l'intervallo, quindi il numero di nodi per ciascun livello sarà abs (A) + abs (B). Esplora tutti i percorsi e ottieni tutte le possibili soluzioni. Quindi sceglierne uno a caso dall'elenco di soluzioni.

Lo spazio di ricerca diventerà troppo grande per calcolare quando N e abs (A) + abs (B) sono grandi. È possibile limitare lo spazio di ricerca creando regole. Una semplice regola qui sarebbe che se il percorso contiene gli stessi valori, ma in un ordine diverso, allora sono considerati uguali. Ciò eliminerebbe molti percorsi nell'albero di ricerca. Puoi pensare molto di più per limitare lo spazio di ricerca, ma lascerò quell'esercizio a te.

Nota: questa soluzione è eccessiva, ma è un esercizio divertente.

Vorrei iniziare semplificando il problema. Se si hanno N numeri da [A, B], si sommano fino ad un valore compreso tra N * A e N * B. Sottrarre semplicemente A da ciascun numero e N * A dalla X di destinazione.

Quindi, senza perdita di generalità, possiamo cercare N numeri tra [0, B '] che si sommano a X'. Di nuovo, questo può essere semplificato dividendo X 'da B'.

Il problema risultante sta cercando N numeri in [0,1] che si sommano a X "= (X-A) / (B-A).

Qual è la distribuzione di questi numeri casuali? Il requisito che aggiungono fino a X "significa che non possono essere distribuzioni indipendenti.Sarò scontato che vogliamo la stessa distribuzione per tutti i numeri N. Altrimenti, è banale.Se sappiamo che tutte le distribuzioni sono uguali, facciamo sappi che la loro media deve essere X "/ N. Questo non è necessariamente 1/2, quindi dobbiamo trovare una distribuzione possibilmente asimmetrica su [0,1] - una distribuzione simmetrica ha media 0,5 poiché p (x) == p (1-x). Eppure tutti i numeri dovrebbero essere possibili se X "/ N non è 0 o 1.

A questo punto, è possibile scegliere liberamente una distribuzione parametrizzata che consenta il significato di in (0,1). Una distribuzione esponenziale dovrebbe funzionare correttamente.

Infine, una volta che hai estratto un numero A (0) da questa distribuzione, dovresti ricorrere e calcolare una nuova distribuzione per il prossimo numero mentre ora devi trovare i numeri N-1 che si sommano a X "-A (0). E naturalmente per l'ultimo numero non hai altra scelta.