13
\$\begingroup\$

Consider the following probability puzzle.

We start with a string of bits all set to 0. At each step we choose a bit uniformly and independently at random and flip it. The value your code has to compute is the probability of getting to the all 1s bit string before you get back to the all 0s bit string.

Let \$n\$ be the length of the starting bitstring.

Examples:

\$n = 1\$. The output is 1.

\$n = 2\$. The output is 1/2.

\$n = 3\$. The output is 2/5.

The remaining outputs for n up to 20 are:

3/8,3/8,5/13,60/151,105/256,35/83,63/146,630/1433,1155/2588,6930/15341,12870/28211,24024/52235,9009/19456,9009/19345,17017/36362,306306/651745,2909907/6168632.

Your code should take \$n\$ as the input and give the right output. The output must be exact, for example as a fraction. There is no need for the fraction to be fully reduced.

Your code must work for \$n\$ up to at least \$20\$ and run without timing out on TIO .

Improve this question
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Can we take n as zero-indexed? \$\endgroup\$
    – Manish Kundu
    Mar 28, 2021 at 18:03
  • \$\begingroup\$ @ManishKundu Yes that's fine \$\endgroup\$
    – user7467
    Mar 28, 2021 at 18:10
  • 2
    \$\begingroup\$ This seems to be \$\frac{A046826}{A046825}\$. A046826 / A046825. \$\endgroup\$
    – tsh
    Mar 29, 2021 at 2:32
  • \$\begingroup\$ Is it allowed to output in factorial base? \$\endgroup\$
    – Command Master
    Mar 29, 2021 at 9:55
  • 5
    \$\begingroup\$ @CommandMaster I don't know what that means but I think the answer is no. \$\endgroup\$
    – user7467
    Mar 29, 2021 at 10:11

11 Answers 11

Reset to default
10
\$\begingroup\$

Wolfram Language (Mathematica), 25 bytes

$$n! \div \left( \sum ^n _{k=0} k!(n-k)! \right)$$

#!/Sum[k!(#-k)!,{k,0,#}]&

Try it online!

-4 bytes from @ovs

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Exactly the same answer I had :)) \$\endgroup\$
    – Manish Kundu
    Mar 28, 2021 at 18:10
  • \$\begingroup\$ 26 bytes by using the definition of the binomial coefficient. \$\endgroup\$
    – ovs
    Mar 28, 2021 at 18:23
  • 1
    \$\begingroup\$ What's the origin of this formula? I was going to approach this as finding the eigenvectors of a matrix representing the transition probabilities... is there a connection to that or is this an entirely different method? \$\endgroup\$
    – Jonah
    Mar 28, 2021 at 19:23
  • 1
    \$\begingroup\$ @Jonah oeis.org/A046825 \$\endgroup\$
    – ZaMoC
    Mar 28, 2021 at 19:41
  • \$\begingroup\$ @Jonah a linear algebra solution would be great but might be hard to do exactly? \$\endgroup\$
    – user7467
    Mar 28, 2021 at 21:12
7
\$\begingroup\$

M, 7 6 bytes

cRİS‘İ

Try it online!

M is Jelly's more mathematical (and out-of-date) sibling. While Jelly uses floating point maths, M uses rational numbers where possible.

Similarly to J42161217's Mathematica answer, we use the binomial coefficient. This calculates the exact value of

$$1 \div \left(1 + \sum ^n _{k=1} \frac 1 {\binom n k}\right)$$

How it works

cRİS‘İ - Main link. Takes n on the left
 R     - Range [1, 2, ..., n]
c      - Calculate nCk for each k
  İ    - Inverse; Get the reciprocal of each
   S   - Sum
    ‘  - Increment, to account for nC0
     İ - Inverse; Get the reciprocal again
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Can you explain why this formula is correct? \$\endgroup\$
    – user7467
    Mar 28, 2021 at 19:14
  • 1
    \$\begingroup\$ @Anush No, my understanding of the maths behind this question isn't good enough. But, if J42161217's answer is valid, then so is mine \$\endgroup\$
    – caird coinheringaahin g ♦
    Mar 28, 2021 at 19:15
6
\$\begingroup\$

Factor + math.combinatorics math.unicode, 45 43 bytes

[ dup [0,b] [ nCk -1 ^ ] with map Σ -1 ^ ]

Try it online!

This uses the formula graciously offered in the following M answer.

Edit: use -1 ^ instead of recip since it's 1 byte shorter.

Explanation:

It's a quotation (anonymous function) that takes an (0-indexed) integer as input and returns a number (probably a ratio) as output. Assuming 4 is on top of the data stack when this quotation is called...

  • dup Duplicate TOS (top of stack). Stack: 4 4
  • [0,b] Create a range object from the number at TOS (0 to 4 inclusive). Stack: 4 T{ range f 0 5 1 }
  • [ nCk -1 ^ ] Push a quotation to the data stack to be used later by with. Stack: 4 T{ range f 0 5 1 } [ nCk -1 ^ ]
  • with Partial application on the left. It sticks that 4 that's been lingering on the data stack into the quotation that's about to be used by map in such a way that it comes before the range elements being mapped over. Stack: T{ range f 0 5 1 } [ 4 [ nCk -1 ^ ] swapd call ]
  • map Apply a quotation to each element of a sequence, collecting the results into a sequence of the same size. (Inside the quotation now...) Stack: 4 0
  • nCk Outputs the total number of unique combinations of size TOS that can be taken from a set of size NOS (next on stack). Also known as 4 choose 0. Stack: 1
  • -1 ^ Take the reciprocal. Shorter than 1 swap / and recip. Stack: 1
  • Now map applies the quotation to each element of the range sequence and we end up with... Stack: { 1 1/4 1/6 1/4 1 }
  • Σ Take the sum of a sequence. Stack: 2+2/3
  • -1 ^ Take the reciprocal. Stack: 3/8.
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nice! I've found a same-length alternative using locals (maybe you can find some other golf in this): Try it online! \$\endgroup\$
    – Leo
    Mar 29, 2021 at 0:54
5
\$\begingroup\$

Python 2, 85 bytes

n=input()
B=9**9;p=1;q=0
for i in range(n+1):x=(B+1)**n/B**i%B;q=p+x*q;p*=x
print p,q

Try it online!

A nice solution made uglier by the requirement that we output an exact fraction. With floats, it looks like:

62 bytes

lambda n,B=9**9:1/sum(1./((B+1)**n/B**i%B)for i in range(n+1))

Try it online!

We use the formula $$ \left(\sum ^n _{i=0} {\binom n i}^{-1}\right)^{-1}$$ and compute the binomials coefficients using this trick. This gives us a sleeves-rolled-up solution without any imports or built-ins for factorial or binomial coefficients.

The original code implements fraction arithmetic by updating the fraction p/q. It might be shortenable but I don't really care to golf it. A more direct but longer conversion uses the fractions library:

94 bytes

from fractions import*
lambda n,B=9**9:1/sum(1/Fraction(((B+1)**n/B**i%B))for i in range(n+1))

Try it online!

This replace-and-evaluate monstrosity would save bytes over the floats version, but it gives wrong answers where some \$\binom{n}{i}\$ ends in a zero digit.

56 bytes, doesn't work

lambda n:1/eval(`(10**17+1)**n`.replace('0'*9,'e0+1./'))

Try it online!

Improve this answer
\$\endgroup\$
0
4
\$\begingroup\$

Python 2,  83  77 bytes

-4 thanks to dingledooper! (from math import factorial as f -> f=lambda n:0**n or n*f(n-1))
-2 thanks to ovs! (0**n or -> n<1or)

f=lambda n:n<1or n*f(n-1)
lambda n:(f(n),sum(f(i)*f(n-i)for i in range(n+1)))

An unnamed function accepting n that returns a tuple (numerator, denominator) (not simplified).

Try it online! (1-20, including simplified fraction)

Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ 80 bytes \$\endgroup\$
    – dingledooper
    Mar 29, 2021 at 0:09
  • \$\begingroup\$ Thanks @dingledooper! \$\endgroup\$
    – Jonathan Allan
    Mar 29, 2021 at 0:30
  • 1
    \$\begingroup\$ It looks like it's shorter to calculate factorial manually \$\endgroup\$
    – dingledooper
    Mar 29, 2021 at 3:20
  • \$\begingroup\$ @dingledooper I should really have tried that too. Thanks! \$\endgroup\$
    – Jonathan Allan
    Mar 29, 2021 at 12:21
  • \$\begingroup\$ n<1or ... saves 2 bytes in the factorial function. If you don't like the (True, 1) output for 0, change f(n) to +f(n) in the main function. \$\endgroup\$
    – ovs
    Mar 29, 2021 at 12:58
2
\$\begingroup\$

JavaScript (Node.js), 61 bytes

n=>[(g=n=>n?n*g(~-n):1)(n),(h=k=>g(k)*g(n-k)+(k&&h(~-k)))(n)]

Try it online!

Search the sample output given by OP on OEIS, and you may find out A046825. Use the formula given on that page:

$$ \begin{split} f(n) & = \frac{1}{\sum_{k=0}^{n}\frac{1}{C_n\left(k\right)}} \\ & = \frac{1}{\sum_{k=0}^{n}\frac{k!\left(n-k\right)!}{n!}} \\ & = \frac{n!}{\sum_{k=0}^{n}k!\left(n-k\right)!} \end{split} $$

It may need +1 byte (change 1 to 1n) if larger (\$n>21\$) testcases is required.

Note: I have no idea why it works.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ How can I improve the explanation in my answer as to how that formula works? \$\endgroup\$
    – Neil
    Mar 29, 2021 at 9:53
  • 1
    \$\begingroup\$ @Neil I don't know. Maybe give a proof as what math textbooks do. And everyone would give up understanding it. :) \$\endgroup\$
    – tsh
    Mar 29, 2021 at 10:14
  • \$\begingroup\$ No, I didn't mean a proof, I meant that I found a sequence with a comment that gives the direct solution to the problem in terms of that sequence, rather than guessing the formula from the sequence that turns up when you search the terms. \$\endgroup\$
    – Neil
    Mar 29, 2021 at 10:43
2
\$\begingroup\$

R, 45 40 bytes

Using J42161217's Mathematica answer, and following Guiseppe's astounding improvement,

   function(n,`!`=gamma)c(!n,(!1:n)%*%!n:1)

Try it online!

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 40 bytes - quite apart from the nice effect of using ! as the factorial, ! has lower precedence than * (where unary - has higher precedence) so we can remove one pair of parentheses. \$\endgroup\$
    – Giuseppe
    Mar 29, 2021 at 19:32
2
\$\begingroup\$

Sledgehammer, 11 bytes

⣸⢄⠔⢅⢉⢟⣹⢤⢟⡹⣽

Decompresses into this Wolfram Language function:

Tr[Binomial[#1, Range[0, #1]]^(-1)]^(-1) &

Try it online!

Returns 0-indexed fractions.

Can't say I have much to add in terms of golfing, but as, judging by the other answers, no one seems to know why the formula works, I can offer an explanation:

Let \$P_n(k)\$ be the probability that, following the given algorithm, a string of all ones is reached before a string of all zeroes, starting from an \$n\$-length bitstring which has \$k\$ ones. We can immediately see that \$P_n(0)=0\$ and \$P_n(n)=1\$. The desired value is \$P_n(1)\$: one bit is flipped on first.

When we flip a bit at random, there is a \$\frac kn\$ chance that bit was a one, and a \$\frac{n-k}n\$ chance it was a zero. Therefore, for \$0<k<n\$, we have \$P_n(k)=\frac knP_n(k-1)+\frac{n-k}nP_n(k+1)\$. In other words, \$P_n(k)\$ is the weighted average of \$P_n(k-1)\$ and \$P_n(k+1)\$, with weights \$k\$ and \$n-k\$, respectively.
If we denote \$P_n(x)-P_n(x-1)\$ by \$\Delta P_n(x)\$, we can equivalently say \$\Delta P_n(k+1)=\frac{k}{n-k}\Delta P_n(k)\$.

Checking some values of \$k\$:

  • \$\Delta P_n(2)=\frac 1{n-1}\Delta P_n(1)\$
  • \$\Delta P_n(3)=\frac 2{n-2}\Delta P_n(2)=\frac{1\cdot 2}{(n-1)(n-2)}\Delta P_n(1)\$
  • And, in general, \$\Delta P_n(k)=\frac{(k-1)!(n-k)!}{(n-1)!}\Delta P_n(1)={n-1\choose k-1}^{-1}\Delta P_n(1)\$ by induction.

Now, consider the telescoping sum
\$P_n(n)-P_n(0)=1=\sum_{k=1}^n\Delta P_n(k)=\sum_{k=1}^n{n-1\choose k-1}^{-1}\Delta P_n(1)\$.
Solving, we get our formula \$\Delta P_n(1)=P_n(1)=\left(\sum_{k=1}^n{n-1\choose k-1}^{-1}\right)^{-1}\$.

The zero-indexed form is slightly more compact: \$P_{n+1}(1)=\left(\sum_{k=0}^n{n\choose k}^{-1}\right)^{-1}\$.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ This is great! Thank you \$\endgroup\$
    – user7467
    Oct 16, 2021 at 8:03
1
\$\begingroup\$

Jelly, 7 bytes

5 bytes with cŻİSİ if we may print with floating point inaccuracy.

cŻPṄ:ƊS

A full program printing a numerator and then a denominator (not simplified).

Try it online!

How?

cŻPṄ:ƊS - Main Link: integer, n
 Ż      - zero range -> [0,1,2,...,n]
c       - (n) choose (that) (vectorises) -> [1, n, ..., n, 1] (Pascal row n)
     Ɗ  - last three links as a monad - f(Pascal row n):
  P     -   product (of Pascal row n)
   Ṅ    -   print (product) and a newline; yield (product)
    :   -   (product) integer divide (Pascal row n) (vectorises)
      S -   sum
        - implicit print
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 24 bytes

ＦＮ⊞υ∨¬ι×⌈υιＩ⟦⌈υΣＥ⮌υ×ι§υκ

Try it online! Link is to verbose version of code. Explanation: Flipping n random bits in a string is equivalent to a random walk over the vertices of an n-dimensional hypercube; moving along an edge corresponds to flipping one of the bits. The starting point is the string of all 0s and the diagonally opposite vertex is the string of all 1s. The probability that it visits that vertex before it returns to the starting point is then documented in the linked page as being (n-1)!/A003149(n-1).

ＦＮ⊞υ∨¬ι×⌈υι

Input n and calculate the factorials up to n-1.

Ｉ⟦⌈υΣＥ⮌υ×ι§υκ

Output (n-1)! as the numerator and the sum of the termwise product of the factorials with their reverse as the denominator.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 6 9 8 bytes

-1 thanks to Command Master.

!,Ý!Â*O,

Try it online!

!,Ý!Â*O,  # full program
 ,        # output...
          # implicit input...
!         # factorial
       ,  # output...
      O   # sum of...
  Ý       # [0, 1, 2, ...,
          # ..., implicit input...
  Ý       # ]...
          # (implicit) with each element...
   !      # factorial...
          # (implicit) with each element...
     *    # multiplied by...
          # (implicit) corresponding element in...
  Ý       # [0, 1, 2, ...,
          # ..., implicit input...
  Ý       # ]...
          # (implicit) with each element...
   !      # factorial...
    Â     # reversed
Improve this answer
\$\endgroup\$
7
  • 2
    \$\begingroup\$ "The output must be exact, for example as a fraction." Unless 05AB1E uses exact reciprocals, this is an invalid answer \$\endgroup\$
    – caird coinheringaahin g ♦
    Mar 29, 2021 at 1:01
  • \$\begingroup\$ @ChartZBelatedly It does give exact output. \$\endgroup\$
    – Makonede
    Mar 29, 2021 at 1:15
  • 1
    \$\begingroup\$ 05AB1E uses floating point arithmetic, therefore the output may look exact (up to a certain number of decimal places), but it will fail for certain inputs, due to floating point issues \$\endgroup\$
    – caird coinheringaahin g ♦
    Mar 29, 2021 at 1:23
  • 1
    \$\begingroup\$ Additionally, I can confirm that reciprocal is inexact, through testing and digging through the source code (it's just 1 / to_number(a) and to_number gives normal number types, and I don't believe Elixir uses exact arithmetic) \$\endgroup\$
    – hyper-neutrino ♦
    Mar 29, 2021 at 1:24
  • 1
    \$\begingroup\$ !,Ý!Â*O, 8 bytes \$\endgroup\$
    – Command Master
    Mar 29, 2021 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.