Probability of randomly selecting 32 bytes in ascending order

[Chris Miller]

I chose the thread level for what I imagine to be the difficulty of this problem, not my own math ability.

Obviously (?) there are 256^32 possible series. So knowing how (i.e., how to calculate) how many of these are in ascending order would give the answer. Is there some polynomial time algorithm?

 

[jbriggs444]

I chose the thread level for what I imagine to be the difficulty of this problem, not my own math ability.

Obviously (?) there are 256^32 possible series. So knowing how (i.e., how to calculate) how many of these are in ascending order would give the answer. Is there some polynomial time algorithm?

Since there is no size parameter for this problem space, the notion of a polynomial time algorithm does not arise. There is simply a solution. [Expressible as some integer multiple of one part in 256^32]

A more coherent question would be whether there is a polynomial time algorithm for computing the probability that an n byte sequence selected at random is in sorted order. [Expressible as some integer multiple of one part in 256^n]

 

[mfb]

Consider the case of 2, 3 or 4 bytes (how many sorted sets are there?) and you should find a general pattern that is reasonably easy to calculate for larger numbers.

 

[jbriggs444]

Consider the case of 2, 3 or 4 bytes (how many sorted sets are there?) and you should find a general pattern that is reasonably easy to calculate for larger numbers.

The possibility of [some particular collection of] duplicate byte values would seem to interfere with the naive calculation. This is similar to the problem or calculating the probability of being dealt a hand of cards in which the four suits appear in a canonical order (clubs, diamonds, hearts, spades) for instance.

 

[mfb]

No matter how you treat equal values it is easy to take into account.

 

[Chris Miller]

A more coherent question would be whether there is a polynomial time algorithm for computing the probability that an n byte sequence selected at random is in sorted order. [Expressible as some integer multiple of one part in 256^n]

I believe that was my question.

Consider the case of 2, 3 or 4 bytes (how many sorted sets are there?) and you should find a general pattern that is reasonably easy to calculate for larger numbers.

I'll give that a try, thanks...

 

[Vanadium 50]

The possibility of [some particular collection of] duplicate byte values

He said "ascending" which means the solution set contains no "ties". Otherwise it would be "non-descending". That in fact is the key.

 

[jbriggs444]

He said "ascending" which means the solution set contains no "ties". Otherwise it would be "non-descending". That in fact is the key.

Good point! Which takes it back into the constant time category.

Because for n > 256 the answer is trivial. There are no 257 octet sequences that are in strictly ascending order.

 

[.Scott]

I would it attack the problem this way:
First, the series needs to "qualify" by having 32 unique values.
The probability of selecting such a group is (256/256)*(255/256)*...*(225/256) = $$256!/((256-32)!\cdot256^{32})$$

Then, given that 32 values that you picked qualify, the probability that they are in the correct order is:
(1/32)(1/31)...(1/2)(1/1) = $$1/32!$$

The chance of success will be the product of those values:
$$256!/(32!\cdot(256-32)!\cdot256^{32})$$

 

[.Scott]

So the chance of getting a hit is: $$1 : 1.9881\cdot10^{36} = 5.0299293\cdot10^{-37}$$

 

[Vanadium 50]

Note that one can simplify the expression. This is one of those times when the general case makes it clearer.

 

[Chris Miller]

Thanks Scott. I like your approach,though I'm having some difficulty with the second step. I'm not quite convinced that the probability of 32 unique bytes being sorted in ascending order is 1/32! Although... the probability of 2 being so is clearly 1/2. And there are 32! possible arrangements of these bytes, of which only 1 is sorted. Okay, never mind. Thanks.

 

[Buzz Bloom]

Hi Chris:

If I am understanding your question correctly, it is the equivalent of the following.
Assume I randomly draw, without replacement, 32 numbers from a bin of numbers from 1 to 256. If I correctly understand the meaning of "ascending", I assume that all 32 drawn numbers must be different, since it is impossible to be all in ascending order if there are duplicates. OK, then, what is the odds that 32 different numbers are in ascending order? Well there are 32! ways the 32 numbers can be ordered, and only one of those ways is in ascending order.

However, you may have intended "ascending" to mean that duplicates are allowed, and that if duplicates are adjacent to each other and the different numbers are in increasing order, then that combined condition qualifies as being in ascending order. In that case the problem is more difficult since you need to include the calculation of the frequency in which various combinations of duplicates could occur.

Hope this helps.

Regards,
Buzz

 

[Vanadium 50]

Assume I randomly draw, without replacement

Obviously (?) there are 256^32 possible series.

So obviously he is drawing with replacement.

 

[Buzz Bloom]

So obviously he is drawing with replacement.

Hi Vanadium:

I did get that Chris's 256³² corresponded to replacement, but I was not sure that was Chris's intent. I was about to add something about the replacement case to my post when I saw your post. The following is what I was in the process of adding.

Hi Chris:

If replacement is allowed, but a drawing with duplicates is not in the solution set, then you need to calculate the number of possible drawings that do not have duplicates. Do you know how to do this?

Regards,
Buzz

 

[Chris Miller]

The motivation for this is a fictional cryptocurrency's proof of work requirement. I.e., a hashed 32-byte digest with bytes in sorted ascending order. I was going down a different path trying to compute the (number of unique 32-byte sorted sequences)/256³² and wandering off into summations, e.g., (sum(n)=(n*(n+1))/2. But I like Scott's approach better. And have verified his answer with a generic program where 32 is #defined.

unique 32 byte sets: 15325948773774698072083375657196722397966551947092857152688179118080000000000
total 32 byte sets: 115792089237316195423570985008687907853269984665640564039457584007913129639936

probability of unique set: 15325948773774698072083375657196722397966551947092857152688179118080000000000/115792089237316195423570985008687907853269984665640564039457584007913129639936

probability of this set being sorted: 1/263130836933693530167218012160000000

total probability: 15325948773774698072083375657196722397966551947092857152688179118080000000000/30468469351315937463570896608000699346964419072417508397774878807316720686891973615794912062434474469621760000000
= 0.0000000000000000000000000000000000005030101314594843011219439095600573062736908405968063413565428685
= 5.030101314594843011219439095600573062736908405968063413565428685 x 10^-37

This, I believe, is considerably less probable than Bitcoin's current target. But the # of leading sorted bytes could be adjusted just the way Bitcoin's leading zeros are. Help here has been much appreciated.

 

[Vanadium 50]

For selecting m items from a set of n distinct items, the probability m is strictly increasing is

\binom nm n^{-m}

I don't see how this can be turned into a proof of work.

 

[Chris Miller]

SHA256² hashing up a 32-byte digest where all (or a certain leading number) of the bytes appear in sorted order would be sufficiently improbable to constitute "proof of work" exactly the way bitcoin does but by requiring a specific number of leading zeros in the digest. In other words, a large number of hashes would probably be required.

 

[Chris Miller]

Lay awake last night for a few hours trying to solve for:

Given the set of all integers from 1 to n with duplicates (i.e., n^n possible sets), how many of these sets will be sorted ascending order (e.g., the set 11111 where n=5 would qualify).

I've taken it this far:

if n: 1 2 3 4 5 6 7
sets: 1 3 10 35 126 462 1716

Was hoping to see a pattern that would expose some general rule or equation that solves for any n. Clearly no Mensa. No luck. Thoughts?

This is similar enough to the posted problem that I didn't want to start another thread.

 

[jbriggs444]

Given the set of all integers from 1 to n with duplicates (i.e., n^n possible sets), how many of these sets will be sorted ascending order (e.g., the set 11111 where n=5 would qualify).

That is perhaps better phrased as

Given the set of all possible n integer sequences where each integer is in the range 1 to n (i.e. n^n possible sequences), how many will be in non-descending order (e.g. the sequence 1, 1, 1, 1, 1 where n=5 is non-descending).

Edit: Google to @Chris Miller: https://oeis.org/A001700

Looks like "monotone" would have been a good synonym for "non-decreasing"

 

[Chris Miller]

Thanks jbriggs444! And there's "my" series. Will see what I can glean from page...

And here she is: (2*n)!/(2*n!*n!)
Works a treat. Never would've figured that out myself, probably. Thanks for the link.