# User:Orby/Stochastic

Let *x* be a real number in [0, 1]. Let *y* be a random variable which is equal to 1 with probability *x* and 0 otherwise. I have been considering a language that performs computation by sampling *y* and manipulating the value. This would fall under the category of stochastic computing.

## Encoding a tape

Suppose we have a right unbounded binary tape. Let *n _{i}* be the value of the

*i*-th cell. We can let

*x*represent the tape if we set

*x*:= Σ

*n** 2

_{i}^{-i}.

Let *z* be equal to 1 with probability 0.5 and be equal to 0 otherwise. We can sample *y* w.r.t. the right unbounded binary tape in the following way

*i*:= 0*i*:=*i*+ 1- if (
*z*== 1) goto (2) *y*:=*n*_{i}

## Decoding a tape

By sampling *y* *m*-times and computing the mean, we get a value that converges on *x* as *m* approaches infinity. To compute *n _{i}*

*i*:= 1*m*:=*m*÷ 2*n*:=_{i}*j*÷*m**j*:=*j*%*m**i*:=*i*+ 1- goto (2)

where *m* is initialized to the number of samples taken and *j* is initialized to the number of ones sampled.

## Decoding the output of a program

Running the program *n* times. Each output will be a zero or a one. Computing the mean and call it *x _{n}*. As

*n*goes to infinity,

*x*goes to the output value of the program. Note with this particular encoding of the tape, we get back earlier cells with greater accuracy than the later cells for a given

_{n}*n*.

## Sample programs

### Cat

y

### Flip every bit on the tape

~y