There are three big options.

The easiest option is to use an update frequency that is tuned really well, so that the game will register fast running as going over the gap, and slower running as falling in. This option is probably not the most robust (can be error prone or give mixed results). HappyCoder suggested this kind of thing (post above this one).

The second is to have some game logic that separates fast and slow running. During fast running you can do additional checks to look ahead for gaps and prevent falling.

The last option is to place little level markers over gaps, like in a level editor. When the character hits them you can check to see if the character is fast running, or slow enough to fall into the gap.

There are two issues at play.

The first is how Mario is considered to be on top of something.

In many games, including most of the SMB series, the physics shape is a capsule, something rounded on the bottom. In the case of Mario's physics, the 2D games he has a shape like: \__/

If Mario clips the corner of a tile he will be assumed to be on top of the tile. (Also if he is moving down when he hits an enemy in several SMB versions he is considered as jumping on it, even if the creature is halfway up his body it is only his vertical direction that matters. But that's another fun story)

Because mario is more like a collision capsule than a collision rectangle, if Mario comes very close to stepping on a ledge, if he is very close, within a few pixels (exact value depending on the game) Mario will be treated as standing on top and will pop back up to ground level.

The second is the exact speeds.

While some of the motion speeds were just values that felt good, the game designers spend a long time intentionally tuning games for these effects. The design team intentionally tuned his speed so at full speed he could run across a full tile gap and clip the corner of his collision capsule.

Every game has slightly different, the older GBA games were tuned to different values than the NES and SNES and later Wii games, but for all of them the developers recognized it was important to make that behavior happen. So they tuned and adjusted and made slight modifications until everything was just right.

A few moments on Google and you can find the physics details of most of the Mario games, his speeds for walking and running and falling, and often the clipping for corners. This one has motion speeds all figured out for SMB1 and SMB2j, with a maximum running speed of 2 + 9/16 pixels per frame. The site says Mario's falling gravity in that game is based on his run speed the moment he falls off an edge, with different gravity values triggering at 2+5/16 speed. And of course, different games have different carefully-tuned values.

The easiest option is to use an update frequency that is tuned really well, so that the game will register fast running as going over the gap, and slower running as falling in. This option is probably not the most robust (can be error prone or give mixed results). HappyCoder suggested this kind of thing (post above this one).

Actually, I believe this is exactly what Mario used. I played different versions of Mario a lot, and IIRC the player could still fall through gaps even when running, when just speeding up (or when slowing down to normal speed).

Most likely, the gap-skip would happen in only one or two frames, and the gravity didn't have time to kick in in that amount of time. To increase the effect, you could also round the position of the player to integers (and round gravity to lower bounds). I think Mario does this, since it always displays the character at pixel coordinates.