This took a bit longer than I would care to admit, but I have finally computed the expected gain of stars per game. The answer depends a little bit on information available and interpretation.
Let denote the probability of you winning a game, which is considered to be constant. If you are on a win streak, meaning you’ve won the previous two games, then the expected winning of your next game is . The probability that you’ve won your previous two games is , so this case contributes to the total expected value. Otherwise, the expected winning is . The probability of this is , so the contribution for this case is . Summing, we obtain that the total expected value of the gain of stars is
Thus, if you win half the time (so that ), you should expect to gain roughly one star every 8 games or so.
Another Hearthstone related problem, which I worked out with my officemate, is to ask what is the probability of you getting the card you need on turn 1 assuming you are going first and that you are willing to discard all other cards in your initial draw in order to get the card that you want. First, the probability that the card you need will appear in the initial draw of three cards is
If you did not get either copy of the card that you need, then you may discard all three cards and try again, knowing that the three cards you tossed cannot come back. In this case, the probability of you getting the card you need is the product of the probability of you not getting the card you want in the initial draw and the probability of getting at least one copy of the card that you need in the second draw.
Adding these, we get some pretty neat cancelations and end up with the simple expression of .
However, we have not yet accounted for the random card that you top deck after your initial draw on turn 1. The only remaining case that needs to be considered is when you failed to get the card you need after tossing all of your cards on the initial draw. In this case, the probability of getting the card you need is
which is about 0.041963. Adding, the total probability is about , or slightly less than one in four.