Navigation

Part 1: Pascal's todolist

When I woke up yesterday afternoon, I suddenly realized that my todolist (the ascii file that I have on my computer with the list of all the things I have to do such as reading stuff on the web, watching movies, think of particular subjects, send emails to friends, buy specific stuff, learn stuff etc...) is actually the conjunction of two simpler lists, which are actually queues.

The first one is a FIFO (First In First Out) queue and the second one a LIFO (Last In First Out) queue. In this text I will refer to both queues as q1 and q2.

When I want to put something in my todolist, there is a non-deterministic choice of which of the two queues the item will go into. Once the queue is chosen then the item is put into this queue (using the queue's standard put method).

When I want to get something from my todolist, for instance because I have a couple of hours to kill and want to do something , there is a non-determinstic choice of which queue I am going to pick into and then retrieve an item from the queue (using the queue's standard get method). Note that if only one of the two queues had elements then that queue is automatically the chosen one.

This this model in mind you can understand that the order under which things are output by my todolist has no particular bearing with the order under which things came into it :-)

Part 2: Digits

In this part we are going to assume that the elements that we put in the todolist are simple binary digits, elements of the set {0,1}. In this case we will call the todolist the MainQueue. We will also assume that we have a (finite) supply of digits and that we always fill the MainQueue before starting to empty it.

Given a sequence x of digits, we denote l(x) the length of x, and we denote w(x) the number of 1s in the sequence. We have the following nice result.

Lemma 1: Given any sequences x and y, if l(x)=l(y) and w(x)=w(y) then there exists a run of the MainQueue so that using x as an input sequence, it outputs y.

Part 3: Probabilistic Behavior

There are various ways to remove (sometimes partially) the hypothesis of non-determinism. When I did last night I ran into some interesting Markov Decisions Processes, but for the purpose of this entry I will ignore them and consider a purely probabilistic setting.

Removing the non-determinism on the MainQueue put operation can be done by assigning a probability to the fact of selecting the first queue. We denote p such a probability and we will refer to p as "the probability of the MainQueue". So given p \in [0,1] a put operation on the MainQueue will use the first queue with probability p and will use the second queue with probability (1-p).

Note that even without having defined any retrieval strategy on the get method method of the MainQueue, we already have the following results.

For p=1 then the output is always equal to the input. This comes from the fact that when p=1 then the MainQueue simply behaves like its embedded FIFO queue. Similarly, when p=0 the output is the reserved sequence of the input (due to the embedded LIFO queue).

There are various way to embed a probabilistic behavior for the MainQueue get operation, but I decided to keep it simple and decide that for a get operation, the first queue is selected with probability s(q1) / ( s(q1) + s(q2) ). The idea here is to probabilistically favor the internal queue with the biggest number of elements. Note that unlike p, the MainQueue put probability, the get probability is recomputed every time an elements is added or removed to any of the internal queues (in other words every time an element is added or removed from the MainQueue).

Part 4: Question

We denote by X_{n} the set of all sequences of digits of length n. Given x and y in X, we can easily compute the probability to generate the output y from the input x. Consequently given a fixed x0 in X_{n} we have defined a function K_{n} from X to [0,1] which compute the probability of obtaining y from x0.

We have the following little result:

Lemma 2: for y in X_{n}, if w(y) != w(x) then K_{n}(y) = 0.

X_{n} is a finite set of size 2 to the power n, not very interesting for want I want to do, so let us denote by X the union of all the X_{n} for n ranging over the natural integers. X contains all the finite sequences of binary digits.

We consider r an infinite sequence of binary digits. We now define K from X to [0,1] as follows: given y in X, there exists n such that y is in X_{n}, then K(y) is the probability that the MainQueue outputs y from the first n digits of r.

nb: It wasn't required to work with r (which is the only infinite sequence in our story), we could have considered an infinite sequence (r_{j}) of finite sequences of integers so that for every j, r_{j} is in X_{j}, and defined K such that given y in X, then K(y) is the probability that the MainQueue outputs y from r_{n} where n is the length of y.

Question: Is there a non trivial metric on X which makes K a continuous function ? This question has got an obvious answer (yes) when p=0 or p=1, but I do not know then answer for other MainQueue probabilities.