# Reconstruct a "blocky" picture?

Consider a finite set $A$. Let the sample space be $A\times A$. We have an unknown probability distribution $f$ on this sample space. Now this probability distribution has a "blocky" property, which I am going to explain.

Let a block be a function (not necessarily probability distribution) over the sample space $b_{(B,C,r)}$ where $B,C\subset A$ and $r$ be any real number (not necessarily in $[0,1]$). Then $b_{(B,C,r)}(x,y)=r$ if $(x,y)\in B\times C$ and $b_{(B,C,r)}(x,y)=0$ if not. Then $f$ can be written as a finite sum of those blocks (at most $|A|^{2}$ of them in fact). Let $X$ be the minimum number of blocks needed to sum to $f$. If prior to observing any trials, we know that $X$ follows a geometric distribution with unknown $p$ truncated to $[1,|A|^{2}]$ then we say that $f$ is "blocky". (Note that despite the analogy to reconstructing a picture, a block need not be a rectangle: there is no relationship among elements in $A$)

Now we are given the outcome of a number of trials, where each trial consists of picking an element in the sample space with probability given by that unknown but "blocky" probability distribution $f$. The task is to make estimate of $f$ of each possible outcome.

So what is a good algorithm for that?

I'm sorry that I am new to statistics and thus I was not able to phrase this in a more proper way, and I do not even know if this problem has a solution or not, so it might be trivial or unsolved for all I know. Hope I can get some help on this. Thank you for any help you can give.

• Precisely how does $f$ "give" a probability? Based on your description, its range can include values outside the interval $[0,1]$. Even when its range does lie in this interval, how are the values of $f$ to be interpreted--as relative weights?
– whuber
Feb 16, 2014 at 18:32
• $f$ is already a probability distribution. Now I think I know where your objection come from, so I would attempt to explain it. If you just grab some random blocks and add together, it need not be a distribution. But we start with an $f$ already being a distribution. The value of $X$ is invariant under multiplication of $f$ by a nonzero constant anyway.
– Gina
Feb 16, 2014 at 22:08