jump to navigation

What are the odds of randomly generating a video? Monday 2/7/11

Posted by smcgamer in Archive, Uncategorized.
trackback

I like to figure out the odds for things that are so long that they will never happen – like the monkey and the typewriter – that is, the odds of a monkey randomly banging a typewriter to perfectly reproduce the complete works of Shakespeare.

Today, I’ll examine the odds of perfectly reproducing a thirty-minute video at 30 frames per second at 24 bits per pixel by using a random video generator.  This hypothetical generator can produce 50 random half-hour videos each day.

Images of mathematical equations and whatnot provided by Wolfram|Alpha.

Bit Depth

Let’s start with bit depth.  Bit depth, or number of bits per pixel, is the number of bits each pixel receives.  Because a bit can be in two states, zero or one, the equation for figuring out the maximum number of colors is as follows:

Here are some common (and not-so-common) bit depths and how many colors each of them has:

  • 1 bit per pixel = 21 = 2 colors
  • Example of a 2x2 Pixel Bitmap, with 24 bits/pi...

    Image via Wikipedia

    2 bits per pixel (used in the NES) = 22 = 4 colors

  • 3 bits per pixel (used in the SNES for most sprites) = 23 = 8 colors
  • 4 bits per pixel (used in Windows 95) = 24 = 16 colors
  • 8 bits per pixel (maximum colors for a GIF) = 28 = 256 colors
  • 16 bits per pixel = 216 = 65,536 colors
  • 24 bits per pixel = 224 = 16,777,216 colors
  • 32 bits per pixel (24 bits + 256 shades of transparency) = 232 = 4,294,967,296 colors and shades of transparency

Let’s say we were to make a random pixel by using a random number generator that can output 100,000 pixels per second, and one color is the correct color.  The odds would be as follows (decimals rounded up if necessary):

  • 1 bit per pixel = 2 colors = 1-in-2 chance = ≈50,000 correct pixels per second
  • 2 bits per pixel = 4 colors = 1-in-4 chance = ≈25,000 correct pixels per second
  • 3 bits per pixel = 8 colors = 1-in-8 chance = ≈12,500 correct pixels per second
  • 4 bits per pixel = 16 colors = 1-in-16 chance = ≈6,250 correct pixels per second
  • 8 bits per pixel = 256 colors = 1-in-256 chance = ≈391 correct pixels per second
  • 16 bits per pixel = 65,536 colors = 1-in-65,536 chance = ≈2 correct pixels per second
  • 24 bits per pixel = 16,777,216 colors = 1-in-16,777,216 chance = ≈2:48 per correct pixel
  • 32 bits per pixel = 4,294,967,296 colors = 1-in-4.2 billion chance = ≈11:55:49 per correct pixel

That’s the odds for just one pixel.  For two pixels, the odds become much larger.  The equation is (number of colorsnumber of colors).

  • 1 bit per pixel = 2 colors = 22 = 4 combinations = ≈25,000 correct pixels per second
  • 2 bits per pixel = 4 colors = 44 = 256 combinations = ≈391 correct pixels per second
  • 3 bits per pixel = 8 colors = 88 = 16,777,216 combinations = ≈2:48 per correct pixels
  • 4 bits per pixel = 16 colors = 1616 = 18 quintillion combinations = ≈5.8 million years per correct pixels
  • 8 bits per pixel = 256 colors = 256256 = 3.23 x 10616 combinations = ≈1.02 x 10601 millenia
  • 16 bits per pixel = 65,536 colors = 6553665536 = 6.74 x 10315612 combinations = ≈2.13 x 10315631 eons (1 eon = 1 billion years)
  • 24 bits per pixel = 16,777,216 colors = 167772161677216 = 1.71 x 10121210686 combinators = So long not even Wolfram|Alpha can compute it
  • 32 bits per pixel = 4,294,967,296 colors = 42949672964294967296 = 41,373,247,568-digit-long number of combinations

That’s right – eons.  And this is just for two pixels.  Our video’s resolution is 640 pixels wide by 480 pixels high, or 307,200 pixels at 24 bits per pixel = 7,372,800 bits total.  The number of combinations is equal to 27372800 combinations, which equals 8.94 x 102219433 combinations.  That’s 2 million digits.  Per frame. If a computer can generate 1,000 of these per second, that only knock off 3 digits, making it 8.94 x 102219430 seconds.  And a googol seconds is only 10100 seconds.  This is immensely larger than the known age of the universe.  And that’s only for one frame!

30 frames of raw 640×480 video at 24 bits per pixel = 221,184,000 bits.  2221184000 = 3.63 x 1066583018 combinations. At ≈33 seconds of video generated per second, that’s 1.1 x 1066583017 seconds before it can find the right frame.

The ultimate calculation: 1800 seconds of video at 30 frame per second.  That’s 640 pixels by 480 pixels by 24 bits per pixel by 30 frames per second by 1,800 seconds (one half-hour, or 54,000 frames).  That’s 398,131,200,000 bits, or 46.34 GB of raw video.

The result? 119,849,433,410 digits indicating the number of possibilities.  119 billion digits.

At 50 videos generated a day, that’s 10 to the 1011.07th power combinations per day (roughly 119,849,433,409 digits).  Divide that by 365,000 (number of days in a millenium), and you get a 1-in-10119849433404 chance that it would get it right in a millenium.  It’s only 119,849,433,398 digits long if you work for an eon.  A googol years would only bring it down to 119,849,433,310 digits, a centillion (10303) years would only be 119,849,433,107 digits.

Thanks a lot to Wolfram|Alpha!  Sorry I almost crashed your servers.


Advertisements

Comments»

No comments yet — be the first.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: