Your friend, David Hilbert, runs a casino with space for an infinite number of guests. He installs a slot machine with the following properties:
To understand how profitable this machine is, he wants to know the probability that no one wins the slot machine.
If David fills up his casino with a number of guests approaching infinity, what does this probability approach?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
A comment here brought up asking how we know e x = lim n → ∞ ( 1 + n x ) n . This is often the actual definition given, but a very good discussion of this (along with other definitions) comes from Fields medal winner Timothy Gowers:
(Go down to point #4 to see the e discussion.)
Fond math memories. I was pretty young when I heard of someone buying a whole bunch of lottery tickets and then suing the lottery commision when they didn't win. I imagined buying 100 tickets with a one-in-a-hundred chance then ramped up n and discovered e by this very method.
(I assume the case was thrown out.)
Hey Im a beginner, and I don't really understand how and why the limit as n approaches infinity would be e^x How come ?
Log in to reply
Historically, the definition of e WAS as lim(n->∞) (1+1/n)^n. A decent proof of this fact using a more modern definition of e can be found here: https://mathcs.clarku.edu/~djoyce/ma122/elimit.pdf
Using that limit definition of e, it's not hard to show that e^x = lim(n->∞) (1+x/n)^n, as is shown here: https://math.stackexchange.com/a/358873
Defining e with a limit is erroneous, or at least very backward. Here's why: Limits aren't guaranteed to converge to a value, some can diverge to infinite, negative infinite, or even alternate between different values. So assuming that this limit converges to a single value is very sketchy, or at least until you get to series calculus it is possible to prove it converges with different convergance and divergence theorems, but that seems very out of the way and overcomplicated. That's why I prefer how MIT proffessor David Jerrison presents it. An elegant proof of most of calculus with e: https://ocw.mit.edu/courses/mathematics/18-01-single-variable-calculus-fall-2006/video-lectures/lecture-6-exponential-and-log/
Log in to reply
Other definitions of e have the same problem. The definition of e as the unique number a such that d a x / d x = a x makes all kind of assumptions, about differentiability (involving limits!), existence of a unique solution, etc.
The simplest definition of e is probably e = k = 0 ∑ ∞ k ! 1 , and the existence of the limit is not difficult to prove.
Shouldn't the problem read probability and not odds?
But what about when the casino has only one customer? According to the rules, that customer would have to win.
Log in to reply
Correct. But the problem focuses on the casino filling up indefinitely.
I have two problems with this. 1. The question said that it were odds of winning. So the probability of winning would be 1/(1+n). 2. All the events aren't independent. If the first customer wins, the second cannot play because there is no money in the machine (otherwise giving us the last rule doesn't make any sense). So the probability would be like P = W + LW + LLW + … upto infinity Where W is p(win) and L is p(lose).
Log in to reply
The problem states: "He wants to know the probability that no one wins the slot machine."
@Moderator it’s NOT the definition. The primitive Definition is technically of a function:
[ t ] r c c c l exp ( ⋅ ) : : B x ⟶ ↦ B ∑ n ∈ N n ! 1 x n
where B is any Banach-Algebra ( eg C or R ). One proves that (1) this is an homomophism from the additive structure to the multiplicative structure and (2) it is continuous (in fact infinitely differentiable, in fact holomorphic—obviously).
One now sets in the case of B = C or R , one sets e : = exp ( 1 ) . Now, since exp ( ⋅ ) is a continuous homomorphism between the additive and multiplicative structure it thus holds that e x = exp ( 1 ) x = exp ( x ) for all x ∈ C by any sensible definition of powers.
Finally one may prove that ( 1 + n x ) n ⟶ exp ( x ) for N ∋ n ⟶ ∞ . Then by the above, we thus have lim n → ∞ ( 1 + n x ) n = e x . Ie this is not really a (safe) starting point, it is a corollary of the definition via the above function.
… that being said, of course, one could start with the limit definition, as one does in school, but this is rubbish.
Log in to reply
The limit definition is the historical definition. Perhaps you find it no longer up to snuff, but it works rather well. The definition you give for a general Banach algebra is inspired by, based on, and a generalization of precisely the same limit formula.
After all, exp ( x ) = n ∈ N ∑ n ! 1 x n is still a shorthand for a limit, exp ( x ) = N → ∞ lim n = 1 ∑ N n ! 1 x n whose convergence must be proven before the definition can be accepted.
(Also, I believe you forgot the factorial signs in the denominator?)
Log in to reply
I know it’s historical. But original attempts are often flawed or unclean. In latter years they get revised and approaches become cleaner, compacter and better. And who cares if the power series is a short hand for a limit of finite sums? I simply meant, that that particular kind of limit is ugly and tedious. By contrast a power series is a lot cleaner and simpler to deal with, in particular as one can easily check that it be absolutely convergent, and that it enjoys the properties of being an homomorphism, is continuous etc., none of which can be readily checked with the older definition.
what??? if each guest at the casino plays one round at the slot machine after all the guests have arrived, but David fills up his casino with a number of guests approaching infinity, that means no one can ever play the machine since they have to wait for everyone to arrive, which will not happen because there are infinite number of guests! that makes it 0% the way i see it. illuminate me please.
Log in to reply
Approaching infinity is not the same as infinity. The problem was carefully worded to avoid that sort of problem.
@Jeremy Galvagni spot on. The question is not what the probability is , but rather what it approaches .
okay. thanks guys
How do we know that here x=-1???
Log in to reply
The moderator’s comment is useful as step 2, not the start. The first step is: P [ none from $n$ ] = 1 ⋅ p n 0 ⋅ ( 1 − p n ) n = ( 1 − n 1 ) n = ( 1 + n − 1 ) n , where p n is the probability of 1 win. We then have P [ none from $n$ ] ⟶ e − 1 for n ⟶ ∞ as per the fact from Analysis.
Log in to reply
Could u pls explain why is it e^-1 when n approaches infinity!!!!!
Log in to reply
@Erica Phillips – Firstly, please kindly explain which part you don’t get:
It’s not clear what you don‘t get.
Log in to reply
@R Mathe – Thanks a lot for taking the trouble to explain!!!! I couldn't understand no. 2 and 3!!!!
Log in to reply
@Erica Phillips – For 2: increase your instagram-attention span, keep 1 in mind and literally just use your eyes ( 1 − n 1 ) n = ( 1 + n − 1 ) n so x = − 1 . Got it?
For 3: read a basic introductory text book on Analysis.
Relevant wiki: Probability - By Complement
Clearly, the probability for a finite number n of players to all lose is ( 1 − n 1 ) n , and we need to find its limit as n → ∞ .
We know that the very similar expression ( 1 + n 1 ) n tends to e as n → ∞ , so we manipulate our limit:
n → ∞ lim ( 1 − n 1 ) n = n → ∞ lim ( n n − 1 ) n = n → ∞ lim ( n − 1 n ) n 1 = n → ∞ lim ( 1 + n − 1 1 ) n 1 = n → ∞ lim ( 1 + n − 1 1 ) n − 1 1 ⋅ n → ∞ lim ( 1 + n − 1 1 ) 1 = e 1 ⋅ 1 = e 1
Relevant wiki: Probability - By Complement
Is a really really beautiful problem. I'm going to cry.
The answer is e Yes, the calculus constant. Yes, it is not a lie Follow me
Probability that guest 1 doesn't win
( 1 − 1 / n )
Probability that neither guest 1 nor 2 win
( 1 − 1 / n ) ( 1 − 1 / n ) = ( 1 − 1 / n ) 2
Probability that neither guest 1, guest 2 nor guest 3 win
( 1 − 1 / n ) ( 1 − 1 / n ) ( 1 − 1 / n ) . . . = ( 1 − 1 / n ) 3
Probability that neither guest 1, guest 2, guest 3... guest n-1 nor guest n win.
( 1 − 1 / n ) n
If you take the limit of that as n approaches infinity (for infinite guests) the result is 1/e
How is this possible? Follow me
Set A = ( 1 − 1 / n ) n
ln ( A ) = ln ( ( 1 − 1 / n ) n )
ln ( A ) = n ∗ ln ( 1 − 1 / n )
ln ( A ) = ln ( 1 − 1 / n ) / n − 1
Now, use L'Hopital to take the limit as n approaches infinity for ln(A) Differentiate the numerator and denominator of n − 1 ln ( 1 − 1 / n ) Then take the limit again
Thank you for the compliment! I have a few problems with your solution, though.
Do you know how to use LaTeX ? It would be much easier to read if you used it in the solution.
The limit as n approaches 0 is actually 1. I believe you meant "the limit as n approaches ∞ is e 1 ."
Finally, do you mind explaining exactly how to get the limit. I'm quite new to calculus, and I don't really know how to calculate the limit.
Log in to reply
Don't worry. Sorry for being late. I've used Latex and made it clearer
This isn't a good problem
Why? How about you do better.
this is unnecessarily messy. Avoid L'Hospital and at all costs—otherwise one has to first check if things are continuously differentiable, etc. It’s ugly!
Besides all the more calculus-like approaches I've read, there is a more statistically approach I'd like to share:
Since we have the probability of success, the number of trials and the constraint that there is only one shot to empty the machine, this problem can be analized as a series of Bernoulli trials, or most commonly known as binomial distribution since the outcome is dicotomical, I mean, you win or you loose.
Parameters of binomial distributions are number of trials (n) and probability of success (p), the problem states that n and p are related since "p" will be the inverse number of "n". With this data is easy to make some trials with different increasing "n" numbers and see that the binomial probability starts to point out to 0.3678 as you go higher in "n" hence lowering "p" as I show here:
Binomial probability calculation: P(n,p) P(10,1/10) = 0.387420... P(100,1/100) = 0.369729... P(1000,1/1000) = 0.368063... P(10000,1/10000) = 0.367897... P(100000,1/100000) = 0.367881... ... So... after a few calculations you can see the probability is approaching to 0.3678... as guests number approaches to infinity.
I know this solution is not as formal or elegant as the 1/e, but yet is another way to solve this riddle.
Hope you like it
This is the same thing. Under Bin ( n , p ) one has P [ 0 successes ] = ( [ m ] c n 0 ) p 0 ( 1 − p ) n = ( 1 − p ) n and since p = n 1 this simplifies to P [ 0 successes ] = ( 1 − n 1 ) n .
Disclaimer: A cheap, mathematically impure solution follows. It's your fault if you read it.
Use a scientific calculator, permitted in Lemma 1, to evaluate the probability of no one winning, found in Lemma 2, for n = 100,000. By Lemma 3, to two decimal places, report this value as your answer. Q.E.D.
Lemma 1: This item is scientific calculator-permitted.
Because the answer must be a rounded decimal rather than a mathematical expression, this item is calculator permitted. (I don't think we're expected to have the reciprocal of e memorized.) Specifically, a scientific calculator is permitted because four-function calculators generally don't have an e button.
Lemma 2: The probability of no one winning when there are n guests is ( 1 − n 1 ) n .
For no guest to win, all guests have to lose. The probability of the first guest winning, and thus the probability of any one guest winning given all previous guests lost, is n 1 . Thus, the probability of any given guest losing is n n − 1 . This has to occur for each guest, so the loss probability is raised to the nth power.
Lemma 3: To two decimal places, the probability of no one winning out of ∞ guests is equal to the probability of no one winning out of 100,000 guests.
This is provable, but we are given three opportunities to answer correctly, so it is reasonable to assume this lemma for the first attempt.
Well played. That's the main flaw with posting problems on Brilliant to the community. I like how you did it, but it's good to keep in mind that doing it the easy way doesn't let you learn as well.
We're looking for the limit of ( 1 − n 1 ) n as n → ∞ .
n → ∞ lim ( 1 − n 1 ) n = n → ∞ lim e n ln ( 1 − n 1 ) = x → 0 lim e x ln ( 1 − x ) = x → 0 lim e − − x ln ( 1 − x )
Now, knowing x → 0 lim x ln ( 1 + x ) = 1 , we get:
n → ∞ lim ( 1 − n 1 ) n = e − 1 .
Could you lot at Brilliant.org please program this, so as to allow for symbol input? Ie e ^( − 1 ) or exp ( − 1 ) or 1 / e , etc.? You would need to connect an interpreter (eg wolfram), but that should not be too problematic. Numerical approximations, where exact irrationals are demanded are unsatisfactory.
That's why they let us use multiple choice. When I originally wrote this problem, I asked "if the probability can be given as n 1 , then find n ." The answer was 2.718, which is the most common approximation for e . The staff at Brilliant changed my wording and my answer to make it like that.
I took a more pragmatic approach to summing an infinite sequence.
I expanded (1 - 1/n)^n using the first few binomial coefficients and ignoring anything with n in the denominator (which disappears as n becomes large) to get the infinite sum 1 – 1 + 1/2! – 1/3! + 1/4! – 1/5! + 1/6! ...
Then I took out my calculator and calculated each term, either adding or subtracting it from memory, like this: 1 / 2 M+ / 3 M– / 4 M+ / 5 M– / 6 M+ By the time I got to / 8 M+ the terms were small enough that I felt confident in rounding off 'MR' to 4 decimal places and submitting the answer.
you should learn a mathematical language. Octave and R are free, and will save you a lot of pain in such numerical experiments. Here’s the one line (
format long
resp.
options(...)
preamble to change the settings to display more decimals) one uses for example in Octave / R:
1 2 |
|
1 2 |
|
Sure, don't specify the number of digits you want in your answer.
This isn't a solution.
Problem Loading...
Note Loading...
Set Loading...
The probability is ( 1 − n 1 ) n . In general, n → ∞ lim ( 1 + n x ) n = e x ; in this case, x = − 1 so that the probability is e − 1 ≈ 0 . 3 6 8 .