According to the AWS doc:
When you stop a running instance ... The instance is migrated to a new underlying host computer when it's started.
Here is also slightly different statement from the same doc:
When you start your instance, it enters the pending state, and in most cases, we move the instance to a new host computer. (Your instance may stay on the same host computer if there are no problems with the host computer.)
So what is the rationale behind the need to move instances to a new host when they are restarted?
The only reason this question has emerged is that I found a question in an AWS Certification Exam sample asking whether migration to new host happens, and currently see no way how one would be able to guess the correct answer.
When you stop an instance compute resource is released. That compute resource can be reused by others while you don't need it, even if it's just a second until you ask for it again. When you request new compute resources you're allocated whatever resources are available. There's no reason it would be started on the same host, this request is not connected to the previous request. It might be that the instance was on an old previous generation host that Amazon wants to derack, or a server showing signs of failure. Most often it's just irrelevant where the instance starts.
Note that a restart of the instance does keep the instance on the same hardware, and ephemeral stores are kept. It's an explicit stop then start that moves it to new hardware.
Update - I checked with Amazon about this and they basically agree with what I said.
"The second sentence is more technically accurate - in most cases, the instance is moved to new hardware but we don't guarantee it. There may be a very small percentage of cases where it isn’t. However, we will not restart the instance on the same hardware if there is an issue with the hardware."