Hacker News Reader

Comment by SideQuark | Hacker News Reader

Lots of math all over the place computing the expected value :)

So, here's a derivation: if rand(x) returns uniformly a real in [0,x) or equivalently for expected value, in [0,x], then here are the first few iteration expected values from which you can see the general answer. 1 term

    E(r) = (1/1) * Integral_0^1 x_0 dx_0 = (x_0^2/2) from 0 to 1 = 1/2

2 terms

    E(r(r)) = (1/1) * Int_0^1  (1/x_0) Int_0^x_0 x_1 dx_1 dx_0 = 1/4

3 terms:

    E(r(r(r))) = (1/1) * Int_0^1 (1/x_0) Int_0^x_0 (1/x_1) Int_0^x_1 x_2 dx_2 dx_1 dx_0 = 1/8

And so on. The nth term is exactly (1/2)^n

View on HN

I think I understand, but I also saw a comment above that specifically says (having done 3 iterations)

  The resulting distribution is not equal to random()^3, because e.g. the probability that all 3 random calls give you a number <0.5 is only 0.125.

https://news.ycombinator.com/item?id=35954931

Any thoughts? Am I mixing up two unrelated things?

The re

Very well explained, that made it click for me, thanks!

Even simpler, every time you sample random you get the same number of bits of entropy. Sampling once and then cubing spreads the same entropy bits over the interval. Cubing thrice spreads 3x the entropy into the reachable area. Thus you know this guy is doing no net favor to the world.

There's a difference between taking a random() and then cubing it, and taking three different random()s and multiplying them together. The EV of the first is 1/4, whereas the EV of the second is 1/8.

You can prove the EVs for yourself, but an intuitive way to think about why the EV of the first is twice as much as the second scenario is to consider their probability density functions. When you cube a single random variable, the resulting PDF is skewed towards lower values, but not as dramatically as when you multiply three separate random variables together.

> not equal to random()^3

Let's clarify what this means, that's probably the confusion. Here's python code

from random import random

x = random()

z = x*3

That's the random()^3 term. But let's try to differentiate this

a,b,c = random(), random(), random()

z = a * b * c

You may notice that the z's don't match in these cases. The key difference is that in the exponent version we draw a single random variable (remember it is >0 and <1). Then we take this value and multiply it by itself 3 times (cube). This corresponds to rolling a dice once and then multiplying the value by itself 3 times (x*x*x). But in the other case we have 3 independent random variables. This is like rolling the dice 3 times and multiplying the 3 different values. Clearly the possibilities of achieving a specific number are going to be different in these situations. What I suggest doing is plotting a histogram of this data (10k samples with 1k bins will be sufficient). Make 3 plots (preferably using subplot). I went ahead and did this for you[0]!

== Worked out ==

Let's actually simplify this a bit[1] and work it out by hand: we'll look at r^2 vs r*r (where r is an independent random uniform variable). We'll look at an upper bound and the middle.

So in r^2 90% of our r's will be under 0.9, with 9% of values in r^2 being <0.81. Now the middle case, r=0.5. Half our values are above 0.25, and half are <0.25. From this we can see 3 bins: <0.25/0.25 - 0.81/>0.81. 50% of our data is <0.25, 40% is between 0.25 and 0.81, and 10% is >0.81. We can tell from these three bins that our data is pushed towards 0 and we have a long tail.

Now let's look at the r*r case. We'll need to write out more possibilities because we have more cases. 0.9*0.9=0.81, 0.5*0.9=0.9*0.5=0.45, 0.5*0.5=0.25. You see we've added an extra bin because the r's don't have to be the same (lucky for symmetry though). Our bins are <0.25/0.25-0.45/0.45-0.81/>0.81. This now corresponds to 25% of the data, 20% of the data, 36% of the data, and 19%. If we look at these bins, we can see that this is flatter. In the r^2 case we had 50% of our data under 0.25 but in the r*r case we only have 25%! Similarly in the r^2 case we had 10% of our data >0.81 compared to 19%! So we should expect a similar shape but flatter.

I hope this helps.

== Quiz to test your understanding: ==

We're going to make a bet and I'm giving you two options. In the first option I'll allow you to roll a dice, take the value, and cube it. In the second case I'll allow you to roll 3 dice and multiply all values. You win if your result is >63. Which option do you choose? What if you win when the result is <8? (I'm sure someone will post an answer)

[0] https://i.imgur.com/gQ5uqED.png

[1] I started writing out the full case but it got long winded so I deleted. I can redo if needed.

Reply on news.ycombinator.com