<p>You can still argue by counting. No matter how randomness is used, there is a way to fix the randomness in such a way that the function is computed correctly deterministically on at least $\frac{2}{3}2^n$ inputs. Thus assuming any function can be computed with error at most $\frac{1}{3}$ by some circuit in size $S$, any function can be described by a circuit of size $S$ together with a set of at most size $\frac{1}{3}2^n$ of inputs where the answer is incorrect.</p>

CC BY-SA 3.0
2013-01-16T12:19:36.003Z
I am not sure if I completely understand your answer.  

I think there is a problem that (for 2pfa-s) I measure the device size $S$ by the number of states, but it doesn't imply any bound on how many bits do I need to describe the probabilistic transition function.


And I don't see how can you determinize the transition function without a blowup in the number of states as each transition can be used many times during one run of the automaton.
kbkb
CC BY-SA 3.0
2013-01-16T12:55:03.297Z
Yes I believe you misunderstand. After fixing the randomness there is no randomness left.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2013-01-21T09:53:10.507Z
Now I see. This approach indeed works for circuits because every gate in a computation is used only once and you can fix it. However it does not translate to 2-way probabilistic finite automata easily because there every state (and therefore also the transition function) can be used many times in a single computation.
kbkb
CC BY-SA 3.0
2013-01-21T12:07:27.957Z
I was indeed thinking about circuits, and I am not sure what to do with automata. I have changed my answer to avoid claiming too much.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2013-01-21T14:50:41.607Z
Actually, can you not make it work for automata in the following way: Since you care only about strings of length n, each state will be visited at most n times. Then in the "automata" obtained after fixing randomness, each state will have a list of n next-state transition functions. Each time a state is visited, the next unused transition function is used.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2013-01-22T15:11:29.247Z
No, these are 2-way automata that can move back and forth the input (transitions are a function from a state and a symbol to a new state and {left, no_move, right}. The last part corresponds to the movement of the head. In probabilistic case it's a function from state, symbol, state, {L,N,R} to [0,1]) so each input symbol can be visited more than once (in deterministic case no more than the number of states (otherwise it would cycle), but that's not true in the probabilistic case).
kbkb
CC BY-SA 3.0
2013-01-15T17:11:12.553Z
2013-01-21T12:06:15.667Z
2013-01-21T12:06:15.667Z
Kristoffer Arnsfelt Hansen
<p>If we consider circuits with arbitrary binary logic gates one can prove by a counting argument that there exists a Boolean function on $n$ variables that require a circuit of size $ \Theta \left( 2^n/n \right) $ (in fact almost all of them are such).</p>

<p>This follows from the fact that there are $2^{2^n}$ Boolean functions on $n$ variables and only at most $16^k (k+n+1)^{2k} k / k!$ different Boolean functions on $n$ variables can be computed by circuits of size $k$ (for each gate there are $16$ possibilities to choose its type and $b+n+1$ possibilities to choose its two predesscors (the other $k-1$ gates, $n$ variables and $2$ constants), $k$ possibilities to choose the final gate and there are $k!$ possibilities to renumber the gates)</p>

<p>I am interested in probabilistic circuits in the following (nonstandard) sense - using gates which can have arbitrary rational probability distribution of which binary function to output. For example a gate which works as AND(x,y) with probability $\frac{7}{13}$, as OR(x,y) with probability $\frac{5}{13}$ and outputs constant $0$ with probability $\frac{1}{13}$.
The computation is allowed to have 2 sided bounded error - that is, we say that the circuit computes a function f if for every input $x_1, \ldots, x_n$ it outputs the correct result $f(x_1, \ldots, x_n)$ with probability $\geq 2/3$.</p>

<p>Is it possible to similarly prove that there exists a Boolean function that requires probabilistic circuit of a superpolynomial size?
The problem is that there are infinitely many different types of gates. Is there any neat trick that could be applied?</p>

<p>The question I <em>actually</em> am interested in is the following - does there exist a Boolean function such that every 2-way probabilistic finite automata (having arbitrary rational transition probabilities) that recognizes it with 2-sided error has superpolynomial number of states? Just thinking that people are more familiar with circuits than 2-way automata and the proof could be transferred from one domain to another.</p>

<p><strong>Update:</strong></p>

<p>More formally I want to prove the following:</p>

<blockquote>
  <p>There exists an infinite sequence of Boolean functions $f_1, f_2,
\ldots$ of $n_1, n_2, \ldots$ ($n_1 &lt; n_2 &lt; \ldots$) variables such
  that for every sequence of 2pfas $P_{f_1}, P_{f_2}, \ldots$ such that
  $P_{f_i}$ recognizes $f_i$ with 2-sided bounded error (that is for
  every word $x_1, \ldots, x_{n_i}$ accepts it with probability $\leq
\frac{1}{3}$ if $f_i(x_1, \ldots, x_{n_i}) =0$ and probability $\geq
\frac{2}{3}$ if $f_i(x_1, \ldots, x_{n_i})=1$) the number of states
  grows superpolynomially: for every polynomial $p(n)$ exists $i$ such that the number of
  states $\left| P_{f_i} \right| &gt; p(n_i)$.</p>
</blockquote>

<p>If we allowed the 2pfa to have only transition probabilities of $\{0, \frac{1}{2}, 1\}$ (or some other restricted set (size of which might depend on $n$ and even grow exponentially in terms of $n$)) then it is provable by a counting argument. Question is - is it still true if all rational transition probabilites are allowed?</p>

CC BY-SA 3.0
2013-01-13T07:46:09.270Z
You can easily simulate these by usual {And, Or, Not} circuits plus random bits.
Kaveh
CC BY-SA 3.0
2013-01-13T08:01:53.747Z
How do you define the (bounded-error) recognition of a Boolean function by a 2pfa?
Abuzer Yakaryilmaz
CC BY-SA 3.0
2013-01-13T08:48:45.723Z
@Kaveh Yes, but the simulating circuit won't be of a polynomial size. To simulate 1 gate with a complex probability distribution you will have to have many random bits.
kbkb
CC BY-SA 3.0
2013-01-13T08:59:01.573Z
@AbuzerYakaryilmaz - The 2pfa has a special accepting state $q_{acc}$ and given the input $x_1, \ldots, x_n$ it ends in $q_{acc}$ with probability $\leq \frac{1}{3}$ and $\geq \frac{2}{3}$ if $f(x_1,...,x_n)=0$ and $f(x_1,...,x_n)=1$ respectively
kbkb
CC BY-SA 3.0
2013-01-13T09:46:56.597Z
@KasparsBalodis: Do you have a 2pfa for each $ f $  and $ n $, i.e. $ P_{n}^f $?
Abuzer Yakaryilmaz
CC BY-SA 3.0
2013-01-13T11:04:42.840Z
@AbuzerYakaryilmaz: Yes. I updated the question to clarify it more formally.
kbkb
<cc.complexity-theory><automata-theory><lower-bounds><randomness><probabilistic-automata>
Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions
kbkb
# Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions

(Asked by: username_0 on 2013-01-13)

If we consider circuits with arbitrary binary logic gates one can prove by a counting argument that there exists a Boolean function on $n$ variables that require a circuit of size $ \Theta \left( 2^n/n \right) $ (in fact almost all of them are such).

This follows from the fact that there are $2^{2^n}$ Boolean functions on $n$ variables and only at most $16^k (k+n+1)^{2k} k / k!$ different Boolean functions on $n$ variables can be computed by circuits of size $k$ (for each gate there are $16$ possibilities to choose its type and $b+n+1$ possibilities to choose its two predesscors (the other $k-1$ gates, $n$ variables and $2$ constants), $k$ possibilities to choose the final gate and there are $k!$ possibilities to renumber the gates)

I am interested in probabilistic circuits in the following (nonstandard) sense - using gates which can have arbitrary rational probability distribution of which binary function to output. For example a gate which works as AND(x,y) with probability $\frac{7}{13}$, as OR(x,y) with probability $\frac{5}{13}$ and outputs constant $0$ with probability $\frac{1}{13}$.
The computation is allowed to have 2 sided bounded error - that is, we say that the circuit computes a function f if for every input $x\_1, \ldots, x\_n$ it outputs the correct result $f(x\_1, \ldots, x\_n)$ with probability $\geq 2/3$.

Is it possible to similarly prove that there exists a Boolean function that requires probabilistic circuit of a superpolynomial size?
The problem is that there are infinitely many different types of gates. Is there any neat trick that could be applied?

The question I *actually* am interested in is the following - does there exist a Boolean function such that every 2-way probabilistic finite automata (having arbitrary rational transition probabilities) that recognizes it with 2-sided error has superpolynomial number of states? Just thinking that people are more familiar with circuits than 2-way automata and the proof could be transferred from one domain to another.

**Update:**

More formally I want to prove the following:

> There exists an infinite sequence of Boolean functions $f\_1, f\_2,
> \ldots$ of $n\_1, n\_2, \ldots$ ($n\_1 < n\_2 < \ldots$) variables such
> that for every sequence of 2pfas $P\_{f\_1}, P\_{f\_2}, \ldots$ such that
> $P\_{f\_i}$ recognizes $f\_i$ with 2-sided bounded error (that is for
> every word $x\_1, \ldots, x\_{n\_i}$ accepts it with probability $\leq
> \frac{1}{3}$ if $f\_i(x\_1, \ldots, x\_{n\_i}) =0$ and probability $\geq
> \frac{2}{3}$ if $f\_i(x\_1, \ldots, x\_{n\_i})=1$) the number of states
> grows superpolynomially: for every polynomial $p(n)$ exists $i$ such that the number of
> states $\left| P\_{f\_i} \right| > p(n\_i)$.

If we allowed the 2pfa to have only transition probabilities of $\{0, \frac{1}{2}, 1\}$ (or some other restricted set (size of which might depend on $n$ and even grow exponentially in terms of $n$)) then it is provable by a counting argument. Question is - is it still true if all rational transition probabilites are allowed?

**Tags:** cc.complexity-theory, automata-theory, lower-bounds, randomness, probabilistic-automata

> **Comments:**
> **username_1**: You can easily simulate these by usual {And, Or, Not} circuits plus random bits.  
> **username_2**: How do you define the (bounded-error) recognition of a Boolean function by a 2pfa?  
> **username_0**: @username_1 Yes, but the simulating circuit won't be of a polynomial size. To simulate 1 gate with a complex probability distribution you will have to have many random bits.  
> **username_0**: @AbuzerYakaryilmaz - The 2pfa has a special accepting state $q_{acc}$ and given the input $x_1, \ldots, x_n$ it ends in $q_{acc}$ with probability $\leq \frac{1}{3}$ and $\geq \frac{2}{3}$ if $f(x_1,...,x_n)=0$ and $f(x_1,...,x_n)=1$ respectively  
> **username_2**: @KasparsBalodis: Do you have a 2pfa for each $ f $  and $ n $, i.e. $ P_{n}^f $?  
> **username_0**: @AbuzerYakaryilmaz: Yes. I updated the question to clarify it more formally.  

---

## 1 answers

### Answer by username_3 on 2013-01-15. Score: 4

You can still argue by counting. No matter how randomness is used, there is a way to fix the randomness in such a way that the function is computed correctly deterministically on at least $\frac{2}{3}2^n$ inputs. Thus assuming any function can be computed with error at most $\frac{1}{3}$ by some circuit in size $S$, any function can be described by a circuit of size $S$ together with a set of at most size $\frac{1}{3}2^n$ of inputs where the answer is incorrect.

> **Comments:**
> **username_0**: I am not sure if I completely understand your answer.    I think there is a problem that (for 2pfa-s) I measure the device size $S$ by the number of states, but it doesn't imply any bound on how many bits do I need to describe the probabilistic transition function.   And I don't see how can you determinize the transition function without a blowup in the number of states as each transition can be used many times during one run of the automaton.  
> **username_3**: Yes I believe you misunderstand. After fixing the randomness there is no randomness left.  
> **username_0**: Now I see. This approach indeed works for circuits because every gate in a computation is used only once and you can fix it. However it does not translate to 2-way probabilistic finite automata easily because there every state (and therefore also the transition function) can be used many times in a single computation.  
> **username_3**: I was indeed thinking about circuits, and I am not sure what to do with automata. I have changed my answer to avoid claiming too much.  
> **username_3**: Actually, can you not make it work for automata in the following way: Since you care only about strings of length n, each state will be visited at most n times. Then in the "automata" obtained after fixing randomness, each state will have a list of n next-state transition functions. Each time a state is visited, the next unused transition function is used.  
> **username_0**: No, these are 2-way automata that can move back and forth the input (transitions are a function from a state and a symbol to a new state and {left, no_move, right}. The last part corresponds to the movement of the head. In probabilistic case it's a function from state, symbol, state, {L,N,R} to [0,1]) so each input symbol can be visited more than once (in deterministic case no more than the number of states (otherwise it would cycle), but that's not true in the probabilistic case).  

---

