Hacker News Reader

Comment by Q_is_4_Quantum | Hacker News Reader

Fun read!

I have an extremely vague question; Is there one of these "stupid" ways of computing pi that doesn't involve an infeasible (to humans) infinity? I'm comparing to the "have pick people random integers and the probability they are coprime is 6/pi^2" method, which, again, to really work involves some poor people wasting an infinity of their lives. Your scheme does too from what I understand? Is this necessary?

Off topic: If you search for "quantum bernoulli factory" you will find some work I did that shows f(p)=2p is achievable if your "quantum coins" are presented as coherent superpositions instead of classical incoherent mixtures. Your work on exact sampling completely blew my mind (I'm a physicist!) while I was trying to undersantd that whole field.

View on HN

I'm not sure I understand your question. Given that it takes an infinite amount of time to write down the decimal expansion of pi, what might it mean to compute pi in finite time?

Yeah sorry, pretty vague, and I'm not sure what the "rules" precisely should be. Roughly I mean something that involves an infinite number of humans but where the workload per human is finite (perhaps only in expectation?) and each human only has to accept and pass on to the next one finite information. [This in the context of calculating pi via the "stupid method" of having each person choose a random integer and then using the probability of co-primeness being 6/pi^2].

My first thought does not achieve the task: expand pi/4 as a sum of positive rational numbers, then have each human use a couple of fair coins from their own Bernoulli factory to output a coin that is heads with probability given by their assigned rational number. The n'th human gets told the partial sum up to that point, flips their bernoulli factory coin and either terminates the protocol if they get heads, otherwise they adds their term to the partial sum they received and passes it on. The problem is the information content in the partial sums will grow with n.

ChatGPT suggests (and cites your paper):

Give the humans an order 1,2,3,…, and let a referee read them in that order. Person k tosses one fair coin and reports H/T. The referee stops at the first time the reported heads exceed the reported tails. If N people were consulted, choose one of those N uniformly at random. Output heads iff that chosen person’s coin was heads.

For a one-pass version: instead of storing the whole consulted prefix, the referee can keep a single “currently marked” consulted person, and when the k-th consulted coin arrives, replace the mark by that new person with probability 1/k. When the process stops, the marked person is uniform among the consulted ones.

Reply on news.ycombinator.com