Understanding increased file size after video compression

I compressed my video file, but after upload/conversion the file is actually a little bigger. Why?

The quality and file size of a video are directly related to bitrate. To make the file size smaller, you reduce the bitrate of the video (compression), but you also begin to lose quality. The trick is finding the balance so you have a faster-loading file and still have a quality viewing experience.

The (third party) video-conversion utility integrated into our uploader is set to convert files to a bitrate that is deemed to be that happy medium for web viewing. Any video uploaded that has a higher bitrate gets its bitrate reduced in order to make a smaller, faster-loading video file (while preserving a good level of quality). On the other hand, if you upload a video that was previously compressed to a lower bitrate than the converter's output setting, it will end up with a higher bitrate - and slightly larger file size.