A man has n hats that he keeps in two drawers. Every morning, he flips a (fair) coin to choose a drawer at random to take a hat from, if there is one. Every night, he flips a coin to choose which drawer to put the hat back into, if he wore one. What is the fraction of days he does not wear a hat?
I'm quite stuck on how to get going... Any help is appreciated.
On
Common sense answer: On a day he wore a hat, he flips a coin to decide which drawer to put it in. He has a fifty fifty chance of putting it in the same drawer as the other hat and a fifty fifty chance of putting it in the other drawer. So on half the days the hats are in the same drawer and on half the days they are in different drawers. On the days they are in different drawers, he will always wear a hat. On half of the days where they are in the same drawer he will wear a hat and on half of those days he will not. So he will wear a hat one-quarter of the days.
AND THE COMMON SENSE ANSWER IS WRONG. Even if n = 2.
You have a simple Markov chain on $n+1$ states (enumerated by the number of hats in the first drawer). Simple calculation shows that in steady state all states are equiprobable - hence they have probability $\frac 1 {n+1}$. A man doesn't wear a hat only in states $0$ and $n$ and in those states probability of non wearing a hat is $\frac 1 2$. Hence he doesn't wear a hat on $\frac 1 {n+1}$ fraction of days.