0
$\begingroup$

Background:
Transitive several dice that act individually as if they are uniformly random but they are built to work against each other. If you know which one your opponent chose, there is a different one you can choose that will win on average much more than it would if they were both actually uniformly random.

At Microsoft research (link)
As dice (link) tutorial (link)

By win, it means that if you roll dice many times, the one that you selected has a higher value more often than not compared to your opponent. If you roll a 4 and they roll a 3, you one once because your value was higher. If you roll a 3 and they roll a 4 then you lost once because your value was higher.

For a typical (non-transitive) balanced die, the number of wins and losses would tend to balance out. For the transitive die, if a winner is selected then the wins vs. losses do not balance out. There are much higher rate of winning than for the non-transitive repeated game.

General question:
Does it hold with pseudo-random number generation?

Detail question (aka answerable):
If I had a particular type of random number generator (Mersene-Twister, Knuth-TAOCP-2002, etc) how many digits of a sequence of random numbers from a single but unknown seed would I need to have in order to be able to select a "transitive seed" that would, for some sequence (perhaps equal in length to the previous digit count) act as if it were rolled by a transitive (winning) die?

If I were to extend the single-roll game to RNG, then each die is replaced by a single draw from a RNG. The two controls are "breed" and "seed". If my number is larger than yours, then I win. The iterated game would have the limitation that it would run a finite, but not too small number of steps, and that the breed/seed are set only once. We would draw equal length sequences, and for each sequence compare the values in order. If, my values on average are larger than yours, then I win, otherwise you win. If my "seed" behaves non-transitively then it acts like a typical game and my average number of wins and losses are "close" to "yours". If, however, my sequence behaves "transitively" and "winning" compared to yours then my "wins" will "substantially outnumber" yours. They will outnumber yours in a manner more consistent with the transitive dice.

An example game (not necessarily transitive) in R is:

#set seed, breed for 1
set.seed(1,kind = "Wichmann-Hill")

#draw
y1 <- runif(n = 35)

#set seed, breed for 2
set.seed(84596,kind = "Wichmann-Hill")

#draw
y2 <- runif(n = 35)

#compare
d <- y2 - y1

#summary on games
summary(d)

The results are:

Min.  1st Qu.   Median     Mean  3rd Qu.     Max. 

-0.81260 -0.12970 0.09458 0.06023 0.31960 0.79520

Follow-on questions:
Do some types of random number generators work better/worse than others? Is "Super-Duper" require less unique samples to find transitive winner than "Marsaglia-Multicarry" all else being equal?

Does this behavior show up in the transfer of stocks? If someone uses a random number generator to control stock buy-sell behavior (like when moving large volumes, and trying to hide it), is there a window of time after which a transitive randomizer can be applied to suck value out of, or pump value into, the transfer?

Is there a transitive-dice that works against particular and popular stock-chart-rule decision methods? EWMA? Fibonacci?

Could I use this to attack the seeds used in something like "Kill Disk"? If I could tell the location of "few" most recently written disk sectors how many would I need to know in order to bound the seed?

$\endgroup$
  • 1
    $\begingroup$ Please explain what "winning" means in the context of two RNGs. $\endgroup$ – whuber May 5 '16 at 17:49
  • $\begingroup$ Thank you for the edit. I believe most of your readers know what transitive dice are. It is not clear how that concept transfers to arbitrary RNGs. Your question suggests your understanding of the situation is unusual, because it seems to confound the RNG with sequences of its output. This makes it difficult to fathom what you are really trying to ask. $\endgroup$ – whuber May 5 '16 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.