Sunday, 26 June 2011

nt.number theory - Expressability of an electrical circuit with probabilistic switches

Here is a purely number theoretical question that I got to know from our electrical engineering department.



Call a number $qin mathbb{N}$, good if one can do the following:



Given a set of "probabilistic" switches, each of which is open with probability $frac{a}{q}$, $a=1,2,dots,q-1$ (you have infinitely many of each type), and two nodes $U,V$. Then for every $n,bin mathbb{N}$ such that $ble q^n-1$ one can build a simple series parallel circuit (where one can use each type of switch more than once) connecting $U$ to $V$ where the probability of $Uto V$ being open is exactly $frac{b}{q^n}$.



The question is which numbers are good? I think the conjecture is that only numbers which are multiples of $2$ or $3$ are good. $5$ for example is not good as one can not construct a circuit which is open with probability exactly $frac{7}{25}$.



P.S. A "simple series parallel" circuit is one that can be build recursively by the operation of placing a switch in series with our circuit or placing a switch in parallel with our circuit. For example the wheatstone bridge is not simple series parallel. Also if one for example, connects between $U,V$ two switches with probabilities $p_1,p_2$ (of being open) in series one gets a probability of $p_1p_2$ of the section $UV$ being open, while if we connect them in parallel we get a probability $1-(1-p_1)(1-p_2)$ of it being open.



EDIT: I will rephrase the question in simple mathematical terms, as the original question is poorly phrased.



Let $qin N$. A set $S_qsubset mathbb{Q}$ contains all numbers of the form $frac{a}{q}$, with $a=1,2,dots q-1$. It also satisfies the property $xin S_qimplies frac{ax}{q}in S_q$ and $x+frac{a-ax}{q}in S_q$ for any $a=1,2,dots q-1$.



For which $q$ does $S_q$ contain every number of the form $frac{b}{q^n}$ (where $b < q^n$)?

No comments:

Post a Comment