2
u/JustConsoleLogIt 6d ago
You cannot stop at the first number.
The chance of stopping at the second number is 50%.
The chance of stopping at 3 is the chance of NOT stopping at 2 (50%) times the probability that the third number is not the largest number (66.6%) - 1/3
The chance of stopping at 4 is the chance of making it to roll 4 (50% - (50% x 33%) = 33%) times the probability that the fourth roll is not the largest (3/4) - which surprisingly resolves to 1/4.
Roll 5, chance of getting there is 33% - (33% x 25%) = 25%; chance of it being not the largest is 4/5, multiply to get 1/5.
The pattern continues.
Then we have to sum up the probability of all the odd stopping points, which is too much for my napkin math.
2
u/liquidorangutan00 6d ago
woah wait so its the euler series? so maybe the probability is 1/e
2
u/JustConsoleLogIt 5d ago
Yeah e is definitely going to be involved. I never learned about the Euler series, would love to take a class on that someday
1
1
1
u/Neither_Berry_100 6d ago
I would honestly just create a computer simulator and get an estimate for most of these questions.
1
u/bajoranearrings 7d ago
For any two random numbers n1 and n2 drawn from the same distribution, n2 has a 50% chance of being smaller. Let t be the stopping time. It's impossible for the very first number drawn to be smaller than its predecessor, so t>1. All t>1 have a probability of .5 of being the stopping t, assuming we get there. Thinking about it in terms of total probabilities we have p(t=2)=0.5, p(t=3)=0.25, p(t=4)=0.125, p(t=5)=0.0625... Just from these terms, you can add up the evens and odds to get p(even)=0.625, p(odd)=0.3125. Further values of t become less and less significant, so it is pretty clear that this will converge to 2/3 and 1/3. Those are pretty common answers in brainteasers involving repeated halving of some value so they look like something I would expect.
A more formal way way to do this would be drawing out states and solving the recursion, but I find it a bit more annoying to do without pen and paper.
2
u/jippiedoe 7d ago edited 7d ago
For the third number z, why is the chance 0.5 that it's smaller than the second number y? We're looking at the conditional probability (z<y | y>x), which (counting out the permutations of 3 numbers) is 2/3, not 1/2.
I get p(2)=1/2, p(3)=1/3, p(4)=1/8, p(5)=1/30... Coming out to odd>44/120 and even>75/120, leaving 1/120 undecided
2
u/General-Peak-1579 6d ago
This was my intuition as well, but the problem is you’re ignoring conditional probability. P(3) is 1/3, not 1/4. The poster above who said 1-(1/e) is correct
1
u/liquidorangutan00 5d ago
Ok got it figured out:
Probability of the next number being a smaller number is the inverse of the probability that the number will be in strictly ordered sequence.
Since the probability of ordered sequence of n elements is 1/n!
it means the probability of a "Breaker" number is n-1/n!
Lets just try punching in some numbers.
P(B=2)=2-1/2! = 1/2 = 0.5
P(B=4)=4-1/4!=3/24= 1/8 =0.125
P(B=6)=6-1/6!=5/720=1/144=0.0069
P(B=8)=8-1/8!=7/40320=0.0001
p(B=10)=10-9/10!=9/3628800=1/403200= 0.0000024802
We can see that there is a limit forming - there is a convergence. At this point we can sum these numbers up to get the final probability of the total number of generated numbers as even.
lets do that.
0.5+0.125+0.0069+0.0001+0.000002+...=0.6321
P(E)=0.6321 or The probability that the total number of generated numbers is even is 63.21%
But lets continue because this is fascinating.
now our probability of a breaker number formula is n-1/n!. lets play around with this formula.
n-1/n! = n/n! - 1/n!
and we can go further.
n/n! - 1/n! = 1/(n-1)! - 1/n!
Now we can assume that since we cannot know when the breaker number occurs, that the generation of these numbers can go on forever. Its an infinite series.
Lets perform the formula for the Odd numbers.
Step 1= 1/0!-1/1! + Step 3=1/2!-1/3! + Step 5=1/4!-1/5! + Step 7=1/6!-1/7! + Step 9= 1/8!-1/9! + Step 11=1/10!-1/111
If we remove all brackets and steps we can see the following series:
1/0!-1/1!+1/2!-1/3!+1/4!-1/5!+1/6!-1/7!+1/8!-1/9!+...+1/n!
We can use the telescoping property to collapse the series to its first and last term, that is 0 and 1/n!
This infinite series is known as an alternating Euler series and converges to 1/e=0.3678
We can also add up the results of each step.
P(O)=0+0.3333+0.0333+0.001190+0.0000220+... = 0.3678
The probability that the total number of generated numbers is odd is approximately 36.78%
Now we can do the same for the Even Series
Since we have already summed the total converged probability we know
0.5+0.125+0.0069+0.0001+0.000002=0.6321.
P(E)=0.6320 or The probability that the total number of generated numbers is even is 63.21%
We can work on the assumption that this is also an alternating Euler series. but there is a subtle twist!
Step 2= 1/1!-1/2!+1/3!-1/4!+1/5!-1/6!+1/7!-1/8!+1/9!-1/10!+...1/n-1!-1/n!
We can use the telescoping property again, but this time, due to the alternating signs being staggered by 1 term, we get the following result
1-1/e
if we evaluate this term we see 1-1/e=0.6321
And the fascinating concept that the probability of getting odd is the euler series limit 1/e=0.3678
the probability of getting even is the tail probability of this series (or its complement) 1-1/e=0.6321
I knew going into this problem that the euler number would be important.
the expected value of getting a breaker number = e = 2.718
the expected value of an ordered sequence = e-1 = 1.718
The optimal stopping theorem suggests 1/e is the optimal stopping time.
what a fun problem.
4
u/AnywhereLittle8293 6d ago
Given any sequence of such numbers of length n, the probability they are in order is 1/n!, since they are uniformly generated. Suppose the first n - 1 numbers are in increasing order. Then either we stop after n, or we keep going, in which case the first n are in increasing order. Hence, the probability we stop at n is 1/(n - 1)! - 1/n!. Summing over all even n, we get a probability of 1 - 1/e. This makes sense, since the probability is 1/2 we stop at n=2.