<h2>Background</h2>
<p>This question is about generating random variates, in the form of their binary expansions, on restricted computing models. Specifically, the computing model is based on <em>pushdown automata</em> (finite-state machines with a stack) that are driven by flips of a coin and generate the binary expansion of a real number. This results in machines called <em>pushdown generators</em>, defined next.</p>
<h2>Pushdown Generators</h2>
<p>A <em>pushdown generator</em> has a finite set of <em>states</em> and a finite set of <em>stack symbols</em>, one of which is called EMPTY, and takes either a fair coin or a coin whose probability of heads is unknown. It starts with a given state and its stack starts with EMPTY. On each iteration:</p>
<ul>
<li>The automaton flips the coin.</li>
<li>Based on the coin flip (HEADS or TAILS), the current state, and the top stack symbol, it moves to a new state (or keeps it unchanged), replaces the top stack symbol with zero, one, or two symbols, and <em>optionally</em> outputs a base-N digit. Thus, there are three kinds of <em>transition rules</em>:
<ul>
<li>(<em>state</em>, <em>flip</em>, <em>symbol</em>) → (<em>digit</em>, <em>state2</em>, {<em>symbol2</em>}): move to <em>state2</em>, write <em>digit</em>, replace top stack symbol with same or different one.</li>
<li>(<em>state</em>, <em>flip</em>, <em>symbol</em>) → (<em>digit</em>, <em>state2</em>, {<em>symbol2</em>, <em>new</em>}): move to <em>state2</em>, write <em>digit</em>, replace top stack symbol with <em>symbol2</em>, then <em>push</em> a new symbol (<em>new</em>) onto the stack.</li>
<li>(<em>state</em>, <em>flip</em>, <em>symbol</em>) → (<em>digit</em>, <em>state2</em>, {}): move to <em>state2</em>, write <em>digit</em>, <em>pop</em> the top symbol from the stack.</li>
</ul>
</li>
</ul>
<p>In the transition rules above, <em>digit</em> is either a base-N digit or the empty string. Also, the machine terminates with probability 0, and rules that would cause the stack to be empty are not allowed. The infinite &quot;output&quot; of the machine is a real number <span class="math-container">$X$</span> in the interval [0, 1], in the form of the base-N digit expansion <code>0.dddddd...</code>, where <code>dddddd...</code> are the digits produced by the machine from left to right.</p>
<p>See also Yao 1985.</p>
<p>A <em>finite-state generator</em> (Knuth and Yao 1976) is the special case of a pushdown generator where the probability of heads is 1/2, each digit is either 0 or 1, rules can't push stack symbols, and only one stack symbol is used. (In other words, a finite-state generator is a <em>finite automaton</em> driven by unbiased random bits.)</p>
<h2>Distributions Computable by Pushdown Generators</h2>
<p>The question that interests me is which probability distributions of real numbers can be computed by pushdown generators, and how they can be constructed.</p>
<p>For example, a pushdown generator with a loop that outputs 0 or 1 at an equal chance produces a <em>uniform distribution</em>.</p>
<p>In this sense, there are existing results for finite-state generators. For example:</p>
<ul>
<li>Let <span class="math-container">$X$</span> be the random variable computable by a finite-state generator, and let <span class="math-container">$PDF(x)$</span> be the probability density function of <span class="math-container">$X$</span>. Then if <span class="math-container">$PDF(x)$</span> is infinitely differentiable on the open interval (0, 1), it must be a polynomial with rational coefficients and not equal 0 at any irrational point on (0, 1) (Kindler and Romik 2004).</li>
</ul>
<p>Also, I believe that the <a href="https://peteroupc.github.io/morealg.html#Finite_State_and_Pushdown_Generators" rel="nofollow noreferrer">following results</a> are true:</p>
<ol>
<li>Suppose a finite-state generator can generate a probability distribution that takes on finitely many values. Then: Each value occurs with a rational probability; and each value is either rational or transcendental. This belief is in view of the results of Adamczewski et al. 2020.</li>
<li>If the distribution function generated by a finite-state generator is continuous and algebraic on the open interval (0, 1), then that function is a piecewise polynomial function.</li>
</ol>
<h2>Questions</h2>
<p>The first question is whether the two results at the end of the previous section are true.</p>
<p>The following questions ask what kinds of distributions are possible with these generators (both when the coin driving the generators is fair, and when it has an unknown probability):</p>
<ol>
<li><p>Of the probability distributions that a finite-state generator can generate, what is the exact class of:</p>
<ul>
<li>Discrete distributions (those that cover a finite or countably infinite set of values)?</li>
<li>Absolutely continuous distributions (those with a probability density function such as the uniform or triangular distribution)?</li>
<li>Singular distributions (covering an uncountable but measure-zero set)?</li>
<li>Absolutely continuous distributions with <em>continuous</em> density functions?</li>
</ul>
</li>
<li><p>Same question as 1, but for pushdown generators.</p>
</li>
<li><p>Of the probability distributions that a pushdown generator can generate, what is the exact class of distributions with piecewise density functions whose pieces are infinitely differentiable? (The answer is known for finite-state generators.)</p>
</li>
</ol>
<h2>References</h2>
<ul>
<li><p>Knuth, Donald E. And Andrew Chi-Chih Yao. &quot;The complexity of nonuniform random number generation&quot;, in Algorithms and Complexity: New Directions and Recent Results, 1976.</p>
</li>
<li><p>Vatan, F., &quot;Distribution functions of probabilistic automata&quot;, in Proceedings of the thirty-third annual ACM symposium on Theory of computing (STOC '01), pp. 684-693, 2001.</p>
</li>
<li><p>Kindler, Guy and D. Romik, &quot;On distributions computable by random walks on graphs, &quot; SIAM Journal on Discrete Mathematics 17 (2004): 624-633.</p>
</li>
<li><p>Adamczewski, B., Cassaigne, J. And Le Gonidec, M., 2020. On the computational complexity of algebraic numbers: the Hartmanis–Stearns problem revisited. Transactions of the American Mathematical Society, 373(5), pp.3085-3115.</p>
</li>
<li><p>Yao, Andrew C. &quot;Context-free grammars and random number generation.&quot; In Combinatorial algorithms on words, pp. 357-361. Springer, Berlin, Heidelberg, 1985.</p>
</li>
</ul>

CC BY-SA 4.0
2021-12-28T10:45:28.750Z
Not quite answering the questions (I think), but maybe relevant to some: https://arxiv.org/abs/math/0304143
Clement C.
CC BY-SA 4.0
2021-12-28T11:07:33.877Z
@ClementC. : The paper you link to, in fact, relates to [another question of mine](https://cstheory.stackexchange.com/questions/50853/from-coin-flips-to-algebraic-functions-via-pushdown-automata).
Peter O.
<pr.probability>
Probability distributions generated by pushdown automata
Peter O.
# Probability distributions generated by pushdown automata

(Asked by: username_0 on 2021-12-06)

## Background

This question is about generating random variates, in the form of their binary expansions, on restricted computing models. Specifically, the computing model is based on *pushdown automata* (finite-state machines with a stack) that are driven by flips of a coin and generate the binary expansion of a real number. This results in machines called *pushdown generators*, defined next.

## Pushdown Generators

A *pushdown generator* has a finite set of *states* and a finite set of *stack symbols*, one of which is called EMPTY, and takes either a fair coin or a coin whose probability of heads is unknown. It starts with a given state and its stack starts with EMPTY. On each iteration:

* The automaton flips the coin.
* Based on the coin flip (HEADS or TAILS), the current state, and the top stack symbol, it moves to a new state (or keeps it unchanged), replaces the top stack symbol with zero, one, or two symbols, and *optionally* outputs a base-N digit. Thus, there are three kinds of *transition rules*:
  + (*state*, *flip*, *symbol*) → (*digit*, *state2*, {*symbol2*}): move to *state2*, write *digit*, replace top stack symbol with same or different one.
  + (*state*, *flip*, *symbol*) → (*digit*, *state2*, {*symbol2*, *new*}): move to *state2*, write *digit*, replace top stack symbol with *symbol2*, then *push* a new symbol (*new*) onto the stack.
  + (*state*, *flip*, *symbol*) → (*digit*, *state2*, {}): move to *state2*, write *digit*, *pop* the top symbol from the stack.

In the transition rules above, *digit* is either a base-N digit or the empty string. Also, the machine terminates with probability 0, and rules that would cause the stack to be empty are not allowed. The infinite "output" of the machine is a real number $X$ in the interval [0, 1], in the form of the base-N digit expansion `0.dddddd...`, where `dddddd...` are the digits produced by the machine from left to right.

See also Yao 1985.

A *finite-state generator* (Knuth and Yao 1976) is the special case of a pushdown generator where the probability of heads is 1/2, each digit is either 0 or 1, rules can't push stack symbols, and only one stack symbol is used. (In other words, a finite-state generator is a *finite automaton* driven by unbiased random bits.)

## Distributions Computable by Pushdown Generators

The question that interests me is which probability distributions of real numbers can be computed by pushdown generators, and how they can be constructed.

For example, a pushdown generator with a loop that outputs 0 or 1 at an equal chance produces a *uniform distribution*.

In this sense, there are existing results for finite-state generators. For example:

* Let $X$ be the random variable computable by a finite-state generator, and let $PDF(x)$ be the probability density function of $X$. Then if $PDF(x)$ is infinitely differentiable on the open interval (0, 1), it must be a polynomial with rational coefficients and not equal 0 at any irrational point on (0, 1) (Kindler and Romik 2004).

Also, I believe that the [following results](https://peteroupc.github.io/morealg.html#Finite_State_and_Pushdown_Generators) are true:

1. Suppose a finite-state generator can generate a probability distribution that takes on finitely many values. Then: Each value occurs with a rational probability; and each value is either rational or transcendental. This belief is in view of the results of Adamczewski et al. 2020.
2. If the distribution function generated by a finite-state generator is continuous and algebraic on the open interval (0, 1), then that function is a piecewise polynomial function.

## Questions

The first question is whether the two results at the end of the previous section are true.

The following questions ask what kinds of distributions are possible with these generators (both when the coin driving the generators is fair, and when it has an unknown probability):

1. Of the probability distributions that a finite-state generator can generate, what is the exact class of:

   * Discrete distributions (those that cover a finite or countably infinite set of values)?
   * Absolutely continuous distributions (those with a probability density function such as the uniform or triangular distribution)?
   * Singular distributions (covering an uncountable but measure-zero set)?
   * Absolutely continuous distributions with *continuous* density functions?
2. Same question as 1, but for pushdown generators.
3. Of the probability distributions that a pushdown generator can generate, what is the exact class of distributions with piecewise density functions whose pieces are infinitely differentiable? (The answer is known for finite-state generators.)

## References

* Knuth, Donald E. And Andrew Chi-Chih Yao. "The complexity of nonuniform random number generation", in Algorithms and Complexity: New Directions and Recent Results, 1976.
* Vatan, F., "Distribution functions of probabilistic automata", in Proceedings of the thirty-third annual ACM symposium on Theory of computing (STOC '01), pp. 684-693, 2001.
* Kindler, Guy and D. Romik, "On distributions computable by random walks on graphs, " SIAM Journal on Discrete Mathematics 17 (2004): 624-633.
* Adamczewski, B., Cassaigne, J. And Le Gonidec, M., 2020. On the computational complexity of algebraic numbers: the Hartmanis–Stearns problem revisited. Transactions of the American Mathematical Society, 373(5), pp.3085-3115.
* Yao, Andrew C. "Context-free grammars and random number generation." In Combinatorial algorithms on words, pp. 357-361. Springer, Berlin, Heidelberg, 1985.

**Tags:** pr.probability

> **Comments:**
> **username_1**: Not quite answering the questions (I think), but maybe relevant to some: https://arxiv.org/abs/math/0304143  
> **username_0**: @ClementC. : The paper you link to, in fact, relates to [another question of mine](https://cstheory.stackexchange.com/questions/50853/from-coin-flips-to-algebraic-functions-via-pushdown-automata).  

---

## 0 answers

