11
\$\begingroup\$

Write a program that halts producing a random finite numerical output with probability 1. The expected value of the outputs of the program must be infinite.

For physical limits, you can assume your language and related functions use infinite precision numbers. E.g. for languages with random function providing range \$[0,1)\$, it returns a real in \$[0,1)\$. (Anyway I need to choose from 1/rnd and while(rnd)print(1))

Inspired by St. Petersburg paradox.

Shortest code wins. Would be quite small for lots of language though.


There are two easy-seen ways to do this, both are accepted given the question: (in Javascript)

_=>1/Math.random() // ∫₀¹1/xdx=∞
_=>{c='1';while(Math.random()<.5)c+='1';return c} // Not golfed to easier get understood for other language user, at least I try to
    // 1/2+11/4+111/8+1111/16+...=∞
\$\endgroup\$
13
  • 6
    \$\begingroup\$ The 1/random() answers don't have an infinite expected value since they are limited by the precision of the rng (i.e. that fraction has a finite maximum possible value) \$\endgroup\$ – Leo May 1 at 8:38
  • \$\begingroup\$ @Leo Default assumes infinity precision right? \$\endgroup\$ – l4m2 May 1 at 11:00
  • 3
    \$\begingroup\$ @Leo not only that, random() can output zero which would cause the program to give invalid output \$\endgroup\$ – Carmeister May 1 at 13:01
  • 3
    \$\begingroup\$ This question is good, but currently is not well defined. Since most random libraries are just pseudo-random ones, and probably rely on the current timestamp for a seed, should we assume that the program is run at a random time? \$\endgroup\$ – Trebor May 1 at 13:43
  • 1
    \$\begingroup\$ I am voting to reopen now that it has been clarified that the output must be finite, and that we can assume infinite precision. \$\endgroup\$ – Robin Ryder May 2 at 9:46

17 Answers 17

8
\$\begingroup\$

R, 9 bytes

rf(1,1,1)

Try it online!

Outputs a realization of the \$F(1,1)\$ distribution. The \$F(d_1,d_2)\$-distribution has infinite mean for \$d_2 \leq 2\$.

One way of defining the \$F(1,1)\$ distribution is as follows: let \$X_1,X_2\$ be independent \$\mathcal N(0,1)\$ random variables. Then \$\frac{X_1^2}{X_2^2}\sim F(1,1)\$.

Using the \$F\$ distribution comes out 1 byte shorter than the 2 more obvious solutions 1/runif(1) and rcauchy(1).

The plot below shows the evolution of the sample mean, for sample size ranging from 1 to 1e6; you can see that it diverges.

enter image description here


Alternate solution for the same byte count:

rt(1,1)^2

which outputs the square of a realization of Student's distribution \$t(1)\$. It has infinite expected value, since the \$t(1)\$ distribution has infinite variance. The square is needed to guarantee that the output is positive; without it, the expected value is undefined, since the realizations are often enough arbitrarily large positive or negative numbers.

\$\endgroup\$
5
  • \$\begingroup\$ Really nice! I think we were typing-in our answers at the same time, so I'm glad they came out with the same bytes (although I think yours is better...) \$\endgroup\$ – Dominic van Essen May 1 at 10:20
  • 1
    \$\begingroup\$ @DominicvanEssen I was happy it worked with rf, as we never get to use that function usually! \$\endgroup\$ – Robin Ryder May 1 at 13:46
  • \$\begingroup\$ Hmmm why does the $F(1,1)$ sample means have such strange jagged patterns in the graph? \$\endgroup\$ – Benjamin Wang May 2 at 0:52
  • 1
    \$\begingroup\$ @BenjaminWang That is what always occurs for the sample mean of independent and identically distributed random variables with infinite expected value. Intuitively: very occasionally, we obtain a huge realization \$X_i\$, which massively pushes the sample mean up. If the next realizations \$X_{i+1},X_{i+2},\ldots\$ are smaller, the sample mean will slowly decrease as the weight of \$X_i\$ decreases, until it jumps up the next time a huge realization occurs. \$\endgroup\$ – Robin Ryder May 2 at 8:48
  • 1
    \$\begingroup\$ @BenjaminWang On the other hand, if the expected value is finite, then the sample mean converges to it by the law of large numbers (see plot at the link). \$\endgroup\$ – Robin Ryder May 2 at 8:49
7
\$\begingroup\$

Jelly, 6 bytes

1ḤXḂ$¿

Try it online!

-1 byte thanks to Jonathan Allan

50% chance to output 1, 50% chance to output double this value. -2 bytes using a while loop inspired by Aaron Miller's answer.

Explanation

1
     ¿  While
  ..$
  X     Random integer from 1 to (current value)
   Ḃ    % 2 (this ensures 50% chance no matter how large the current value is - except if it's 1)
 Ḥ      Double the current value

Unfortunately, Jelly doesn't have a "random decimal from 0 to 1" built-in, otherwise this could be <random><reciprocal>.

Proof of validity

The probability to output \$2^x\$ is \$2^{-x-1}\$ for all \$x\in\mathbb{Z}^+\$. Therefore, the expected output is \$\sum\limits_{n=0}^\infty 2^n\cdot 2^{-n-1}=\sum\limits_{n=0}^\infty\frac12\rightarrow\infty\$

\$\endgroup\$
3
  • \$\begingroup\$ I'd suggest golfing to 2ḤX’$¿, but that seems to rapidly snowball out of control whenever it gets past 4... \$\endgroup\$ – Unrelated String May 1 at 10:53
  • \$\begingroup\$ 1ḤXḂ$¿ or 2ḤXḂ$¿ are the same thing just without \$x=0\$. \$\endgroup\$ – Jonathan Allan May 1 at 18:39
  • \$\begingroup\$ @JonathanAllan Ah, clever. Thanks. \$\endgroup\$ – hyper-neutrino May 1 at 18:40
6
\$\begingroup\$

Retina, 5 bytes

?+`
1

Try it online! Explanation:

?+`

Loop a random number of times with an exponential distribution...


1

Double the length. (Actually you get 2ⁿ-1, but that's still enough to diverge to infinity.)

\$\endgroup\$
4
\$\begingroup\$

Python 3, 37 bytes

from random import*
print(1/random())

Try it online!

I had a slightly cool solution but now this is just the trivial solution.

\$\endgroup\$
0
4
\$\begingroup\$

Vyxal, 6 7 3 bytes

Thanks to @hyper-neutrino for helping me to understand what expected output is.

Thanks to @Lyxal for porting a different answer than I did for -4 bytes.

∆ṘĖ

Try it Online!

Explanation:

∆Ṙ   # Random float in range [0.0, 1.0)
  Ė  # Reciprocal
     # Implicit output
\$\endgroup\$
1
4
\$\begingroup\$

Thue, 29 bytes

Edit: +9 bytes to fix issue spotted by @RossMillikan.

1::=.10
10::=~1
.0::=~0
::=
1

Try it online! The TIO interpreter requires a trailing newline, and outputs each digit on a different line, which is not required. Here is an interpreter without these restrictions.

Outputs in binary (meta link). Each step has a 50% chance to double the binary integer, or to start outputting it. The proven formula from other answers.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I don't think this is acceptable. It sounds like the chance of $n\ 1$s being output decreases as $2^{-n}$. In that case the expected value converges. Absent a startup transient it is just $2$. \$\endgroup\$ – Ross Millikan May 3 at 2:42
  • \$\begingroup\$ @RossMillikan Thank you, fixed. \$\endgroup\$ – Conor O'Brien May 3 at 19:52
1
\$\begingroup\$

C++ (gcc), 169 119 118 bytes

#include<bits/stdc++.h>
int main(){std::mt19937 p((uint64_t)new int);std::string s="1";while(p()%2)s+=s;std::cout<<s;}

Try it online!

This solution is directly derived from the linked paradox in the question. The output string is composed of 1 digits so technically it can be interpreted as a number.

The random number generator is seeded with the address of a heap variable. The address changes each time the program is run.

Another option is to use the address of a newly allocated heap variable: mt19937 rng((uint64_t) new char); (source)

\$\endgroup\$
1
\$\begingroup\$

Pyth, 4 bytes

/1OZ

Try it online!

/1   # 1 divided by
OZ   # Random float between 0 and 1
\$\endgroup\$
1
\$\begingroup\$

Bash, 24 bytes

echo 32767/$RANDOM|bc -l

Try it online!

Prints a random number between \$1\$ and \$\infty\$.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 7 bytes

1W‽²↑KA

Try it online! Link is to verbose version of code. Explanation:

1

Print 1.

W‽²

Repeat a random number of times with an exponential distribution...

↑KA

... duplicate the output.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ 52 bytes? More like 7 bytes. \$\endgroup\$ – lyxal May 1 at 8:36
  • 1
    \$\begingroup\$ @Lyxal Yeah, I normally remember to paste the succinct byte count at the same time as I paste the succinct code over the verbose code but I only got four hours of sleep last night :-( \$\endgroup\$ – Neil May 1 at 10:07
1
\$\begingroup\$

MATL, 3 bytes

1r/

Try it online!

This produces the output 1/x, where x is uniformly distributed on the interval (0,1). This has infinite mean.

\$\endgroup\$
1
\$\begingroup\$

Python 3, 31 bytes

from time import*
print(time())

Try it online!

The Python 3 random library uses the current time for a seed. Therefore, it is necessary to specify the random distribution of time that the program is run, to ensure that the simple 1/random() is valid. Depending on the yet-to-come specification, my answer may or may not be valid.

\$\endgroup\$
1
\$\begingroup\$

R, 9 bytes

1/rexp(1)

Try it online!

rexp(1) - a single random sample from an exponential distribution with a (default) rate parameter of 1 - is the shortest R random function call with a nonzero probability density at zero (there are other shorter random functions [rt and rf], but unfortunately they each lack default values for required parameters, so the function calls are no shorter*).

*Edit: no shorter, but both can be made just-as-short: see Robin Ryder's answer

\$\endgroup\$
2
  • \$\begingroup\$ For the second solution, you can use the fact that 1/0=Inf with e.g. 1/rpois(1,1) (12 bytes), which sometimes outputs Inf. \$\endgroup\$ – Robin Ryder May 2 at 9:05
  • \$\begingroup\$ @RobinRyder - Thanks - you're right, of course (even though I was trying to find a way to use a different approach to the R built-in random distributions). Anyway, it looks like both of these approaches are now outlawed by the new 'finite numerical output' rule... \$\endgroup\$ – Dominic van Essen May 2 at 22:08
1
\$\begingroup\$

Befunge-93, 8 7 bytes

2?.#*@#

Try it online!

This is basically just the St. Petersburg paradox. Every time the pointer reaches the ? and goes either left or right, it has a 1/2 chance of doubling the top of the stack and a 1/2 chance of just outputting the top of the stack and halting.

Explanation of the code:

2?.#*@#

2        Push 2 onto the stack.
 ?       Change the direction of the pointer to a random direction:
2   *      If left, double the top of the stack.
  .  @     If right, output the top of the stack and halt.
 ?         If up/down, the pointer returns to the ?.
\$\endgroup\$
0
\$\begingroup\$

><>, 3 bytes

1nx

Try it online!

Has an infinite expected value, due to diverging more quickly than exponentially more unlikely repunits. Will nevertheless always terminate when it empties its own stack, when the random trampoline takes more left turns than right turns.

\$\endgroup\$
0
\$\begingroup\$

Random Brainfuck, 5 bytes

+[?.]

Throw a D256 until you throw a 0

Try it online!

\$\endgroup\$
-1
\$\begingroup\$

JavaScript (V8), 11 bytes

Of course, I'm not serious.

_=>Infinity

Try it online!

Infinity is a numerical type:

console.log(typeof Infinity)

\$\endgroup\$
9
  • 2
    \$\begingroup\$ Does this actually generate "random numerical output"? When I re-run it, it seems to output 'Infinity' every time... \$\endgroup\$ – Dominic van Essen May 1 at 12:23
  • 1
    \$\begingroup\$ @DominicvanEssen Fine. _=>Infinity+Math.random() \$\endgroup\$ – EnderShadow8 May 1 at 12:27
  • \$\begingroup\$ @EnderShadow8 infinity plus any number between 0 and 1 is Infinity \$\endgroup\$ – Recursive Co. May 1 at 12:38
  • 1
    \$\begingroup\$ @ophact r/woooosh \$\endgroup\$ – EnderShadow8 May 1 at 13:34
  • 2
    \$\begingroup\$ @EnderShadow8 In Javascript 1/0 is Infinity while 0/0 is NaN. \$\endgroup\$ – Etheryte May 1 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.