generate 3 random number sequences such that their sum is highly unlikely to be equal

[kant kodali]

Hi All,

I have three processes that can run either on the same machine or across different machines, and each process needs to generate a sequence of random numbers over time. What would be the best approach to generate these numbers (which can be of type int, uint, or bigint) so that the sum of the numbers in the sequence from each individual process is highly unlikely to be equal to the sum from any other process, while also ensuring that when the sums are compared at any given time, each process has an equal chance of having the highest sum

Thanks!

[Robert Engels]

Pretty sure the central limit theorem says this is impossible. 

On Aug 18, 2024, at 6:20 AM, kant kodali <kant...@gmail.com> wrote:



Hi All,

I have three processes that can run either on the same machine or across different machines, and each process needs to generate a sequence of random numbers over time. What would be the best approach to generate these numbers (which can be of type int, uint, or bigint) so that the sum of the numbers in the sequence from each individual process is highly unlikely to be equal to the sum from any other process, while also ensuring that when the sums are compared at any given time, each process has an equal chance of having the highest sum

Thanks!

--
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-dev/CA%2BiiNx-PqXQmDgCecuipjj8VRAB5kqYbMLC3y4c0eSwVPWCa%3Dw%40mail.gmail.com.

[Robert Engels]

Actually I take that back. It depends on your definition of highly unlikely.

With a single number in each series. It is roughly 1 / (2g * 2g * 2g) - pretty unlikely. As the number of items in the series increase it gets worse not better. 

On Aug 18, 2024, at 6:51 AM, Robert Engels <ren...@ix.netcom.com> wrote:



[Robert Engels]

Correction, with 3 processes it is 1 / (2g * 2g). 

On Aug 18, 2024, at 7:31 AM, Robert Engels <ren...@ix.netcom.com> wrote:



[kant kodali]

by "highly unlikely" I mean the probability of the sum of each individual sequence being equal to another is extremely low (I can't put a number on this but say as low as possible). And if this is not possible with sum operation then any other operation of each individual sequence is also OK.

I thought about two approaches but not sure if they are the right way to go

1. Derive an integer from uuidv7 and then take the sum
2. Generate random primes over time by setting a different seed at each individual application and then multiply the random primes of each individual sequence to compare with another

[Robert Engels]

What about overflow? Do you expect the sum of uint32 to fit in a uint32 on will you use a larger type?

What is the sum used for?

This sounds like an XY problem and it would be helpful to describe in more detail what you are trying to do. 

On Aug 18, 2024, at 2:08 PM, kant kodali <kant...@gmail.com> wrote:



[kant kodali]

bigInt works(in fact that is the desired type). The sum or any other operation on the sequence generated by one application is used to compare against another application to declare a "winning" application and the probability of tie should be very low/almost impossible

[Robert Engels]

Just use a secure random from the crypto/rand package. 

But I am not sure why the higher sum means “they win”…

Why not just generate random bits and interpret as a uint64 or larger and he done?

On Aug 18, 2024, at 3:19 PM, kant kodali <kant...@gmail.com> wrote:



[Jason E. Aten]

On Sunday, August 18, 2024 at 9:27:10 PM UTC+1 Robert Engels wrote:

Why not just generate random bits and interpret as a uint64 or larger and he done?

Indeed.

> while also ensuring that when the sums are compared at any given time, each process has an equal chance of having the highest sum

This "equal chance" at "any given time" requirement means that the election process _must be memoryless_. That means that a sum (or any other operation) over a _history_ is never going to work. For example, if you use a sum on the history sequence, the previous winner will be biased towards being the winner again, and you will never get an "equal chance" of each participant being the winner.  In order to guarantee an equal chance at any point in the sequence, you must explicitly ignore the history beyond the current (or most recent) number.

 

[Robert Engels]

Much better stated for what I was getting at. The expected next value is the mid point so the sum is biased towards the previous winner. 

On Aug 27, 2024, at 10:38 PM, Jason E. Aten <j.e....@gmail.com> wrote:



--

You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-dev/2804090f-5fa0-48fe-8a08-f01eede8b880n%40googlegroups.com.