Calculate the probability of getting to the target first (exactly)

Question

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 .

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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!

Answer 5

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)

Answer 6

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.

Answer 7

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!

Answer 8

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}\$.

Answer 9

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

Answer 10

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.

Answer 11

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