4 ms·

I think the sequence tends toward the edge at exp(-n), not 2^-n. The distance from the edge is a product of n I.I.D. variables, so the logarithm is a sum of n I

I think the sequence tends toward the edge at exp(-n), not 2^-n. The distance from the edge is a product of n I.I.D. variables, so the logarithm is a sum of n I.I.D. variables, and the central limit theorem gives us the result. You can confirm in a python terminal (or anything else) that the product of n `random()`s decreases more rapidly than 2^-n. So maybe there's some value in it after all :)

tbalsam 3y ago
How do you mean? I'm going based on the propagation of expectations through the system. The expectation of a uniform distribution is half the bound. Unless there's some math shenanigans going on, I believe that the expected expected value of a distribution drawn from distributions should be 1/2 * 1/2 * 1 in this case. Of course it's not a bound but right now I'm having a hard time determining otherwise. Is there a mathematical motivation for e^-n here? That seems an odd choice since the uniform distribution is 0-1 bounded generally. However I could understand if it emerges in a few conditions.
- sobellian 3y ago
  e shows up because we're doing an iterated product (of random variables, but still). If you look at the central limit theorem, sum(log(rand())) tends to N * E[log(rand())] for large N. Well, what's E[log(rand())]? -1! Like I said, it's fairly easy to test this in a python terminal. I encourage anyone who doubts me to try it :)
  - tbalsam 3y ago
    Alright, I tried it in the terminal and the numbers confirmed my earlier math. .5->.25->.125 mean as N->infinity. I chained the python uniform function like the above code in the originally linked post does and averaged the results. The snark to me and the other commenters is a bit unnecessary in either case. I'm not really sure where you're getting a natural log or an iterated product of random variables in this instance. Could you perhaps show where you're transforming uniform(uniform(uniform(uniform(0, 1)))) into the math you're showing above? I'm trying to follow along here but am having difficulty connecting your line of reasoning to the problem at hand.
    - sobellian 3y ago
      Not trying to be snarky by any means. I'm sorry if you interpreted it that way. I don't think the difference will show up for small N. This is an asymptotes thing. Try it for N = 100, that's what I did. For example: >>> np.product(np.random.random(100)) 5.469939152265385e-43 >>> 1 / np.e**100 3.7200759760208555e-44 >>> 1 / 2**100 7.888609052210118e-31 The underlying thing here is that random(random()) in this case is the same as random() * random(). So random(random(random(...))) is the same as random() * random() * random() and then the analysis goes on. And sure, random() * random() has a mean close to 1/4. But the dynamics change as N becomes large. Edit - and just in case you doubt whether random() * random() * ... is a valid way of doing this, I also just checked the laborious way of doing it: >>> def foo(n): ... result = 1.0 ... for _ in range(n): ... result = np.random.uniform(0, result) ... return result ... >>> foo(100) 1.4267531652344414e-46 >>> foo(100) 7.852496730908136e-49 >>> foo(100) 1.3216070221780724e-41
      - tbalsam 3y ago
        > I'm sorry if you interpreted it that way. is probably a good marker that it is time for me take my bow in this conversation, however, for an alternative approach I recommend SideQuark's comment on iterative random variables vs chains of multiplied random variables, which have different characteristics when defined as a sequence.
        sobellian 3y ago
        I checked his comment, I think he's incorrect on the approaches being different. Using my function `foo` that does the iterative approach, we can compare the distributions and they're fairly identical. >>> np.mean([foo(100) for _ in range(100000)]) 3.258425093913613e-33 >>> np.mean([np.product(np.random.random(100)) for _ in range(100000)]) 8.814732867008917e-33 (There's quite a bit of variance on a log scale, so 3 vs 8 is not a huge difference. I re-ran this and got varying numbers with both approaches. But the iterated code is very slow...) Note that the mean is actually quite a bit closer to 2^-100 even though the vast majority of numbers from either distribution fall below 2^-100. Even so, the mean for both is approximately a factor of 100 less than 2^-100. Suspicious! Although I think we've both burned enough time on this.
Nevermark 3y ago
Except that your logarithms can have any consistent base, including 2. So I don't think using a logarithm to introduce a special dependence on e is warranted in this case.
- sobellian 3y ago
  Well the expected value of E[log2(rand())] is not the same as E[log(rand())] and therein lies the difference. See my sibling comment. Like I said, you can check this in a python terminal.
SideQuark 3y ago
>The distance from the edge is a product of n I.I.D. variables It is not a product of random variables; it is an iterated random variable. The output of one influences those higher in the chain. Redo your python code with rand(rand(rand...))) not rand() * rand() * rand()... The expectation of composition of functions is not the composition of expectations, so there is some work to do. For uniform over [0,1] for the innermost item, it becomes an iterated integral, with value (1/2)^n.
- sobellian 3y ago
  I did redo it, and the distributions are identical. It's just a very heavily skewed distribution, so the expected value is not very intuitive. I still think even E[x] decreases faster than 2^-n though. See my other comments. Edit - Actually, I think E[x] = 2^-n, but showing this numerically for large n is impractical because of just how skewed the distribution is. It is simultaneously true that E[iter_rand(N)] = 2^-N and E[log(iter_rand(N))] = -N. Fun stuff :)
  - SideQuark 3y ago
    It's not about intuition. I computed it directly from the integral definition for expected value. I posted it elsewhere in the thread. It proves it for all N. Also, you keep using the new incorrect claim that r() * r() * ... * r() is the same as r(r(...r())..). They are not.
    - maxbond 3y ago
      random() * 5 is equivalent to random(5) (the former being the classic way to implement the latter). So why wouldn't random() * random() be equivalent to random(random())?
      - SideQuark 3y ago
        Multiplying by a constant commutes with expectation. Multiplying by a random variable does not. It may in some cases, but intuition is not the way to check it.

tbalsam 3y ago

How do you mean? I'm going based on the propagation of expectations through the system. The expectation of a uniform distribution is half the bound. Unless there's some math shenanigans going on, I believe that the expected expected value of a distribution drawn from distributions should be 1/2 * 1/2 * 1 in this case. Of course it's not a bound but right now I'm having a hard time determining otherwise. Is there a mathematical motivation for e^-n here? That seems an odd choice since the uniform distribution is 0-1 bounded generally. However I could understand if it emerges in a few conditions.

sobellian 3y ago
e shows up because we're doing an iterated product (of random variables, but still). If you look at the central limit theorem, sum(log(rand())) tends to N * E[log(rand())] for large N. Well, what's E[log(rand())]? -1! Like I said, it's fairly easy to test this in a python terminal. I encourage anyone who doubts me to try it :)
- tbalsam 3y ago
  Alright, I tried it in the terminal and the numbers confirmed my earlier math. .5->.25->.125 mean as N->infinity. I chained the python uniform function like the above code in the originally linked post does and averaged the results. The snark to me and the other commenters is a bit unnecessary in either case. I'm not really sure where you're getting a natural log or an iterated product of random variables in this instance. Could you perhaps show where you're transforming uniform(uniform(uniform(uniform(0, 1)))) into the math you're showing above? I'm trying to follow along here but am having difficulty connecting your line of reasoning to the problem at hand.
  - sobellian 3y ago
    Not trying to be snarky by any means. I'm sorry if you interpreted it that way. I don't think the difference will show up for small N. This is an asymptotes thing. Try it for N = 100, that's what I did. For example: >>> np.product(np.random.random(100)) 5.469939152265385e-43 >>> 1 / np.e**100 3.7200759760208555e-44 >>> 1 / 2**100 7.888609052210118e-31 The underlying thing here is that random(random()) in this case is the same as random() * random(). So random(random(random(...))) is the same as random() * random() * random() and then the analysis goes on. And sure, random() * random() has a mean close to 1/4. But the dynamics change as N becomes large. Edit - and just in case you doubt whether random() * random() * ... is a valid way of doing this, I also just checked the laborious way of doing it: >>> def foo(n): ... result = 1.0 ... for _ in range(n): ... result = np.random.uniform(0, result) ... return result ... >>> foo(100) 1.4267531652344414e-46 >>> foo(100) 7.852496730908136e-49 >>> foo(100) 1.3216070221780724e-41
    - tbalsam 3y ago
      > I'm sorry if you interpreted it that way. is probably a good marker that it is time for me take my bow in this conversation, however, for an alternative approach I recommend SideQuark's comment on iterative random variables vs chains of multiplied random variables, which have different characteristics when defined as a sequence.
      - sobellian 3y ago
        I checked his comment, I think he's incorrect on the approaches being different. Using my function `foo` that does the iterative approach, we can compare the distributions and they're fairly identical. >>> np.mean([foo(100) for _ in range(100000)]) 3.258425093913613e-33 >>> np.mean([np.product(np.random.random(100)) for _ in range(100000)]) 8.814732867008917e-33 (There's quite a bit of variance on a log scale, so 3 vs 8 is not a huge difference. I re-ran this and got varying numbers with both approaches. But the iterated code is very slow...) Note that the mean is actually quite a bit closer to 2^-100 even though the vast majority of numbers from either distribution fall below 2^-100. Even so, the mean for both is approximately a factor of 100 less than 2^-100. Suspicious! Although I think we've both burned enough time on this.

Nevermark 3y ago

Except that your logarithms can have any consistent base, including 2. So I don't think using a logarithm to introduce a special dependence on e is warranted in this case.

sobellian 3y ago
Well the expected value of E[log2(rand())] is not the same as E[log(rand())] and therein lies the difference. See my sibling comment. Like I said, you can check this in a python terminal.

SideQuark 3y ago

>The distance from the edge is a product of n I.I.D. variables It is not a product of random variables; it is an iterated random variable. The output of one influences those higher in the chain. Redo your python code with rand(rand(rand...))) not rand() * rand() * rand()... The expectation of composition of functions is not the composition of expectations, so there is some work to do. For uniform over [0,1] for the innermost item, it becomes an iterated integral, with value (1/2)^n.

sobellian 3y ago
I did redo it, and the distributions are identical. It's just a very heavily skewed distribution, so the expected value is not very intuitive. I still think even E[x] decreases faster than 2^-n though. See my other comments. Edit - Actually, I think E[x] = 2^-n, but showing this numerically for large n is impractical because of just how skewed the distribution is. It is simultaneously true that E[iter_rand(N)] = 2^-N and E[log(iter_rand(N))] = -N. Fun stuff :)
- SideQuark 3y ago
  It's not about intuition. I computed it directly from the integral definition for expected value. I posted it elsewhere in the thread. It proves it for all N. Also, you keep using the new incorrect claim that r() * r() * ... * r() is the same as r(r(...r())..). They are not.
  - maxbond 3y ago
    random() * 5 is equivalent to random(5) (the former being the classic way to implement the latter). So why wouldn't random() * random() be equivalent to random(random())?
    - SideQuark 3y ago
      Multiplying by a constant commutes with expectation. Multiplying by a random variable does not. It may in some cases, but intuition is not the way to check it.