Actually I think you have two problems.
First, Recessed cans come with a thermal overload, so if the fixture heats up beyond normal the thermal protector turns it off. These protectors can get worn and will trip at random until replaced. You might see if you can access your can from above and if it is covered with insulation then you need to pull the insulation away from it so it will operate cooler. This might fix the problem, if not you will need to replace the unit. Unfortunately you really can't replace the thermal protector without replacing the can. This really isn't for a DIY, you need someone who knows how to get the parts, take down the bad parts and reassemble the fixture.
Second, If your outlet is overheating from the Christmas lights, that is an indication of a loose or bad connection in the receptacle or splices in the box. If you need to remove the cover and check out the wiring. Also if the outlet conductors are stabbed in at the back of the receptacle you need to remove them and wrap the around the side terminals. There is plenty of comment on this subject on this site so no need to go into detail.
Last is just to answer your final question. Its really easy to find out if your receptacle and lights are on the same circuit. Just go to your circuit breaker panel and it should be marked, but if it isn't then you just need to turn each breaker on and off until the circuit in question turns off.
Good luck and Happy Holidays.