5
$\begingroup$

...and encoding it as a probability distribution.

Suppose we have a sequence of non-negative integers that is periodic with period $N$:

\begin{equation*} A_{1},A_{2},...,A_{N},A_{1}... \end{equation*}

Each $A_{k}$ takes on a value no greater than some constant $B$:

\begin{equation*} 0 \leq A_{k} \leq B \end{equation*}

We then take this sequence and do a simple convolution, for some constant $L > 0$ and $1 \leq n \leq N$:

\begin{equation*} S_{L}(n) = A_{n} + A_{n+1} +...+ A_{n+L-1}. \end{equation*}

From $S_{L}(n)$ we then form a probability distribution $P(n)$ which gives the frequency of each of its values. Let $e_{j}(k) = 1$ if $j = k$ and $0$ otherwise. Then:

\begin{equation*} P(n) = (e_{n}(S_{L}(1)) + e_{n}(S_{L}(2)) +...+ e_{n}(S_{L}(N))) / N. \end{equation*}

What I would like to find out is the extent to which this process can be reversed. I have two data points:

1) I know (pretty much) everything about the probability distribution $P(n)$: the distribution itself, its mean, range, variance, skewness, kurtosis, etc.

2) I can tell you the frequency of values of $A_{k}$ in one period, so that if the sequence is 1,0,2,3,1,0, I can tell you there are two 0's, two 1's, one 2, and one 3.

To what extent am I able to reconstruct the sequence $A_{k}$ from these two data points?

  • 0
    I've added an answer below showing it's impossible to reconstruct the sequence, but you'll probably get better answers if you explain your motivation and/or what sort of answers to "to what extent" you'd like. (For instance, you can always "reconstruct" the frequencies because you already know them. :p)2010-08-03
  • 0
    BTW: instead of talking of your probability distribution, it's simpler to talk of just the frequencies (how many times a number appears as $S_L(k)$ for some $1 \le k \le N$), because the distribution just divides by $N$ (and mean, variance, etc. are less information than the distribution itself).2010-08-04

1 Answers 1

2

No, you cannot recover the sequence $A_k$. As a trivial example, note that any cyclic permutation of $(A_1, A_2, \dots, A_N)$ would result in the same distribution (and frequencies). But since this is a periodic sequence, you probably don't care about distinguishing between cyclic permutations of the same sequence, so here's another example.

Consider L=1. Then your probability distribution is just equivalent to the frequencies, so any permutation of the $A_k$s would give the same distribution. If L=1 is too degenerate, here's another example with L=2.

Say $L=2$, and $N=10$. Then, both sequences $(1, 1, 0, 0, 0, 1, 1, 0, 0, 0)$ and $(1, 1, 0, 0, 0, 0, 1, 1, 0, 0)$ would have the same distribution of sums $S_L$: 2 twice, 1 four times, and 0 four times. You can easily extend this example to any $L$.

  • 0
    Hi ShreevatsaR, thanks for the answer. You are correct that I am ignoring cyclic permutations of the sequence. It appears that the original sequence is being blurred too much, and I need some more data points.2010-08-13