ConvolutionalFixedSum: Uniformly Generating Random Values with a Fixed Sum Subject to Arbitrary Constraints

David Jack Griffin; Robert Ian Davis

ConvolutionalFixedSum: Uniformly Generating Random Values with a Fixed Sum Subject to Arbitrary Constraints

Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

This paper addresses the problem of uniform random generation of vectors of values with a fixed sum, subject to upper and lower constraints on the individual component values. Solutions to this problem are used extensively in the generation of tasksets, specifically task utilization values, in support of the performance assessment of schedulability tests for real-time systems. This paper introduces a general-purpose solution in the form of an Inverse Volume Ratio Sampling method that is applicable provided that it is possible to determine the ratio of the volume below a given hyperplane to the total volume of the valid region in n-dimensional space, as demarcated by the constraints and the fixed sum. An efficient approach is derived for volume calculation using numerical convolution, thus instantiating the ConvolutionalFixedSum algorithm, which provides a user-specified level of precision, while scaling at O(n³, log(n)). A stringent uniformity test is developed, called the slices test, which is able to fully explore the extent of the valid region in each of the n dimensions. The slices test reveals that while the outputs of UUniFast and ConvolutionalFixedSum form uniform distributions, in some cases the outputs of prior state-of-the-art algorithms do not.

Original language	English
Publication status	Published - 9 May 2025

Bibliographical note

Source code for the ConvolutionalFixedSum algorithm is available at: https://github.com/dgdguk/convolutionalfixedsum. Can be installed in Python via pip install convolutionalfixedsum.

Keywords

Real time system
random number generator

Access to Document

ConvolutionFixedSumFinal published version, 652 KBLicence: CC BY

Cite this

@conference{1d69d148f7724833a6ca77896052cb71,

title = "ConvolutionalFixedSum: Uniformly Generating Random Values with a Fixed Sum Subject to Arbitrary Constraints",

abstract = " This paper addresses the problem of uniform random generation of vectors of values with a fixed sum, subject to upper and lower constraints on the individual component values. Solutions to this problem are used extensively in the generation of tasksets, specifically task utilization values, in support of the performance assessment of schedulability tests for real-time systems. This paper introduces a general-purpose solution in the form of an Inverse Volume Ratio Sampling method that is applicable provided that it is possible to determine the ratio of the volume below a given hyperplane to the total volume of the valid region in n-dimensional space, as demarcated by the constraints and the fixed sum. An efficient approach is derived for volume calculation using numerical convolution, thus instantiating the ConvolutionalFixedSum algorithm, which provides a user-specified level of precision, while scaling at O(n3, log(n)). A stringent uniformity test is developed, called the slices test, which is able to fully explore the extent of the valid region in each of the n dimensions. The slices test reveals that while the outputs of UUniFast and ConvolutionalFixedSum form uniform distributions, in some cases the outputs of prior state-of-the-art algorithms do not.",

keywords = "Real time system, random number generator",

author = "Griffin, {David Jack} and Davis, {Robert Ian}",

note = "Source code for the ConvolutionalFixedSum algorithm is available at: https://github.com/dgdguk/convolutionalfixedsum. Can be installed in Python via pip install convolutionalfixedsum.",

year = "2025",

month = may,

day = "9",

language = "English",

}

TY - CONF

T1 - ConvolutionalFixedSum: Uniformly Generating Random Values with a Fixed Sum Subject to Arbitrary Constraints

AU - Griffin, David Jack

AU - Davis, Robert Ian

N1 - Source code for the ConvolutionalFixedSum algorithm is available at: https://github.com/dgdguk/convolutionalfixedsum. Can be installed in Python via pip install convolutionalfixedsum.

PY - 2025/5/9

Y1 - 2025/5/9

N2 - This paper addresses the problem of uniform random generation of vectors of values with a fixed sum, subject to upper and lower constraints on the individual component values. Solutions to this problem are used extensively in the generation of tasksets, specifically task utilization values, in support of the performance assessment of schedulability tests for real-time systems. This paper introduces a general-purpose solution in the form of an Inverse Volume Ratio Sampling method that is applicable provided that it is possible to determine the ratio of the volume below a given hyperplane to the total volume of the valid region in n-dimensional space, as demarcated by the constraints and the fixed sum. An efficient approach is derived for volume calculation using numerical convolution, thus instantiating the ConvolutionalFixedSum algorithm, which provides a user-specified level of precision, while scaling at O(n3, log(n)). A stringent uniformity test is developed, called the slices test, which is able to fully explore the extent of the valid region in each of the n dimensions. The slices test reveals that while the outputs of UUniFast and ConvolutionalFixedSum form uniform distributions, in some cases the outputs of prior state-of-the-art algorithms do not.

AB - This paper addresses the problem of uniform random generation of vectors of values with a fixed sum, subject to upper and lower constraints on the individual component values. Solutions to this problem are used extensively in the generation of tasksets, specifically task utilization values, in support of the performance assessment of schedulability tests for real-time systems. This paper introduces a general-purpose solution in the form of an Inverse Volume Ratio Sampling method that is applicable provided that it is possible to determine the ratio of the volume below a given hyperplane to the total volume of the valid region in n-dimensional space, as demarcated by the constraints and the fixed sum. An efficient approach is derived for volume calculation using numerical convolution, thus instantiating the ConvolutionalFixedSum algorithm, which provides a user-specified level of precision, while scaling at O(n3, log(n)). A stringent uniformity test is developed, called the slices test, which is able to fully explore the extent of the valid region in each of the n dimensions. The slices test reveals that while the outputs of UUniFast and ConvolutionalFixedSum form uniform distributions, in some cases the outputs of prior state-of-the-art algorithms do not.

KW - Real time system

KW - random number generator

M3 - Paper

ER -