Should you play this game?
Suppose a casino invents a new game that you must pay $250 to play. The game works like this: The casino draws random numbers between 0 and 1, from a uniform distribution. It adds them together until their sum is greater than 1, at which time it stops drawing new numbers. You get a payout of $100 each time a new number is drawn.
For example, suppose the casino draws 0.4 and then 0.7. Since the sum is greater than 1, it will stop after these two draws, and you receive $200. If instead it draws 0.2, 0.3, 0.3, and then 0.6, it will stop after the fourth draw and you will receive $400. Given the $250 entrance fee, should you play the game?
Since there must be at least two numbers drawn, simple math says that 50% of the time it will be only two numbers and lose $50, and 50% of the time it will be at least three numbers and win $50 or more.
It's the "or more" that puts a smile on my face.
While four or more numbers won't happen very often, it's certainly often enough to make this a positive expectation game.
And there's another "or more" in that statement. 😊
Simulation shows a number very close to e, so I am paying $250 to play a game with an ER of about $271.28.
I also "kinda sorta" have a proof of this:
Let P(n) be the probability that your first n numbers sum to < 1
The expected value = 100 x (
2 x (1 - the probability that your first 2 numbers sum to < 1)
+ 3 x (the probability that your first 2 numbers sum to < 1 - the probability that your first 3 numbers sum to < 1)
+ 4 x (the probability that your first 3 numbers sum to < 1 - the probability that your first 4 numbers sum to < 1)
+ ...)
= 100 x (2 x (1 - P(2)) + 3 x (P(2) - P(3)) + 4 x (P(3) - P(4)) + ...)
= 100 x (2 + P(2) + P(3) + P(4) + ...)
If P(n) = 1 / n! (and I have gotten this for 2, 3, and 4, but haven't found a general proof for all n), then this = e.
Okay, MathExtremist and the other real mathoids here - can somebody prove:
Interesting! I find the expected gross return to the player to be $100*e =! $271.72. It costs $250 to play, so the expected profit is $21.72.
Also, please put answers and solutions in spoiler tags, to not ruin the fun for everybody else. I'd like to suggest, ThatDonGuy, that you please edit your post to put in in spoiler tags.
Quote: Wizard
Interesting! I find the expected gross return to the player to be $100*e =! $271.72. It costs $250 to play, so the expected profit is $21.72.
Also, please put answers and solutions in spoiler tags, to not ruin the fun for everybody else. I'd like to suggest, ThatDonGuy, that you please edit your post to put in in spoiler tags.
Okay, although I didn't treat this as a "math problem," but as a request for information, so I don't see why the answer needs to be hidden.
And how did you get your answer?
Quote: ThatDonGuyOkay, although I didn't treat this as a "math problem," but as a request for information, so I don't see why the answer needs to be hidden.
And how did you get your answer?
This is a great exercise in calculus. I have been meaning to write up my solution, but it will take a while. Below is a ...
First, use a double integral to determine the probability of going over 1 in two tries.
Second, use a triple integral to determine the probability of going over 1 in three tries.
Third, use a quadruple integral to determine the probability of going over 1 in four tries.
You will see a pattern between this three probabilities. Once you see this pattern you will be able to easily calculate the answer in Excel. Or you can get it directly if you're familiar with a particular infinite series.
If the values can only be .1, .2, etc., then there is a maximum "win" of $1100 (10 draws at .1 + one additional draw to go over 1.0). Does this affect the expected value?
I've posted it also gives the solution to an interesting puzzle from the week before.Quote: beachbumbabs from duplicate threadIt's an interesting question, so I'm placing the link below that you tried to publish (your linkage ability is restricted by your new membership).
538 puzzler
Agree. Except, in practice it is impossible to chose a random number in the indicated range, so the language of the problem as a gambling problem is incorrect.Quote: Wizard
Interesting! I find the expected gross return to the player to be $100*e =! $271.72. It costs $250 to play, so the expected profit is $21.72.
While technically you are correct for the RNG's that exist today, they are as random as we can possibly get, and for all intensive purposes, can be considered random.Quote: teliotAgree. Except, in practice it is impossible to chose a random number in the indicated range, so the language of the problem as a gambling problem is incorrect.Quote: Wizard
Interesting! I find the expected gross return to the player to be $100*e =! $271.72. It costs $250 to play, so the expected profit is $21.72.
Who did you say had a gambling problem? I missed something ;-)Quote: teliotAgree. Except, in practice it is impossible to chose a random number in the indicated range, so the language of the problem as a gambling problem is incorrect.Quote: Wizard
Interesting! I find the expected gross return to the player to be $100*e =! $271.72. It costs $250 to play, so the expected profit is $21.72.
Surely you didn't mean "intensive purposes."Quote: Romes]While technically you are correct for the RNG's that exist today, they are as random as we can possibly get, and for all intensive purposes, can be considered random.
And yes, there is no such thing as a true RNG that selects from one of infinitely many possible values, as the problem indicates. Nor will there ever be. Such a true RNG is a physical impossibility. In fact, RNGs can only produce rational numbers, and among those, only those with finitely many non-0 decimal digits. No RNG can output a random irrational number. There isn't enough storage space in the universe for the decimal digits of even one such number.
Quote: teliotAgree. Except, in practice it is impossible to chose a random number in the indicated range, so the language of the problem as a gambling problem is incorrect.
What wording would you suggest? I plan to use this for a future Ask the Wizard question. I was planning to remove mention of the word "casino" and go with something like this:
Quote:What is the expected number of trails before the sum of random numbers drawn from a uniform distribution from 0 to 1 exceeds a total of 1?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Quote: WizardWhat wording would you suggest? I plan to use this for a future Ask the Wizard question. I was planning to remove mention of the word "casino" and go with something like this:
Quote:What is the expected number of trails before the sum of random numbers drawn from a uniform distribution from 0 to 1 exceeds a total of 1?
You may want to change trails to trials. :)
All that is correct, and at an even more basic level no finite computer can directly represent any irrational number like pi. Still, asking the question itself isn't improper -- the question was "should you play this game" not "could you." The "should you" question can be answered with continuous math even if a truly continuous embodiment can't be physically realized. Quantum mechanics and all that.Quote: teliotSurely you didn't mean "intensive purposes."
And yes, there is no such thing as a true RNG that selects from one of infinitely many possible values, as the problem indicates. Nor will there ever be. Such a true RNG is a physical impossibility. In fact, RNGs can only produce rational numbers, and among those, only those with finitely many non-0 decimal digits. No RNG can output a random irrational number. There isn't enough storage space in the universe for the decimal digits of even one such number.
http://mathworld.wolfram.com/UniformSumDistribution.html
That page links to the OEIS sequence here: http://oeis.org/A001048
It turns out that I have some familiarity with this sequence. I developed a side bet for keno/bingo games based on drawing increasing numbers from the ball hopper (and paying more as the sequence continues). It turns out that the probability of drawing exactly N increasing numbers before the sequence is terminated by the N+1th draw being less than the Nth draw is 1 in (N! + (N-1)!). E.g., the chances of the second ball being less than the first are 1 in (1! + 0!) = 1/2.
Far be it from me to philosophize about the meaning of a "random number" - however, in all my days on this planet, I have yet to see a random number. A true random number would not be expressible symbolically (with probability 1), as nearly all numbers are incapable of such a description. Moreover, the average size of a randomly chosen positive integer is much larger than the number of elementary particles in the known universe.Quote: WizardWhat is the expected number of trials before the sum of random numbers drawn from a uniform distribution from 0 to 1 exceeds a total of 1?
That said, your statement above seems good to me.
I'm not above philosophizing. :) I think "random number" needs to be taken in context. If I tell you I've seen plenty of random integers between 1 and 6 (inclusive) at the craps table, I think you'd be hard-pressed to argue. The concept of a random real is, as you note, a tougher concept to quantify -- but not to observe. Radioactive decay produces random reals in the form of elapsed time between particle emissions. However, we don't have the technology to record those elapsed times with infinite precision (and never will, I think). That's not a failure of the random process itself, it's a failure of our ability to capture the data.Quote: teliotFar be it from me to philosophize about the meaning of a "random number" - however, in all my days on this planet, I have yet to see a random number. A true random number would not be expressible symbolically (with probability 1), as nearly all numbers are incapable of such a description. Moreover, the average size of a randomly chosen positive integer is much larger than the number of elementary particles in the known universe.
I disagree. Those times are only valid down to the Planck time, which is about 10^(-43) seconds, in other words, only a scant 43 non-0 decimal digits maximum in that RNG.Quote: MathExtremistThe concept of a random real is, as you note, a tougher concept to quantify -- but not to observe. Radioactive decay produces random reals in the form of elapsed time between particle emissions.
That's because they provably don't exist. Thought you'd get that by me, eh? It was a good try, assuming time is continuous and all.Quote:However, we don't have the technology to record those elapsed times with infinite precision
And there is a very good argument to make that time will cease to exist eventually. So, even in the best of all possible universes, your RNG has a half-life.
http://www.scientificamerican.com/article/could-time-end/
(I read the article many years ago, sorry the link is so lame - they're talking about maybe 100T years in the future, when the entire universe is just quantum fluctuations and everything greater than that has evaporated). No, continuous RNGs will never be, no way, not in this universe.
Okay, I'm out of my depth on the question of continuity of time. But I think you could argue that even if time were continuous, it wouldn't matter to humans. Sensory processing takes a measurable time and I recall reading somewhere that the maximum neural transmission is slower than the speed of sound. But back to philosophizing, that's one of the reasons why math exists as a discipline separate from physics -- to study things that can't exist in real life. Like gambling games based on random reals in the range [0,1].Quote: teliotI disagree. Those times are only valid down to the Planck time, which is about 10^(-43) seconds, in other words, only a scant 43 non-0 decimal digits maximum in that RNG.
That's because they provably don't exist. Thought you'd get that by me, eh? It was a good try, assuming time is continuous and all.
XKCD: Purity
Mike, It's just another one in my very long list of science-based pet peeves -- pick a random number in the interval [0,1] -- pah! But at least this pet peeve is deeper than most.Quote: WizardKeep at it gentlemen.
You're not the first to have that thought:Quote: DRichHow would we ever know if a number is random? Can anything be proved to be random? My thought is randomness does not exist we just don't necessarily know how it was derived.
Quote: Of the Laws of Chance, or, a method of Calculation of the Hazards of Game, Plainly demonstrated, And applied to Games as present most in Use
It is impossible for a Die, with such determin'd force and direction, not to fall on such determin'd side, only I don't know the force and direction which makes it fall on such determin'd side, and therefore I call it Chance, wich is nothing but the want of art...
Translated by John Arbuthnot in 1692 from "De Ratiociniis in Ludo Aleae", which in turn was translated from the original 1656 German work "Van Rekeningh in Spelen van Geluck" by Christiaan Huygens.
Quote: WizardThis is a great exercise in calculus. I have been meaning to write up my solution, but it will take a while.
Here's some help for you:
Quote: teliotMike, It's just another one in my very long list of science-based pet peeves -- pick a random number in the interval [0,1] -- pah! But at least this pet peeve is deeper than most.
It would be hard to teach probability and statistics without such exercises.
You have these continuous "attractor" distributions (like the bell curve via the central limit theorem) that allow us to say approximately continuous things for discrete distributions. But, really, it's all discrete when you get right down to it.Quote: WizardIt would be hard to teach probability and statistics without such exercises.
Here's an exercise, Mike. I'm not saying you're not going to find it. But, find me a probability or statistics exercise in some book you have that talks about picking a "random number" generically in a continuous range of values in a similar fashion to this problem.
-continues pet peeve-
*head asplode*
This discussion is both completely different in context but completely the same in concept, as the 0.999999... = 1 thread from a while back.Quote: WizardThis is a great discussion! The very kind I hoped would flourish here. Keep at it gentlemen.
Quote: teliotHere's an exercise, Mike. I'm not saying you're not going to find it. But, find me a probability or statistics exercise in some book you have that talks about picking a "random number" generically in a continuous range of values in a similar fashion to this problem.
From Probability and Statistics by Morris H. Degroot, second edition, copyright 1986, page 193. See exercise 2 or 3.
Quote: teliotHere's an exercise, Mike. I'm not saying you're not going to find it. But, find me a probability or statistics exercise in some book you have that talks about picking a "random number" generically in a continuous range of values in a similar fashion to this problem.
This probably isn't what you mean, but Chapter 7 of Numerical Recipes basically starts out with that:
Quote: Numerical Recipes in C, 2nd edition, p. 275
From http://apps.nrbook.com/c/index.html (the old version is free online, the new version is subscription-only.)
No it's not. Not in the least. I think you don't understand the questions that are being asked in both cases, otherwise you couldn't possibly equate them. One is trivially easy. The other is impossibly difficult.Quote: DJTeddyBearThis discussion is both completely different in context but completely the same in concept, as the 0.999999... = 1 thread from a while back.
Since the drawings can't stop at one pick, because the total must be OVER 1.0, you're just paying $100 to get it right back. I wouldn't expect a casino would want to rate a player and comp on that.
Obviously, the math is the same either way, but it just seems to me an odd way to word the question.
For example, how about this, f(n) = the real number you get in the range [0,1] by disregarding the first n digits of pi and using the remainder to get the decimal number. For example, f(1) = 0.1415926535..., f(2) = 0.415926535..., f(3) = 0.15926535 .... and so on. All you need is a good way to seed it (choose the n to start at). So, pick a random positive integer as the seed. And of course, you would have the nearly impossible task of proving that the resulting decimal numbers are uniformly distributed. And, of course, they form only a countably dense subset of [0,1], so not every number is possible. But, even so, you couldn't name a single irrational number that is not in the range. Sigh.
Quote: teliotThanks Mike and ME, easier than I thought ...
I think you owe each of us a beer.
I'm not sure where our point of departure is. I am not arguing it is impossible to draw a perfect random number. However, that doesn't mean that problems like that of the OP can't have a correct answer or are not worthy of being discussed.
Beer it is.Quote: WizardI think you owe each of us a beer.
I'm not sure where our point of departure is. I am not arguing it is impossible to try a perfect random number. However, that doesn't mean that problems like that of the OP can't have a correct answer or are not worthy of being discussed.
I don't think we depart on any of this. The math question was interesting,and the solutions I've seen are geometrically curious. It's just that the statement of the problem is misguided in its language phrasing it as a gambling problem. I can think of lots of practical ways to pick a number from 1 to 38. But, I can't think of a single practical way to pick a random number in the interval [0,1]. I wouldn't know where to begin. So how could we ever play this so-called gambling game? I think ME came closest, but for Planck time.
Quote: WizardOkay, I hope you people are happy. Here is a link to my solution to the original problem. I welcome all comments and corrections.
Severe glaring at and loss of 25 Mathoid points for using "I think it is safe to assume that" in a proof.
Quote: Wizard
I'm not sure where our point of departure is. I am not arguing it is impossible to try a perfect random number. However, that doesn't mean that problems like that of the OP can't have a correct answer or are not worthy of being discussed.
I agree, while some keep arguing about perfect random generators, a bunch of us would be busy betting the house on this thing.
Hahaha I had the same thought when I saw that. Verbiage Mike... "Therefor I conclude that" would have gotten the extra 25 Mathoid points =P.Quote: ThatDonGuySevere glaring at and loss of 25 Mathoid points for using "I think it is safe to assume that" in a proof.
It can be proven... Have a billion drawing simulation and thus you should be able to prove that each number comes out the number of times it should.Quote: DRichHow would we ever know if a number is random? Can anything be proved to be random? My thought is randomness does not exist we just don't necessarily know how it was derived.
i.e. If you had whole integers 1-10 then you would expect over a billion "random" drawings that each number would come up 1/10th of the time. With the RNG's we're capable of making it can never be "truly random" and it will never be exactly .1 for this example... but it will be .0999999999999999999999999999999999999999, which for me personally, I take as .1 and thus "random."
Quote: teliotBeer it is.
Thank you!
Quote:But, I can't think of a single practical way to pick a random number in the interval [0,1]. I wouldn't know where to begin.
Can't Mathematica draw a random integer from just about any range? For example, 0 to a google. Assuming it can, then take that number and divide it by a google to get, for all intents and purposes a random number from [0,1]?
Whiskey for me, actually. But I won't make you fork over the $18 for a Manhattan on the Strip. :)Quote: teliotBeer it is.
I don't think we depart on any of this. The math question was interesting,and the solutions I've seen are geometrically curious. It's just that the statement of the problem is misguided in its language phrasing it as a gambling problem. I can think of lots of practical ways to pick a number from 1 to 38. But, I can't think of a single practical way to pick a random number in the interval [0,1]. I wouldn't know where to begin. So how could we ever play this so-called gambling game? I think ME came closest, but for Planck time.
Again, I don't think it's a question of whether a human, or any human-created construct, could pick any possible real in [0,1]. The Numerical Recipes book is specifically directed toward how to do numerical operations in a computer. It's a foregone conclusion that the base 2 (or base 10) representation of an irrational number, which is infinite, can't be perfectly stored in a finite computer. That doesn't mean you can't do operations with irrationals; computers pass around sqrt(2) or pi() all the time and end up with results including those terms. It's just that converting a finite formulaic representation like 0.5*sqrt(2)/pi() into a floating point decimal representation results in an inevitable loss of precision. For tasks like Monte Carlo simulation, it doesn't matter, and that's the premise of the random numbers section of Numerical Recipes. The question there is "given that you want to approximate the selection of a uniform real over [0,1] using a digital computer, what are good algorithms to do it?" That's different than asking whether those algorithms are approximations in the first place, because of course they are. Most standard computing systems use no more than 64 bits to represent floating point numbers. Due to the way IEEE 754 stores data, double-precision floats can represent very small numbers, but it's easy to see where that system breaks down. For example, the binary representation of the following two numbers in 64-bit floats is identical so clearly there's data being lost:
1.0000000000000002
1.0000000000000003
Also, try copying that into Excel and see what happens...
I'll again admit to ignorance regarding the issue of radioactive decay vis-a-vis Planck time -- I couldn't find any information that the timing of a subatomic particle decay is necessarily quantized to some integer multiple of Planck time units. What is certainly true is that we can't possibly build a measuring tool capable of telling the difference, and that's an important distinction.
Quote: Romes...It can be proven... Have a billion drawing simulation and thus you should be able to prove that each number comes out the number of times it should...
While having each number come out an equal amount of times, that doesn't prove random.
Yes, but those purposes matter. First off, you'll need a lot more storage to represent that data than the typical 64 bits (see my prior post). Obviously, the more space you dedicate to a digital representation, the more precise you can make it. I just gave the example of how 1.0000000000000002 can't be accurately represented in just 64 bits, but what I just typed there actually uses 18 bytes (characters) so that's an exact 144 bit representation.Quote: WizardCan't Mathematica draw a random integer from just about any range? For example, 0 to a google. Assuming it can, then take that number and divide it by a google to get, for all intents and purposes a random number from [0,1]?
More to teliot's point, I think, anything that involves the technique you describe -- and which is the same technique used by most PRNGs to derive floating point values over a given range -- is necessarily producing only rational numbers. Generating an integer between 0 and INT_MAX, and then dividing by INT_MAX, still leaves a lot of holes in the number line. For example, here's the Mersenne Twister code that does exactly this:
/* generates a random number on [0,1)-real-interval */
double genrand64_real2(void)
{
return (genrand64_int64() >> 11) * (1.0/9007199254740992.0);
}
from http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/mt19937-64.c
Quote: MathExtremistMore to teliot's point, I think, anything that involves the technique you describe -- and which is the same technique used by most PRNGs to derive floating point values over a given range -- is necessarily producing only rational numbers. Generating an integer between 0 and INT_MAX, and then dividing by INT_MAX, still leaves a lot of holes in the number line.
If you can draw an integer from 0 to a google, and then divide by a google, those holes will be pretty tiny. Can anyone provide a real world application for needing a random number where a 128-byte RNG won't do? Yes, such an RNG can't create a true irrational number, but for what purpose would one need one?
Actually, they are infinitely large. That's teliot's objection, I believe. If you pick any two real numbers, there are infinitely many reals between them.Quote: WizardIf you can draw an integer from 0 to a google, and then divide by a google, those holes will be pretty tiny.
I can't think of one, but I'm in the gaming world where "sufficiently random" is 6 bits of data, e.g., craps, roulette, card shuffling. Slot machines have been approved using 8-bit PRNGs. It doesn't take much for people to bet on something uncertain, even if it's not sufficiently precise for, say, meteorological simulations.Quote:Can anyone provide a real world application for needing a random number where a 128-byte RNG won't do? Yes, such an RNG can't create a true irrational number, but for what purpose would one need one?
Quote: MathExtremistIf you pick any two real numbers, there are infinitely many reals between them.
Agreed, but in the real world, who cares?
I don't know that anyone does, and back to my argument about measurability, I don't know that anyone could tell either. I think it's a matter of semantics -- it's impossible to select "any" real from the range [0,1] but it's easy (sort of) to select one of a finite subset of reals in the range [0,1] and use that as a practical approximation to "any". How to do that selection is an interesting computational problem.Quote: WizardAgreed, but in the real world, who cares?
Quote: WizardIf you can draw an integer from 0 to a google, and then divide by a google, those holes will be pretty tiny. Can anyone provide a real world application for needing a random number where a 128-byte RNG won't do? Yes, such an RNG can't create a true irrational number, but for what purpose would one need one?
Data encryption is usually first on the list of applications. Gambling applications seem to be a close second.
As for your generator, what method would you use to select the initial integer to divide? How would you randomize that selection process?
Fermilabs uses decaying Cesium to generate numbers. I think we can trust that source to extent that we can measure it accurately.
Mike, in the problem stated on 538 that you answered in this thread, it is not the least bit clear that the bias of any given computer rng wouldn't substantially impact the odds of the game. If you read through the Big Crush tests to certify rngs, you would be surprised to learn the the Mersenne Twister doesn't pass all of those tests, even though the Mersenne Twister does pass the much less robust Diehard tests. I would hardly know where to begin to compute the EV of the game using the Mersenne Twister as the RNG and 64 bit representations for the doubles in the range [0,1].Quote: WizardIf you can draw an integer from 0 to a google, and then divide by a google, those holes will be pretty tiny. Can anyone provide a real world application for needing a random number where a 128-byte RNG won't do? Yes, such an RNG can't create a true irrational number, but for what purpose would one need one?
As for holes -- you've given only finitely many numbers on a continuous interval, and you ask if there are holes. Yikes!
