0
$\begingroup$

Is there a statistical formula/function to calculate number of basic geometric shapes on the displays of random pixel generator?

Let's say we have a basic random pixel generator which has 10*10 screen resolution, 100 pixels each having 3 colors (blue, green & red). What are the odds of getting a rectangular 6 pixel solid color image (2X3, 3X2, 1X6 or 6X1 all connected having same color) on the screen?

What is the right approach/logic to make such calculation? Is enumerating all possible outcomes only way to come up with a likelihood?

$\endgroup$
2
  • 1
    $\begingroup$ Enumeration isn't computationally feasible, $3^{100}$ being a very very large number, but simulation is, and actually rather easy too. $\endgroup$
    – jbowman
    Commented Mar 6, 2019 at 16:12
  • $\begingroup$ @jbowman Can you please simulate the likelihood? Is it a high likelihood or low? Would be good to know some relationship between color number and pixel number as well. I couldn't have a clear answer to my question. Thanks! $\endgroup$
    – Bert
    Commented Mar 6, 2019 at 18:37

1 Answer 1

0
$\begingroup$

This is more exploratory Commentary than an Answer.

As far as I can see this will be a fairly messy problem. For simplicity, let's start by figuring out if any of the ten rows on your 'screen' will have six or more pixels of the same color in a row.

Begin by using R to simulate the probability of getting a run of six or more pixels of the same color in a single row of ten positions. [Colors RGB are denoted 123; rle is R's 'run length encoding' function, from which we can get the lengths of runs of colors, and hence the maximum run length. At the end of the simulation mx >= 6 is a logical vector of a million TRUEs and FALSEs; mean(mx >= 6) is the proportion of its TRUEs.]

set.seed(2019)  # for reproducibility
col = 1:3
mx = replicate( 10^6,  max(rle(sample(col, 10, repl=T))$len) )
p = mean(mx >= 6);  p
[1] 0.015034

Thus the probability of a run of five of one color in one row of ten pixels is $p = 0.015.$ With a million iterations, this result should be accurate to about three decimal places.

[There is considerable literature on counting numbers of runs; you may prefer to use ideas there to get an exact result by analytic means. There are users of this site who are better at combinatorial computations than I; maybe someone will post a better answer.]

Now let the random variable $X$ be the number of such color runs among ten independent rows, where $X \sim \mathsf{Binom}(10, p).$ We find $$P(X > 0) = 1 - P(X = 0) = 1 - (1-p)^{10 }\approx 0.14.$$

1 - pbinom(0, 10, p)
[1] 0.1405663

The answer for columns on your screen should be the same. It will be a little more difficult to find the probability of $2 \times 3$ arrays of color-matched pixels and then the probability that any one of the four configurations you mentioned will occur. (Because the four types of outcomes are not mutually exclusive, the last step will not be as simple as adding four probabilities.) Finally, to me, it seems a bit arbitrary not to include patterns such as the one below (in which * is a non-red pixel):

***RRRR***
****RR****

Note: Here is a demonstration of getting mx from one simulated row of ten, for which the maximum run happened to be of length 3.

 row = sample(1:3, 10, repl=T); row
 [1] 1 1 3 3 2 2 2 1 3 2             # RRBBGGGRBG
 rle(row)
 Run Length Encoding
   lengths: int [1:6] 2 2 3 1 1 1
   values : int [1:6] 1 3 2 1 3 2
 rle(row)$len
 [1] 2 2 3 1 1 1
 max(rle(row)$len)
 [1] 3
$\endgroup$
1
  • $\begingroup$ Thanks for your insight. I see some literature on this pixel connectedness subject that concerns pixel positions (x,y), (x+1, y+1) etc However my math on probabilities is not advanced enough to elaborate on all these calculations. I cannot understand such simulation codes either. It will be appreciated to have a mathematical demonstration on the likelihood of having such 6 pixel solid color shapes. It would be good to know correlation between pixel numbers and color numbers too. $\endgroup$
    – Bert
    Commented Mar 6, 2019 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.