Decreasing numbers

Pick a random number (evenly distributed) between 0 and 1. Continue picking random numbers as long as they keep decreasing; stop picking when you obtain a number that is greater than the previous one you picked. What is the expected number of numbers you pick?

#Combinatorics #MathProblem #Math

Note by Jinay Patel
7 years, 6 months ago

No vote yet
3 votes

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

This is a non-combinatorial solution. The probability of successfully finding a run of at least length one is ∫01dx1\int_0^1 dx_1. It's easy to argue that the probability of successfully finding a run of at least length two is ∫01(∫0x2dx1)dx2\int_0^1 (\int_0^{x_2} dx_1) dx_2, and in general ∫01∫0xn⋯∫0x2dx1⋯dxn\int_0^1 \int_0^{x_n} \cdots \int_0^{x_2} dx_1 \cdots dx_n parameterizing this over xx as pn(x)=∫0x∫0xn⋯∫0x2dx1⋯dxnp_n(x) = \int_0^x \int_0^{x_n} \cdots \int_0^{x_2} dx_1 \cdots dx_n we soon find that p1(x)=x,p2(x)=x22,p3(x)=x33!,…,pk(x)=xkk!p_1(x) = x, p_2(x) = \frac{x^2}{2}, p_3(x) = \frac{x^3}{3!}, \dots, p_k(x) = \frac{x^k}{k!} such that the probability of encountering a run of at least length kk is 1k!\frac{1}{k!} (by instantiating pp at x=1x = 1). Let P[X=k]P[X = k] be the probability of encountering a run of exactly length kk, then P[X=k]=pk(1)−pk+1(1)=1k!−1(k+1)!=k(k+1)!P[X = k] = p_k(1) - p_{k+1}(1) = \frac{1}{k!} - \frac{1}{(k+1)!} = \frac{k}{(k+1)!} the generating function of the expected value is then just f(x)=∑kk2(k+1)!xkf(x) = \sum_k \frac{k^2}{(k+1)!}x^k evaluated at x=1x = 1; this is clearly analytic around x=0x = 0 and also around x=1x = 1, so we can manipulate this series keeping in mind that the OGF of ex=∑kxkk!e^x = \sum_k \frac{x^k}{k!}: f(x)=∑kk2(k+1)!xk=x−1∑k(k−1)2k!xk=x−1(∑kk2xkk!−2∑kxk(k−1)!+∑kxkk!)=x−1(∑kkxk(k−1)!−2x∑kxk−1(k−1)!+ex)=x−1(x∑k(k+1)xkk!−2xex+ex)=x2−x+1xex\begin{aligned} f(x) &= \sum_k \frac{k^2}{(k+1)!}x^k \\\\ &= x^{-1} \sum_k \frac{(k-1)^2}{k!} x^k \\\\ &= x^{-1} \left(\sum_k k^2 \frac{x^k}{k!} - 2\sum_k \frac{x^k}{(k-1)!} + \sum_k \frac{x^k}{k!}\right) \\\\ &= x^{-1} \left(\sum_k k \frac{x^k}{(k-1)!} - 2x\sum_k \frac{x^{k-1}}{(k-1)!} + e^x\right) \\\\ &= x^{-1} \left(x \sum_k (k+1) \frac{x^k}{k!} - 2xe^x + e^x\right) \\\\ &= \frac{x^2 - x + 1}{x} e^x\end{aligned} where E[X]=f(1)=eE[X] = f(1) = e

Lee Gao - 7 years, 6 months ago

Not sure whether this is correct, but let's try.

The probability that you will get the chance of getting the nnth number is 1(n−1)!\frac{1}{(n-1)!}, as you need the previous n−1n-1 numbers to be ordered decreasing and all (n−1)!(n-1)! possible orderings are equally likely. Summing over all nn gives the expected number:

∑n=1∞1(n−1)!=e\displaystyle\sum_{n=1}^\infty \dfrac{1}{(n-1)!} = \boxed{e}

Ivan Koswara - 7 years, 6 months ago
×

Problem Loading...

Note Loading...

Set Loading...