validation/training accuracy and overfitting If we randomly split the data into training data and validation data, and assume the training data and validation data have similar "distributions", i.e. they are both good representations of the whole data set.

In this case, should the validation accuracy always be roughly the same as the training accuracy if there is no overfitting? Or is it possible that, for some cases, there could exist an "intrinsic" gap between the training and validation accuracy that is not due to overfitting or bad representation of the validation data?

If such "intrinsic" gap exists, how to tell if the gap between the training and validation accuracy is "intrinsic" or caused by overfitting?
I'm not sure what you mean by 'intrinsic'.  

A higher training accuracy means you have found a model of the training data that doesn't describe the validation data equally well.  Because of this, any statistically significant difference in training-validation accuracy is due to overfitting.   Figuring out what 'statistically significant' means in this context is not totally trivial, unfortunately, but the general point still stands.