Probability of randomly selecting 32 bytes in ascending order

  • #1
365
34
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?
 

Answers and Replies

  • #2
jbriggs444
Science Advisor
Homework Helper
9,611
4,258
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]
 
  • #3
35,268
11,534
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.
 
  • #4
jbriggs444
Science Advisor
Homework Helper
9,611
4,258
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.
 
  • #5
35,268
11,534
No matter how you treat equal values it is easy to take into account.
 
  • Like
Likes jbriggs444
  • #6
365
34
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...
 
  • #7
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
26,429
9,936
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.
 
  • #8
jbriggs444
Science Advisor
Homework Helper
9,611
4,258
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.
 
Last edited:
  • #9
.Scott
Homework Helper
2,677
985
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})$$
 
  • #10
.Scott
Homework Helper
2,677
985
So the chance of getting a hit is: $$1 : 1.9881\cdot10^{36} = 5.0299293\cdot10^{-37}$$
 
  • #11
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
26,429
9,936
Note that one can simplify the expression. This is one of those times when the general case makes it clearer.
 
  • Like
Likes mfb
  • #12
365
34
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.
 
  • #13
Buzz Bloom
Gold Member
2,347
416
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
 
  • #14
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
26,429
9,936
Assume I randomly draw, without replacement
Obviously (?) there are 256^32 possible series.
So obviously he is drawing with replacement.
 
  • #15
Buzz Bloom
Gold Member
2,347
416
So obviously he is drawing with replacement.
Hi Vanadium:

I did get that Chris's 25632 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
 
  • #16
365
34
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)/25632 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.
 
  • #17
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
26,429
9,936
For selecting m items from a set of n distinct items, the probability m is strictly increasing is

[tex] \binom nm n^{-m}[/tex]

I don't see how this can be turned into a proof of work.
 
  • #18
365
34
SHA2562 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.
 
  • #19
365
34
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.
 
  • #20
jbriggs444
Science Advisor
Homework Helper
9,611
4,258
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"
 
Last edited:
  • Like
Likes Chris Miller
  • #21
365
34
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.
 

Related Threads on Probability of randomly selecting 32 bytes in ascending order

Replies
10
Views
51K
Replies
1
Views
1K
Replies
28
Views
2K
  • Last Post
Replies
8
Views
2K
Replies
4
Views
8K
Replies
29
Views
2K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
17
Views
10K
Replies
3
Views
2K
  • Last Post
Replies
12
Views
1K
Top