Is it possible to find a seed to generate given set of integers?

15 次查看（过去 30 天）
Omar Ali Muhammed
评论： Walter Roberson 2021-3-9
Given certain ranfom integer numbers defined over [1 N]. Is it possible to find a SEED that is cappable of doing the inverse operation. As an example N=10, given the random numbers 4, 8, 3, 6, 1, 2, 9, 10, 5, 7, Now
Is it possible to find suitable SEED To generate the random number sequence.
Regards

请先登录，再回答此问题。

回答（1 个）

John D'Errico
John D'Errico 2021-3-8
Even for short sequences, finding a seed that would recover a given sequence will potentialy be difficult and it would strongly depend on the random number scheme used to produce that sequence, but is this possible to accomplish at all in general? NO.
Your goal is provably not possible to accomplish, since you might have a sequence of arbitrary length. Therefore the seed, IF it existed, must have sufficient information content available in it, and a seed, by definition, will be itself a number with a fixed number of bits in it.
We can think of this as a hashing scheme, where you implicitly need to encode ALL of the information content in a sequence of length N, into a single number with a fixed number of bits and N may be as large as you wish. If your sequence is long enough, then this is simply not possible.
Sorry.
  4 个评论
显示 2更早的评论
Omar Ali Muhammed
Omar Ali Muhammed 2021-3-9
Dear, I suppose using the MATLAB function randperm() for PRNG. So what is the theory behind what you deduced based on your experiment. Can you explain in more detailes your stratigy.
Regards
Walter Roberson
Walter Roberson 2021-3-9
These days randperm() is implemented using the Fisher-Yates Shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
Before that, randperm() was implemented as
function y = randperm(n,k)
[~,idx] = sort(rand(1,n));
y = idx(1:k);
end
I am not sure what the theoretic analysis of either of those would be.
My earlier experiments were mechanical: I just kept increasing the seed until I got a match.
Hmmm... If I recall correctly, I was exploring "the numbers games", also known as "The Lottery". A certain number of "balls" are drawn from a pool of balls labeled with consecutive numbers, and prizes are awarded according to how many of your numbers match (in any order) the numbers drawn. My question was "if the numbers were drawn by randperm() instead, how short of a leading subset do you need to know in order to be able to find a seed that gives the complete sequence?". I swept a limited range of seeds, and was surprised how many matches I could get for the entire sequence I was working with. I also got non-matches that stopped one short, which implicitly answered the question that in that context, using that technique, you needed the entire sequence. This left open the hypothesis that if you did a better mathematical analysis that you might be able to do better; it also left open the hypothesis that there might be a prefix length beyond which if you knew the entire prefix you could continue the prediction, having established the seed.
A relevant question is whether the set of positive integer double precision numbers is enough to uniquely identify the state of Mersenne Twister . Mathematically you would expect not.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Mathematics 的更多信息

标签

产品


版本

R12.1

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by